thanks a lot it helped me a lot

Pls make codeforces great again.

You wrote terrific, but I'm not sure whether you mean terrific or terrible. Terrific also means great :|

It's not your business! You didn't even participate in that contest.

In Google.

эх, хотя бы извинился :(

Во-первых это моя задача. Во-вторых какой-то человек нашел эту задачу С который был тут 2 года назад за неделю и другие его повторили. Во-третьих, я заявку на этот раунд отправил еще в декабре прошлого года (могу доказать) и то что в течении этого года кто-то что-то подобное поставил это я должен жаловаться

Who forced you to google?

this is actually a problem on calculating the worst-case height of the AVL-Tree.

http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html

So the fibonacci pattern wasn't very intuitive to me. Hence I solved this question with a basic recurrence as described. Let us define a f(N) as minimum number of people required for a person to win N matches. If we have this, our answer is simply the greatest value of N where f(N)>=n, where n is the input, i.e. the number of people.

So, for N match wins, we need N losers, hence we add N to the answer(ret). Now we run recurrence over these losers, if we notice the number of wins required for these losers will be [0,N-2], inclusive, as only if the highest player had N-2 matches won, could he have played the winner who was at N-1, leading him to N victories. Hence we iterate over [0,N-2] and find the number of people needed for those players.

Hence we had all the losers counted, We add 1 to f(n) to get the total player count.

Here is the recursive method. Add memoization for AC.

long long f(int n){
    long long ret = n;
    for(int i = 0; i<=n-2; i++)
        ret+=f(i);
    return ret;
}

This recurrence, naturally turned out give same output as fibonacci, but it is a non-experimantal way of solving this problem. Thanks :)

Why do you think bitset problem is not a good idea? Many people regard a single 32-bit integer arithmetic as a single unit time operation. Then why not a bitset?

complexity is (n/32)^3 ~ 80^3

Actually, the Permanent of a matrix counts the number of valid permutations. However, calculating the permanent is a hard problem. But we only need the parity of the number of permutations, i.e. the parity of the permanent. For that, we can calculate the determinant of the matrix over a field of size 2 (the permanent and determinant are equal in ).

The permanent of an adjacency matrix counts the number of perfect matchings in bipartite graph of rows-columns. Since the determinant is something like a - b and permanent is a + b, they have the same parity. The number of perfect matchings in bipartite graph rows-columns is the number of vertex-disjoint covers of cycles in the original graph (every vertex will have one incoming edge and one outgoing edge). This is basically the number of valid permutations when you look at them as cycles.

Assuming we want a guy to have played n + 1 matches:

First of all, he must have played exactly n matches.

Secondly, he must have beaten someone else who had played at least n - 1 matches.

It is obvious that we want to minimize the number of matches used to maximize the answer. Therefore, we just assume that the guy that was beaten had played n - 1 matches before.

Thus the recurrence formula comes to the surface, which is F(n + 1) = F(n) + F(n - 1), where F(n) represents the number of people we need to have one guy who has played n matches.

The base case are F(0) = 1, F(1) = 2.

I send round proposal at 20th December 2015, which is earlier than August 13, 2016.

I think so, too

Actually if you are going to use big O notation, then both are wrong, correct order is O(n³). But yes you are right it should be n³ / 32, at least for most accepted solutions, have not seen author's code, but i'm pretty sure he could not reduce the outer N loop, so it would never be (n / 32)³

Maybe author's solution is O(n*2^k)?

Do you mind explaining your solution? It is particularly short and fast, but I can't understand it. Thanks!

O(n*k*k) solution: (EDIT: I think I made a mistake in the explanation for i > k) (Note: I am not good at explaining solutions, so this might not make much sense). Let us say a node q reaches a black node if for some p distance(q, p) <= k and p is black. The problem wants us to find the number of ways to color nodes such that all nodes can reach a black node.

First root the tree at any node.

dp[x][i] keeps track of info for node x, and 0 <= i <= 2*k.

If i <= k, then node x is a distance of i from the nearest black child, and all of its children can reach a black child.

If i > k, then some node in the subtree of node x is i-k-1 (<----EDIT) edges away and cannot reach a black node (there may be multiple nodes that cannot reach a black node, but it is OK to just select the farthest one, because if the farthest one is able to reach a black node in the future, then any closer ones will be able to too).

Examples: If i = 0, then node x is colored black and all of its children can reach a black node.

If i = k+1, then x cannot reach a black node, but all of its children can. (<----EDIT)

If i = 2*k, then node x is not colored black, and there is a node in the subtree of node x that is k edges away and cannot reach a black node.

At the beginning of the dfs, set dp[x][0] = 1 (this is the case when we color the node black) and dp[x][k+1] = 1 (this is the case when we don't color the case black).

During the dfs call on each child (call it j), update dp[x]. This can be done by iterating over dp[x][f] and dp[j][g] for 0 <= f, g <= 2*k.

There are 4 cases when updating. First let Y denote the union of x and the subtrees of the children that have already been visited (not including j). (For example, if there are edges 1-2, 1-3, 1-4, 1-5, then when j=4, Y = {1, subtree(2), subtree(3)}).

f<=k, g<=k: All nodes in Y and j can reach black nodes. Update nxtDP[min(f, g+1)] because that's the distance to the nearest black node.

f>k, g>k: Y and j both have a node that can't reach black nodes. Update nxtDP[max(f, g+1)] because some node max(f, g+1) edges away from x can't reach a black node.

f<=k, g>k: All nodes in Y can reach a black node, but some node in g can't. If the nodes in g that currently can't reach a black node can reach black nodes in Y, update nxtDP[f]. Otherwise update nxtDP[g+1].

Can you also share your approach?

1. The determinant of a matrix is the sum of every combination of ((-1)^inv)*(the product of all the a[i][j] chosen) where every i and j doesn't repeat itself on another chosen pair and inv is the number of inversions on the number of columns/rows chosen. This means that it has information about the sum of every possible product without repeating the same row/column inside this matrix.

2. A key observation: -1=1 on MOD 2.

3. The inverse matrix is the transpost of the matrix of the cofactors. You get the cofactor of some position i,j by excluding the row i and column j and getting the determinant of the rest of the matrix and multiplying it by (-1)^(i+j). This means that the inverse matrix has information about every cofactor. Also, because of 2, you don't need to worry about the (-1)^(i+j)

4. If you change some a[i][j] from 1 to 0, the determinant will differ by the value of the cofactor associated to it because the 1 was originally multiplying cofactor and being summed to the original determinant. Think about Laplace's formula to calculate the determinant and you will understand. Since the inverse matrix has information about every cofactor, you can use it to get every single cofactor efficiently.

This is my take on this problem, it might have some mistake but I think that's it.

Deleted