very nice problem in this round,very thanks MikeMirzayanov :)

I needed just 2 minutes for problem D T_T

My solution 8732482 of D.
I use this fact:
If A is adjacency matrix and B = A ^ k then number of different path whits length = k from u to v = B[u][v]

Also i speed up matrix multiplication using fact that we have only m '1' in matrix.

Problem D:

Start a small ( just 2 steps ) dfs ( or bfs ) from each graph vertex, count the number of ways to get from current vertex in some other ( let it be cnt[v] ). Then add cnt[v] * ( cnt[v] - 1 ) / 2 to the answer.

My Code

For problem D:

I went through all the nodes, and for each node, I choose 2 of its neighbors (I try them all), then add to the sum the common neighbors of those 2.

My Code

Here is my editorial for F:

The state of the board can be stored with three variables: The row we're on, the number of columns which have no 1s in them (call it x), and the number of columns with exactly one 1 in them (call it y). We then have the following options, depending on these counts.

For each row, we need to select two indexes to be 1s, the rest need to be zero. Here are the possible ways to do that. If x > 1, there are ways to choose two columns to insert a 1. This decreases x by two and increments y by 2.

If x ≥ 1 and y ≥ 1, then there are x·y ways to choose the two columns.

If y > 1, then there are ways to choose the two columns to insert a 1. This decreases y by 2.

Combining all of these methods together yields the right answer.

wait for F solution

Solution for E: The idea is to binary search for the best ratio. So now, this problem reduces to checking if a certain ratio is possible. Let K be the optimal ratio.

First, add a dummy node at x=0, and between every pair of nodes with x_i < x_j, add an edge with cost sqrt(|x_j-x_i-L|) — R * b_j. We will now show that if the shortest path from x=0 to x_n is negative, then we have (sum of frustrations) — R * (sum of picturesqueness) < 0, so (sum of frustrations) / (sum of picturesquness) < R. We know that K <= (sum of frustrations) / (sum of picturesquness), thus, we get that R > K. On the other hand, if the shortest path is positive, then this implies R < K. Thus, we can binary search for the optimal K. Once we've found K, we can then just do the standard dp while keeping prev pointers to reconstruct the path.

Editorial for D: What i did is a DFS but checking whether a edge is visted or not if edge is not visted. if(edge is visted ) i do nothing else what i do is dfs(current parent) and before entering the dfs i upadte all paths from let say parent to child(current) Link for Solution: Solution

My solution for D is to iterate through every possible start and stop point (a and d) and then calculate the number of b and c respectively. I made a mistake that in the O(n^2) loop, i used the memset() function to memset an O(n) array. Expected to be O(n^3) but still AC. Could anyone explain? The link to my code is below http://codeforces.me/contest/489/submission/8728972

It's a nice Round ! That helps me get more than 300 ratings ! Thanks for MikeMirzayanov !

Life of real man according to MikeMirzayanov

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if( ... )
        {
            girls[j] = 1000;
            result++;
            break;
        }

- live in O(nm), be a man

Would someone mind to share the DP solution for problem B? :)

Can anybody tell me why this code is giving TLE ??

Can someone explain why the complexity is O(mn) and not O(n^2 m) At least the j++ in the second loop does get executed n^2 times. So how can we give the argument that the second loop is only executed m times?

It is not clear to me why the total complexity for D is O(mn). Could somebody explain it to me?

Can someone give the DP solution for Problem C? Thanks :D

http://codeforces.me/contest/489/submission/19787251

I don't see why my adjacency matrix approach didn't fit in the time limit for problem D, it should takes O(n) for each new path and O(nm) in total for solving the problem, which is the same as the editorial's solution.

Could any help please? Thanks in advance, any suggestions would be appreciated. =D

in problem B.

how to apply maximum flow.

Can somebody explain BerSU Ball's recursive DP solution?

Just in case there is a harder variation of 489A — SwapSort, there is an O(n * log(n)) method (that kinda resembles using a linked list to me): 53566076

What is the complexity of D solution? I'm pretty confused it. My opinion is (n^2 +m). Is that right?

Can problem B be done Online ?

My code for C fails on case 4 not sure why... Any help would be much appreciated

https://codeforces.me/contest/489/submission/176150923

This is my solution to the D problem,
Any idea why this fails
I did it in O(nm + n^2) = O(nm)