"The contestants will be able to receive full feedback on a limited number of submissions per task."

Can you give more details about this? Sounds like a new feature. How many submissions are allowed per task, and how many of those can get full feedback?

I think the registration link is not correct.

Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).

It's April 14th, right?

Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).

Reminder: less than 50 minutes to start

Is it open to discussion now?

Can anyone explain me the solution of problem "Tenis" ? :((

Would any kind user mind posting 2-3 sentences / code for their solutions? It would be very much appreciated, thank you!

Hi all, here are brief descriptions of the solutions.

Segway (author: satja)

Let's call any moment when a racer reaches an accelerator (using it or not) an event. We will process events in chronological order using a set. For every accelerator we store the number of racers who have already passed its beginning. Total complexity $$$O(NM \log(NM))$$$

Ljepotica (author: ipaljak)

Let $$$f(X)$$$ denote the sum for all valid sequences less than or equal to $$$X$$$. We need to calculate $$$f(B) - f(A-1)$$$. We will calculate $$$f(X)$$$ using dynamic programming. Our state is the following $$$(i, k, smaller, last)$$$ with the following meaning: the current position (i.e. depth in the tree), the number of times Ena changed her opinion about what left means, whether the constructed prefix is already smaller than $$$X$$$ and current Ena's opinion on what left means. Total complexity $$$O(NK)$$$.

Izlet (author DBradac)

Let $$$f(u, v)$$$ denote the number of different colors on the path from $$$u$$$ to $$$v$$$. Clearly $$$f(u, u) = 1$$$ and $$$f(u, v) = f(v, u)$$$. Let 1-comp denote a maximum (i.e. cannot be extended) set of nodes which all have $$$f(u, v) = 1$$$. These can be found using a dfs and they surely form a connected subtree of the original tree. For every 1-comp we will choose one node, connect all the others directly to it and ignore them from now.

Suppose now that for every $$$u \neq v$$$ we have $$$f(u, v) \geq 2$$$. Define a 2-comp as a maximum set of nodes which all have $$$f(u, v) = 2$$$ for $$$u \neq v$$$. These can be found quickly in the following manner. Find a pair of nodes $$$(a, b)$$$ such that $$$f(a, b) = 2$$$ and there is no 2-comp already found containing both of them. Add to the 2-comp all nodes $$$c$$$ such that $$$f(a, c) = f(b, c) = 2$$$. It's easy to see this is a maximum 2-comp. Also, note that a 2-comp forms a connected subtree of the original tree.

Any two different 2-comps can have at most one node in common. Suppose the contrary, since they are both connected subtrees, they must share an edge and therefore have the same two colors. So, they are actually the same 2-comp.

Now we can connect the nodes in each 2-comp arbitrarily as long as they form a connected subtree.

Once we have constructed the tree, finding a valid coloring is easy. Run a dfs/bfs. When choosing the color of a new node $$$v$$$, run dfs from it through all the nodes colored so far. When the number of distinct colors doesn't increase, we have found a node with the same color as $$$v$$$. If we haven't found any, color $$$v$$$ with a new color. Total complexity $$$O(n^2)$$$.

Using induction we can prove the correctness of the algorithm, i.e. that we can connect every 1-comp and every 2-comp arbitrarily.

Tenis DBradac

Claim 1: It's easy to see that if $$$x$$$ can win a tournament and $$$y$$$ can beat $$$x$$$, then $$$y$$$ can also win a tournament.

Let $$$S$$$ denote the set of players that can win a tournament. Also let $$$T$$$ denote the minimum nonempty set of players such that no player not in $$$T$$$ can beat a player in $$$T$$$. We claim that $$$S = T$$$.

First we show that $$$S \subseteq T$$$. By definition of $$$T$$$, no player outside $$$T$$$ can win the tournament.

By claim 1 we have that no player outside $$$S$$$ can beat a player in $$$S$$$. By definition of $$$T$$$ we have $$$|T| \leq |S|$$$. Suppose that there exists $$$x \in T, x \not\in S$$$. Since $$$|T| \leq |S|$$$, there is $$$y \in S, y \not\in T$$$. By defintion of $$$T$$$, $$$y$$$ can not beat $$$x$$$, so $$$x$$$ can beat $$$y$$$. But then by Claim 1, $$$x \in S$$$ which is a contradiction. We have $$$T \subseteq S$$$ and therefore $$$S = T$$$.

Let $$$M(p)$$$ be the maximum rank of a player $$$p$$$ among all surfaces. Let $$$C(k)$$$ be the number of players $$$p$$$ with $$$M(p) \leq k$$$. It's easy to see that $$$C(k) \leq k$$$. Let $$$t$$$ be the minimum number such that $$$C(k) = k$$$. Then $$$T$$$ is the set of all players $$$p$$$ with $$$M(p) \leq t$$$. Let $$$D(k) := k - C(k)$$$. Finding $$$t$$$ corresponds to finding the first zero value in a nonnegative array of values $$$D$$$. Each update changes only two values of $$$M(p)$$$ so we can use a segment tree to manage these updates efficiently. Total complexity $$$O(N + Q \log N)$$$.