We are programmers. Everything is zero-indexed.

It's maybe me but I'm confused why for people ask for clarification got downvotes... pretty weird you know.

и не поспоришь

(deleted)

Из серии: "Хочу поблагодарить MikeMirzayanov за то, что создал систему codeforces, и дал нам всем возможность решать задачи и контесты."

Это еще не скоро) А преждевременная оптимизация — зло, так что не паримся :)

i think next contests will be 277.6 ... too!!:D
277.5--277.6--277.7--277.8--277.9--277.95-- .... :D

I thought Mike involved in the preparation, no?

Or did you mean Mr. Mike MikeMirzayanov Mirzayanov

totally agree with you...... meanwhile my friends made a cake having the text "Happy Birthday RED_BACK" in my last birthday..... :P

That also mean we have more chance to choose.

Чтобы не переименовывать 278, например

xdd, the same as "tourist wiped the dust from keyboard and got Accepted on A,B,C div 1"

are you sure that registration is open ?

Vote -1 to make this comment more interesting)

Your idea is too old :P See here

Рамка как рамка, почему вам не нравится?

Ага! Я бы даже сказал: ностальгические...

I solved using a dp.

The states where dp[amount of columns that needs 2 '1'][amount of columns that need 1 '1'].

The transitions would be picking 2 of these columns (out of all the possible ones) for each row.

I hope it gets accepted.

I did it in O(N^3) with DP[row][col1][col2], where col1 and col2 is number of columns with 1/2 remaining cells to choose. When you are adding new row, you may either choose 2 columns with 1 cell left and move to DP[row+1][col1-2][col2], choose 2 columns with 2 cells left and move to DP[row+1][col1+2][col2-2], or choose 1 column with 1 and 1 with 2, moving to DP[row+1][col1][col2-1].

My first implementation was a bit messy and it was challenged, but after adding some prunings it looks fast enough.

Also wondering

I tried to enumerate every pair of vertices (B, D) and calculate the number of diamonds (assuming these two are the middle vertices of a diamond). Intersecting their parents and their children, I obtained the number of possible vertices (A, C) that could form a diamond. Also intersecting these two sets, I obtained the number of "repeated" vertices that are both parents and children of A and B, and thus can't form a diamond with itself. And add to the answer the value (parents * children — their intersection).

But this approach gave TLE

For each possible (end of diamond v; source of diamond u) we can count the number of paths of length 2 from u to v.

Let us define cnt[v][u] as the number of different paths of length 2 from u to v. We run the following loop:

1. For x in [1;n] {x is a possible middle point of the diamond}
2. • For v in children[x]:
3. • • For u in parents[x]:
4. • • • If u ≠ v:
5. • • • • cnt[v][u] +  + 

Now we can easily obtain the answer:

There's a simple O(N^2) solution (N^2 is an upper bound, actually it is faster I think):

• For every node i, do a dfs (max depth 2) using i as root

• During dfs, for every node j that you reach using 2 edges, update cnt[j] (where cnt[j] is the number of ways to reach j using 2 edges) PS: clearly you stop dfs when you use 2 edges

• At the end of the dfs, iterate from node 1 to N and for every node j update result in this way:

  1. if cnt[j] < 2, do nothing
  1. else: ris += (cnt[j] * (cnt[j]-1))/2 --> This is a "reduct" form of binomial coefficient (I want to consider all rhombs starting to i and ending at j, so I can take all combination of 2 intermediate nodes)

At the end of the whole process you'll obtain the answer :)

I solved D using pascal triangle and a dfs of depth 2 for each node.

The hacking case on B for me was: 2 2 3 2 2 1

Some people did not sort the arrays, and the solution like this was enough to pass the pretests.

About D,you can try to use Brute Force. :)