Think about it this way. For your condition tu hold, the value n must within the last K positions. And you can choose the following values in ways, where is length of the suffix starting in value n. Then you have to multiply by the number of good permutations of size . That is, . This is exactly the same as choosing a cycle for element n of size at most K, and then multiplying by the number of good permutations for the remaining elements.

I'm not sure if I understood what you mean by counter test. It's true that the permutation you show should be counted as good for the problem statement, but it does not comply with the condition you mentioned.

Well, yes. It is mentioned in the editorial as well. For any two components A and B, take any vertexes and . Since it is always true that u can beat v, or v can beat u, there are no incomparable components.

Indeed, we can have that situation. The important thing to see, is that the partially ordered set induced by the condensation is in fact a total order. We can call that a chain (or path, as he did).

I don't understand how the tree is built. How would it look like for yzzyz?

Well, I agree that my writing wasn't super clear.

The idea is to prove by induction in k that if 1 + 2 + ... + k ≤ n < 1 + 2 + ... + (n + 1), then the Grundy number of a position with n stones where the moves 1, 2, ..., k are allowed is exactly k. The set X' was used to show that other moves might be allowed as well, it is irrelevant.

It is not true that Grundy(n, X) = k(n) for any X.

I think I got a reasonable proof:

First, from the definition of Grundy number (as a minimum excluded) it is not hard to see that for a state s such that Grundy(s) = k there must be a path s = s_k → s_k - 1 → ... → s₁ → s₀ where Grundy(s_i) = i. Since the number of stones taken in each step must be different, you have an upper bound for Grundy(n), namely the largest k such that 1 + 2 + ... + k ≤ n. Below, I will denote this k as k(n).

It is possible to prove equality by induction. Our states will be of the form (n, X) where n is the number of stones and X is the allowed moves (a set of integers) and the inductive hypothesis will be that for any state , Grundy(s) = k(n). You can verify that the base case is true, and for any k' < k(n) it is possible to reach a state with k' = k(n'). This implies that Grundy(s) ≥ k(n) and together with the previous upper bound proves equality.

I don't understand your proof of j being the Grundy number. Taking your example, if you have a pile of 10 and remove 5 you get a pile of 5 and you are allowed to take 1, 2, 3, 4 from it.

How is that equivalent to removing 2 and 3 from {1, 2, 3, 4}? I mean, in that case you would get {1, 4} and you could remove 1, 4 or 5 stones from it. Am I missing something?

Yes, you are right, it's not exactly tree isomorphism. Now, I wonder if an adaptation of that algorithm is possible.

What about putting all elements of A (with multiplicity) in a binary trie, do the same with elements of B and then doing tree isomorphism?

You can use two pointers to achieve O(N)

Team from Argentina:

1. Román Castellarin ponysalvaje
2. Maximiliano Redigonda mredigonda
3. Gianni Weinand Weheineman
4. Gastón Fontenla (First Participation) gfonn

I just read the abstract of this paper.

And m = 1 is a special case to be considered apart.

Okay. Sorry for mixing things up. I was definitely mistaken. Don't know how I came up with that, I was sure I had read it somewhere.

Yes, it seems they changed that. I think this a much more reasonable policy. But there should have been a notification about this (I searched and didn't find it anywhere).

I think it's clear he wasn't happy with his perfomance and he "hacked himselft out of the contest". If you have negative score, the contest is unrated for you, or at least it used to be that way.

I had the same problem. Then I tried replacing the option lang=en to lang=ru in the URL, and registration page appeared.

Since I don't understand Russian, I switched back to English and it was still working.

Yes, same thing happened to me.

I use Codeprocessor with FileEdit and TZTester to generate template code, class and testing code and it works. You can find them here.

Think of the distinct projects as vectors p_i = (a_i, b_i). On time t you can reach any of the points t·p_i, but you can also reach any convex combination of them. The points that can be obtained as a convex combination of a certain set of points is the convex hull of that set.

If you take into account that, whenever is possible to reach (x, y) you can also reach any (x', y') such that 0 ≤ x' ≤ x and 0 ≤ y' ≤ y (that is the rectangle with corners in (0, 0) and (x, y)). You also need to add (0, 0), (0, max_y) and (max_x, 0) to the set {t·p_i}_{1 ≤ i ≤ n}. The set of points reachable on time t will be those contained in the convex hull. You can do binary search or some vector calculations to find out what is the minimal t such that the target point lies inside it.

Hope it's clear.