Petr's blog

European Championship 2025 (EUC) Editorial
By Petr, 26 hours ago, In English
Open
Open
Open
Open
Open
Open
Open
Open
Open
Open
Open
  • Vote: I like it
  • +65
  • Vote: I do not like it

»
25 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
24 hours ago, # |
  Vote: I like it +29 Vote: I do not like it

E is, supposedly, well known in romania

→ Reply
  • »
    »
    24 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Right, we understood it very early in the mirror and it became a bit of a meme among the judges :D But, we could not really find the source so thanks for sharing. Could you also tell us where the problem appeared? I could not understand it immediately from the link.

    We were lucky, because among the Romanian teams participating to the onsite, none sent a submission.

    → Reply
»
24 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
23 hours ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Ohhhhh, super cool that it can be done in $$$O(n/\log n)$$$. This Erdos guy must be strong!

    We knew about the fact it could be done with $$$O(n)$$$ voters, but we thought it would make the problem harder without really making it more interesting.

    → Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I think an easier way to get to $$$O(n)$$$ votes (specifically, $$$2n$$$) is to just color the edges of the graph with $$$n$$$ colors (according to $$$(a+b)\pmod n$$$), and then for each color process all the edges of that color simultaneously.

    308721319

    → Reply
»
20 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    19 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know about a paper on the problem (linked from the wiki page about Huffman) but I don't know an $$$O(n^2)$$$ solution. Do you have a reference?

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I have used ide one so it may be the reason for coinciding the solution

→ Reply