dario2994's blog

European Championship 2024 (EUC)
By dario2994, 8 months ago, In English

The European Championship 2024 will take place on the 24th of March in Prague. The top teams from the European ICPC regionals CERC, NWERC, SEERC, SWERC will compete for the title of European champions. It is the first edition of this ICPC super-regional.

The mirror contest European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) will be held on Codeforces at Mar/24/2024 13:00 (Moscow time) and will last 5 hours.

The mirror contest will contain the same problems as the official competition.

I am the chief judge for the competition and I want to thank:

  • The amazing set of judges who proposed and prepared the problems: antontrygubO_o, bicsi, Giove, Martin Kacer, MZuenni, Petr.
  • Our beloved tester ksun48 who showed us that our perception of the difficulties was not exactly spot on...
  • Our beloved proofreader Philae for proofreading the statements.
  • Everyone involved in the organization of EUC. In particular our director Boba Mannová, and Fernando Silva, Václav Herman, Ondřej Votava, Jan Kubr, Jan Baier.
  • The developers of DOMjudge, the contest system used in the official contest.
  • MikeMirzayanov for Polygon (that we used to prepare the problems) and for letting us host the mirror on Codeforces.

I invite you to participate in the contest and I hope that you will like the problems.

On the difficulty
The contest features problems with difficulties from div1A to div1E. It should be enjoyable for many, and challenging even for the strongest teams in the world.

Rules

  1. The contest is unrated, so your codeforces rating will not be affected.
  2. The scoring is ICPC-style: teams are first sorted by number of problems solved, then the time-penalty is used as a tie-break. An incorrect submission gives a 20 minutes penalty.
  3. We encourage participation as a team.
  4. If you are participating in a team, we encourage you to use only one computer for coding the solutions (as in an ICPC contest). Regarding using templates, googling, and copy-pasting code: feel free to do it.
Rationale of rule 4.

UPDATE: We hope you liked the problems!

Congratulations to the winners, and especially to the first two teams for AK:

  1. dw my perception of the difficulties was not exactly spot on: tourist, ecnerwala.
  2. xinyoudui: PubabaOnO, orzdevinwang, jqdai0815
  3. MIPT: Yolki-palki: Tikhon228, Pechalka, Kapt
  4. Captain take me!: crazy_sea, A_zjzj, 275307894a
  5. Beyond Three Wolves: Kevin114514, CrTsIr, Atomic-Jellyfish
  6. HSE: FFTilted: Kirill22, Ormlis

We uploaded the editorial of the contest.

Tune in to ICPCLive to see the closing ceremony and find out how the onsite teams did at 18:00 CET!

UPDATE 2:

Congratulations to the medalists of the onsite contest:

  1. Warsaw Eagles 2024 — University of Warsaw (the only team with 9 problems)
  2. Zagreb 1 — University of Zagreb
  3. KNU_0_GB_RAM — Taras Shevchenko National University of Kyiv
  4. ELTE 1 — Eötvös Loránd University
  5. UWr 1 — University of Wroclaw
  6. ENS Ulm 1 — École Normale Supérieure de Paris
  • Vote: I like it
  • +383
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How many problems should we expect there to be?

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Is there a ranking

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Is there has a prize for winners

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it -33 Vote: I do not like it

[deleted]

→ Reply
»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Conflict with ARC. sad

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

