I have a probabilistic solution for Problem A (optimised) https://mirror.codeforces.com/contest/2068/submission/308681793

E is, supposedly, well known in romania

H when the distances are the same. https://atcoder.jp/contests/abc135/tasks/abc135_e

Btw A can be solved with $$$4n - 7$$$ votes: 308693499.

This can be proven inductively. WLOG, assume $$$m = \binom{n}{2}$$$. The $$$n=2$$$ case is trivial. For $$$n \ge 3$$$, from the inductive hypothesis, say we have a set $$$V$$$ of $$$4n - 11$$$ votes getting the desired facts concerning only the candidates $$$1, 2, \ldots n-1$$$. Now, let $$$S$$$ be the set of candidates who we want to beat $$$n$$$ and $$$T$$$ be the set of candidates who we want to be beaten by $$$n$$$. Let $$$\sigma_S$$$ be any ordering of $$$S$$$ and $$$\sigma_T$$$ be any ordering of $$$T$$$. For $$$2n-6$$$ of the votes from $$$V$$$, make $$$n$$$ the most preferred candidate, and for the remaining $$$2n-5$$$ votes, make $$$n$$$ the least preferred candidate (keeping their ranking among $$${1, 2, \ldots n-1}$$$ the same). Let $$$\hat{\sigma_S}, \hat{\sigma_T}$$$ denote the reverse of $$$\sigma_S, \sigma_T$$$ respectively.

Now, we add four more votes, with the following rankings:

1. $$$\sigma_S, n, \sigma_T$$$
2. $$$\hat{\sigma_S}, n, \hat{\sigma_T}$$$
3. $$$\sigma_T, \sigma_S, n$$$
4. $$$n, \hat{\sigma_T}, \hat{\sigma_S}$$$

Intersetingly, $$$O(n/ \log{n})$$$ votes suffice and are asymptotically optimal.

Interestingly, I came up with pretty much same problem as D. Morse Code for another contest some years ago, it got rejected (reason: it appeared in some shortlist very long time ago, $$$O(N^4)$$$ intended solution IIRC)

Later I discovered $$$O(N^2)$$$ solution in a paper.

I have two solutions for K: the one we didn't believe in during the onsite (passing in 1930ms on CF) and the one that I think more or less matches the intended:

AC 1900ms: Kuhn on graph where left part has numbers we are matching to ($$$a[i] \cdot j$$$), right part is $$$i$$$. We build $$$O(n^2)$$$ edges in $$$O(n^2\log)$$$ (or with hashtable lookup, but it seems sorting would be faster). Then Kuhn with 2 default optimizations: timer-based used[v] for O(1) clear on each successful path found, and shuffle(all(g[v]), rng) so we don't go too often into the same vertex and hopefully find a free index to pair with in first elements of adjacency list. Overall it should be $$$O(n^3)$$$ as we have $$$n$$$ vertices and $$$n^2$$$ edges, but in reality $$$n^2\log$$$ construction part took most of the time in my TL upsolving attempts. 308915147

AC 1300ms: on failed path push, remove all future and existing edges to right-part vertices that we failed to propagate the path from. Each time we fail we watched X edges and we remove more than X edges, and we succeeded $$$n$$$ times so it's more or less clear why it's $$$O(nE)$$$ and it's also fast because most of successful steps require much less than $$$E$$$ for dfs. Here $$$E$$$ should be something close to $$$O(n\log n)$$$ as this is pretty close to the jury's solution (though it is done a bit backwards). 308914819

Is it supposed to be this way? The gap between two solutions in terms of how hard it is to come up with is pretty big. The first one really just squeezes in TL tightly. The second one is not so fast itself. Was it the same experience for the onsite participants with 5+ attempts?

Would appreciate some comments in general as well. I am thinking a lot now on this "remove edges for not-pushed vertices" optimization and how useful it could be in other problems

there is O((n+m) log (n+m)) solution in E if we consider edges not in the BFS traversal as taking the minimum along vertical paths and update all of them offline using binary lifting.

Why is $$$E = O(n \log n)$$$ in problem K?

In the editorial for problem E, in the part for "Computing f assuming we know g" it says:

Set $$$f[n]=0$$$ and $$$f[v]=g(v)$$$ for all other $$$v$$$. Now process each vertex in the following way. Pick the unprocessed vertex $$$v$$$ with the lowest current value of $$$f[v]$$$. Process $$$v$$$ by iterating through all vertices $$$u$$$ adjacent to $$$v$$$ and setting $$$f[v]=max(g[v],min(1+f[u]))$$$.

I don't think this works on the first sample.

The procedure would do the following:

1. Initialize $$$f$$$ as $$$f[1] = 3, f[2] = 4, f[3] = 3, f[4] = 4, f[5] = 0$$$

2. Pick $$$v = 5$$$ and set $$$f[5] = max(g[5], min(1 + f[2], 1 + f[4])) = 5$$$

3. Pick $$$v = 1$$$ and set $$$f[1] = max(g[1], min(1 + f[2], 1 + f[3])) = 4$$$

4. ...

But the correct answer of f[1] should be 5. Am I misunderstanding something?

I got AC by modifying the procedure to

E is a really beautiful problem, thank you! I found an easier way to calculate $$$g(v)$$$ that doesn't need DSU or the lazy propagator (though I don't understand what exactly it does in the editorial).

If we want to use a non-tree edge $$$(u,v)$$$ at some node $$$w$$$, then exactly one of $$$u$$$ and $$$v$$$ must be in the subtree of $$$w$$$, which is equivalent to saying that $$$w$$$ is in the subtree of $$$lca(u,v)$$$, but is not the LCA itself, and at least one of $$$u$$$ and $$$v$$$ is in $$$w$$$'s subtree. If we denote by $$$level[]$$$ the distance to $$$n$$$, then the path using the non-tree edge $$$(u,v)$$$ from $$$w$$$ will have length $$$level[u] + level[v] + 1 - level[w]$$$. Now we can store the pair $$$(level[u] + level[v] + 1, edge-index)$$$ in the sets for both $$$u$$$ and $$$v$$$. Just like in the editorial, we calculate the $$$g(v)$$$ using DFS, doing smaller-into-larger merging. When merging, if $$$(value, index)$$$ is already contained in the other set, it means we are at the LCA, so we delete it instead, otherwise we insert it. After processing all children, $$$g(v)$$$ will be the minimum in $$$v$$$'s set minus $$$level[v]$$$.

Implementation

Could someone explain Problem H to me more clearly,I cannot understand the editorial very well,very please

Can someone explain the dp solution for problem J used in this Submission

What's up with the checker of problem I?

I have some submission 317737217 (which still has some bugs), but to me the output of the program seems clearly correct on the third testcase (remove the wall above the start immediately and roll the bar towards it).

Why is it graded as "Wrong answer Ball did not escape"?

pinging bicsi