Processing math: 92%

USACO 2023 December Contest, Gold

Problem 1. Flight Routes


Contest has ended.

Log in to allow submissions in analysis mode


Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in N (2N750) cities labeled 1N, and for each pair of cities (i,j) with i<j there either exists a single direct flight from i to j or not.

A flight route from city a to city b (a<b) is a sequence of k2 cities a=c1<c2<<ck=b such that for each 1i<k, there is a direct flight from city ci to city ci+1. For every pair of cities (i,j) with i<j, you are given the parity of the number of flight routes between them (0 for even, 1 for odd).

While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

Then follow N1 lines. The ith line contains Ni integers. The jth integer of the ith line is equal to the parity of the number of flight routes from i to i+j.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the number of pairs of cities with direct flights between them.

SAMPLE INPUT:

3
11
1

SAMPLE OUTPUT:

2

There are two direct flights: 12 and 23. There is one flight route from 1 to 2 and 2 to 3, each consisting of a single direct flight. There is one flight route from 1 to 3 (123).

SAMPLE INPUT:

5
1111
101
01
1

SAMPLE OUTPUT:

6

There are six direct flights 12,14,15,23,35,45. These result in the following numbers of flight routes:

Flight Route Counts:

            dest
          1 2 3 4 5

       1  0 1 1 1 3 
       2  0 0 1 0 1 
source 3  0 0 0 0 1 
       4  0 0 0 0 1 
       5  0 0 0 0 0

which is equivalent to the sample input after taking all the numbers \pmod{2}.

SCORING:

  • Inputs 3-4: N\le 6
  • Inputs 5-12: N\le 100
  • Inputs 13-22: No additional constraints.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.