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. :)

no...it was so good for me

I had some problems at the end of the contest, but other than that it went smoothly.

yep. My hack, which I did about 1 min before the end, wasn't sent to server =((((

Let's use binary search to find best possible ratio. When you fixed ratio R, then you know that for total picturesqueness of X you can take no more than R*X total frustration. So for every point you can calculate dist[i] which is equal to best possible difference between F(frustration that you have taken) and R*X. If dist[n] is not positive — it means that you can make ratio no more than R, because you found path with F<=R*X. Otherwise smallest possible ratio is larger than R.

I probably never going to become candidate master((

If you have four numbers 2 in the list, it means there are 4 ways to get to vertex 2 right?

If that is so, you should pair only these ways (every pair of ways to a vertex will generate a diamond). So you should count how many times each number repeats and calculate the how many pairs you can form with 'count' elements (c*(c-1)/2).

OMG!! I was kinda lazy to solve it but I never imagined there will be someone who would do THIS!! XD

Java заставляет делать очень много кода на ввод-вывод. с++ный cin и cout выглядят куда приятнее.

С временем трюк хитрый! :D

А вот мне никто не пишет ='(

troll mode ON :D

You shouldn't allocate such large arrays on stack. Place it outside the function to make it statically allocated.

In Ubuntu x64 the typical stack limit is 8192KB. You can query and modify it with ulimit -s. However, in Codeforces, stack limit is even larger than memory limit of most problems so stack overflow can't happen at all.

I know that you feel...

What a pity! :(

You may try N^3/32 solution. Generate bitsets of ingoing and outgoing edges for every vertex. Fix 2 vertices B and D (this gives us N^2), and count number of rhombi for this pair. To count this number, you should count number of valid A's for it (using bitsets of ingoing edges for B and D, you can make it in N/32 by taking blocks of 32 vertices from both bitsets and counting 1's in bitwise AND of these blocks) and number of valid C's for it (same idea, but with outgoing edges). Add the product of received results to the answer, and don't forget to substract invalid rhombi with A==C (to count them you should make same AND trick with all 4 bitsets at the same time).

Why do you think it would TLE? n is small (<= 3000), so n^2 is good enough.