please share the editorial link.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why not able to see submissions :(

→ Reply
»
8 months ago, # |
  Vote: I like it +66 Vote: I do not like it

Life is so unfair... 8 problems solved... context, I really hope this situation changes next year...

→ Reply
»
8 months ago, # |
  Vote: I like it -42 Vote: I do not like it

How to solve ABCDEFGHIJK?

→ Reply
»
8 months ago, # |
  Vote: I like it +90 Vote: I do not like it

Will we ever get rid of the 'proof by accepted' problems such as this problem K? I've been waiting to hear the solution/proof of it in the problem analysis -- getting that "you should just do the thing you thought you should do and it will pass, proof by accepted, proof left as an exercise to the reader". :(

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Proof will be in editorial published on CF. I skipped it because there wouldn't be time to go over other problems if I covered it, sorry.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      It is already published!

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      Thank you, the editorial explains it perfectly and it is a nice problem overall; but a side thing I do not personally like is that I can bet that a good part of teams who have solved it have no idea (or at least didn't waste their time) to prove it. It is just something that looks like it could be a solution + seeing a number of accepted solutions what implies that the idea is correct. That might also explain a relatively large number of solves onsite versus a relatively small number of solves on the CF mirror.

      Our team came up with the same proposed idea, thought that it might work but honestly no idea whether or not it does, and we literally had a comment 'If we were onsite we'd submit this for sure, but no point in randomly trying it on a mirror'. I just personally don't like that, nothing more.

      Thanks for the reply and thanks for the fun contest overall!

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

    Idk what solution was presented in the editorial but I know how to prove my solution. There is a triangle if and only if each side has a length strictly smaller than $$$s := \sum x_i / 2$$$. Say, each side should be of length at most $$$t = floor((s-1)/2)$$$ (call a set valid if its sum is at most $$$t$$$).

    W.l.o.g. assume $$$n_a \le n_b \le n_c$$$. Then we have two conditions when the answer is no: 1. the sum of the smallest $$$n_c$$$ elements is larger than $$$t$$$. 2. the sum of the smallest $$$n_a - 1$$$ elements and the largest one is larger than $$$t$$$.

    In the first case, it is impossible to have anything smaller in set $$$C$$$, and in the second case, it is impossible to have the set containing the largest element to be any smaller.

    In all other cases, the answer is yes. We first start with the following configuration: - Set $$$A$$$ consists of $$$n_a - 1$$$ smallest elements and the largest element (let this largest element be $$$m$$$). - All other elements are distributed arbitrarily among $$$B$$$ and $$$C$$$.

    Note that due to our no-preconditions, we know that set A is already valid. If B and C are also valid, we are done. Otherwise, w.l.o.g. assume that C is invalid. Then we perform a sequence of swaps in which we step-by-step decrease the sum of elements in C while preserving the fact that B and A stay valid.

    If $$$C.max > B.min$$$, we swap C.max and B.min. It decreases the sum in C. Note that B is still valid as $$$A$$$ contains $$$m$$$, and thus $$$sum_A \ge m$$$, so $$$sum_B + C.max - B.min \le (s - sum_C - sum_A) + C.max - 1 \le (s / 2 - C.max) + C.max - 1 < s / 2$$$, where $$$C.max \le m$$$. Hence, all sets stay valid. Otherwise, if $$$C.max <= B.min$$$ and $$$C.max > A.min$$$, we swap C.max and B.min. As $$$B.min >= C.max$$$, the same arguments apply. Finally, if none of these two conditions apply, we have $$$C.max > A.min, B.min$$$. Hence, $$$C$$$ consists of $$$n_c$$$ smallest elements out of all and is still too large. It contradicts the first no-case.

    Therefore, we can always perform an operation. Note that the largest element always stays in A as we can only swap some element that is strictly smaller than $$$C.max$$$. Hence, such an operation is always applicable. Furthermore, note that $$$C.max$$$ is non-increasing, and hence when we swaped some value away, it will never come back to $$$C$$$. We derive that the number of swaps is limited by $$$n$$$. Performing these swaps is easy.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got AC on F, but I am not sure my solution has the right time complexity.

What am I doing is I iterate over the common bit of the pair and notice that now we only want to find 2 masks such that one is not a submask of the other. I am doing this by brute force ( trying 2 adjacent masks after sorting by length ). Now if I don't find a solution assume A is a submask of B, then I can discard B as a candidate for all bits that A and B share ( because for those, A is clearly better ).

Can someone try to uphack this?

→ Reply
»
8 months ago, # |
  Vote: I like it +50 Vote: I do not like it

We can't see other's submissions (codes) now, could you allow to view other submissions?

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

    I'd be more than happy to do it, but I have no idea how. Maybe you or other CF experts can advise?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      I am still confused if its a genuine question or you already know it and I am the one not getting the context here. But since no one answered it and I really want to see the implementation so I will answer it.

      Go to "Edit" and then in "Allow view other submissions to" select "Anyone"

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

        It was a genuine question. When I click "Edit" on the contest page, there is no "Allow view other submissions to" option there. Maybe I do not have enough access rights? dario2994, does it appear for you?

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

          there is a visibility option (atleast in my div1/2), maybe change that to public? (im not completely sure either btw)

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

            Visibility is already public.

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

          It should be done now (even though I did not have enough rights either)

          → Reply
»
8 months ago, # |
  Vote: I like it +19 Vote: I do not like it

tourist is winning rounds, back to top ig

→ Reply
»
8 months ago, # |
  Vote: I like it +168 Vote: I do not like it

Fuck your no flags policy

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I was so surprised to hear that. When did they introduce this policy?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Organizers just like to make up rules on the fly.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        side note: the jury was not informee about this and would have allowed the flag

        → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    I actually checked the rules and there's nothing about the flags. Have I missed something?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +56 Vote: I do not like it

      I'm not up to speed either. It's strange all around. The scoreboard has country flags but you can't show them on stage? It may even be the presenter's personal position rather than an official policy.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it +21 Vote: I do not like it

        I remember in Moscow 2020 finals our Kharkiv team (the only one though I'm not sure) brought the flag on stage, noone interfered.

        → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

    Wasn't there a blog post on codeforces a couple of weeks ago (already deleted I guess) showing multiple teams at ACPC coming with Palestinean flags on stage? wtf?

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Image How exactly does one come up with this observation? Can anyone please explain? (Question-E)

→ Reply
»
8 months ago, # |
  Vote: I like it +18 Vote: I do not like it

There was an original problem of F on luogu: https://www.luogu.com.cn/problem/P8252

→ Reply
»
8 months ago, # |
  Vote: I like it -9 Vote: I do not like it

orz

→ Reply
»
8 months ago, # |
  Vote: I like it -12 Vote: I do not like it

My rating is higher than tourist

→ Reply
»
8 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Please add editorial link in Contest materials

→ Reply
»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Listen to the language because it's always in the first person, even when talking about others

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

Didn't find any Russian team from the ranking. EUC doesn't include Russian?

→ Reply
»
8 months ago, # |
  Vote: I like it +28 Vote: I do not like it

The organisation of the event was amazing! Thank you so much!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WHEN?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. Will the test cases of the championship be published?

→ Reply
»
8 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Problem I is very similar to COCI '22 Contest 1 #3 Berilij

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

dario2994 Where is possible to download test cases ?

→ Reply
»
3 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I used centroid to solve C :) my submission: 270131979

→ Reply