dario2994's blog

By dario2994, history, 13 months ago, In English

The Southwestern Europe Regional Contest will take place on the 19th of February in Milan. It is the ICPC regional contest (i.e., the winning teams will advance to the ICPC World Finals) for teams from France, Israel, Italy, Portugal, Spain, and Switzerland.

The mirror contest SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) will be held on Codeforces at Feb/19/2023 14:05 (Moscow time) and will last 5 hours.

The mirror contest will contain the problems from the official competition plus some additional problems.

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

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 div2A to div1F; so anyone can find something at their level.

Many teams with little experience participate in SWERC, so the problem set should be enjoyable also for div2 contestants. On the other hand, solving all the problems should be challenging even for the strongest teams in the world: the MIT team did not AK in 5 hours.

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!

We uploaded the editorial of the contest (you can find it at https://codeforces.com/contest/1776, among the contest materials).

The solution to problem N submitted in the mirror contest by the team Let it rot is a quadratic solution which they managed to squeeze in the time limit. This was not the expected solution. So, morally, this problem is still unsolved! In the next days I might decrease the time limit. We have a solution which gets AC in less than one second but we wanted to be generous with the time limit. It turns out, we were too generous.

Congratulations to all the participants of the onsite contest and in particular to the three teams solving 11 problems:

  1. ENS Ulm 1 -- École Normale Supérieure de Paris
  2. gETHyped -- ETH Zürich
  3. P+P+P -- Harbour.Space University
  • Vote: I like it
  • +351
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
Rev. 2   Vote: I like it +83 Vote: I do not like it

I wonder whether there ever will be a swerc problemset that MIT team can AK

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder whether there ever will be a swerc problemset that MIT and THU team can AK

»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

good luck everyone!

»
13 months ago, # |
  Vote: I like it -43 Vote: I do not like it

I hope that the round will be good and we will score a lot of points

»
13 months ago, # |
  Vote: I like it +20 Vote: I do not like it

thanks to problemsetters for the contest! I think J is a nice problem

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

Not able to view solutions , please check the bug

»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem B, G seem cool. Surely gonna learn something from them. Btw, how to approach problem B?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    hint 1
»
13 months ago, # |
  Vote: I like it +62 Vote: I do not like it

Pretty nice contest, but a lot of the problems could be solved by making wild guesses and getting proof by AC.

»
13 months ago, # |
  Vote: I like it +162 Vote: I do not like it

Thanks for the contest, the problemset is wonderful! By the way, I hate problems with real numbers.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    How is it humanly possible to solve B in 9min 😨

»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve K?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I used log-exp trick, though get WA on test 21

  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    we want to compute first 250 coefficents of ((1+x/1)*(1+x/2)*...*(1+x/(n-1))/n with good precision

    we will compute log and then exp

    when we will compute log we must compute sum of inverse kth degrees from 1 to n-1

    if k=1 it is bruteforce for n<=1e5, otherwise it is log((n-1))+lambda+1/(2*1.0*(n-1))+(1/(12*(n-1)*(n-1)))+o(1/n^2) from https://en.wikipedia.org/wiki/Harmonic_number (i don't know, in Russian version of wikipedia it is +1/(12n^2) in English it is -1/(12n^2)...).

    if k>=2 it is 1+1/2^2+...+1/c^2+1/(c+0.5)-1/(n-0.5)+O(1/c^3) (c is 100000)

    if k>=3 bruteforce

    then exp, luckily it passes

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Reformulate the problem, now each guy has number $$$n$$$ and each second does $$$n \to \text{rand}\pmod{n}$$$, whoever reaches $$$0$$$ first wins.

    Our solution: almost surely the winner is determined in $$$K$$$ seconds, say, $$$K=200$$$. Let's calculate $$$f(n, k)$$$ being the probability that we reach $$$0$$$ in exactly $$$k$$$ seconds.

    Denote by $$$e_k(x_1, \ldots, x_m)$$$ the sum of all $$$k$$$-products of numbers $$$(x_1, \ldots, x_m)$$$. Then $$$f(n, k) = e_{k-1}(1/1, \ldots, 1/(n-1))/n$$$ (exercise for the reader). We can calculate this if we know all respective $$$p_k(1/1, \ldots, 1/(n-1))$$$, where $$$p_k(x_1, \ldots, x_n) = \sum x_i^k$$$.

    I cannot say how to do it numerically correctly as I didn't get AC.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can calculate sums of such type using https://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula

»
13 months ago, # |
  Vote: I like it +42 Vote: I do not like it

How to solve D?

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    It can be solved using greedy.

    Claim 1: It is optimal to use the computer as soon as we can.

    Claim 2: It is not optimal to just let a contestant sit idly. Our priority would be to minimize this as much as possible after ensuring the first claim.

    Let's say, some contestant just finished solving some task using the computer at $$$X$$$ time unit. Now find the minimum $$$i$$$, such that some contestant can finish solving a problem at $$$(X+i)$$$ time unit using the computer. If you can't find any, no more problems can be solved.

    Also, define $$$F_j$$$ = the time unit when $$$j$$$ th contestant gets free

    There could be more than one contestant, who can finish solving a problem at $$$(X+i)$$$ time unit. Among them, we pick someone such that his idleness period is minimized. More formally, among them, $$$j$$$ th contestant,

    $$$~~~~~~~~~~G_j=X+i-F_j-\text{time required to solve the problem}$$$

    Pick the contestant with minimum $$$G_j$$$.

    If again, more than one contestant has the same $$$G_j$$$ pick the one who has the minimum $$$F_j$$$.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    .

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

where can i find the official scoreboard ?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How To solve Problem H(Beppa and SwerChat ) please?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint1
    Solution
    Proof of solution
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the problems even though they were hard for me (⁠ ⁠≧⁠Д⁠≦⁠). Can someone give me a hint for problem F?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If there's a vertex u with degree <n-1, then we can divide edges into (u, v) and (v, w) 2 kinds (v, w!=u). Otherwise the graph is complete graph, we need to devides into 3 kinds: (1, 2), (u, 2) (u!=1) and (u, v) (otherwise).

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

    Thanks bcollet and YocyCraft for the help

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E,N ?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong with this submission? Seems to work fine for first 3 tests, but in the 4th case, it's TLE for no apparent reason.

Link to my submission: https://codeforces.com/contest/1776/submission/194236734

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    java.util.Scanner is extremely slow when dealing massive input. Maybe you can try to use java.io.BufferedReader instead.

»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Will contest with official problems with same exact order from onsite be uploaded to gym?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem D, initially I didn't get the constraint that right bounds of all the intervals should be different and solved the problem for that! I guess the problem would be much more interesting without that constraint.

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

Uploaded the editorial, see the announcement.

»
13 months ago, # |
  Vote: I like it -13 Vote: I do not like it

participated as individual,solved 3 simple problems and ranked 634

»
13 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Maybe on a separate topic, how does one make sure (as a problem-setter) that they guarantee the absolute or relative error in the statement for problems involving floating point arithmetic? (especially when the "true" answer $$$ans_{truth}$$$ cannot be expressed with infinite precision)

Do they allow a greater gap between $$$ans_{judge}$$$ and $$$ans_{contestant}$$$ (say, $$$2 \epsilon$$$) and hope/prove that $$$ans_{judge}$$$ and $$$ans_{truth}$$$ are at most $$$\epsilon$$$ apart from each other?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    In my experience, in most problems requiring some care with floating point precision it is very hard/impossible to prove that the official solution is accurate enough.

    Here is a list of not-so-deep things that can mitigate the risk of having a wrong official solution.

    1. Implement different solutions performing the operations differently. If they agree (to the desired precision), then it is likely that they are both accurate enough.
    2. If replacing doubles with long doubles does not change the result (to the desired precision), then it is likely that the solution is accurate enough.
    3. If you ask for precision $$$\epsilon$$$, make sure that your solutions have precision $$$\epsilon/10$$$ or better.
    4. If you ask for precision $$$\epsilon$$$, consider enforcing only precision $$$1.1\epsilon$$$.

    This is just my take on the matter, if other problem setters have different ideas, I am curious to read them.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +70 Vote: I do not like it

      I completely agree with those points, but I wonder what happens in contests with hacks, like normal CF rounds. We can't afford to allow bigger error, as then some hacks that should have succeeded would fail?

»
13 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

in G we have accepted (194321886) that checks x = maxsum, x = leftmost sum, x = rightmost sum, and then try random x.

it is math magic or tests are not strong?

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

    Maybe I am not understanding, x = maxsum is the solution.

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

      yes)) our maxsum == all sum, not on segment of length n

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

    In your submission, you wrote:

    int maxseg = pref.back();
    for(int x : {x1, x2, maxseg}) {
      // check each one
    }
    

    Here maxseg is actually storing the total number of Ws in the string, right? Or am I missing something in your template? From your comment I assumed that by maxseg you meant the maximum number of Ws in a segment of length n, in which case maxseg always works (as in the editorial).

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

      yes, maxseg is whole sum, but anyway my question is actual :)

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Your randomized solution is actually quite clever and educational. You didn't just randomly pick any $$$x$$$ from $$$[0 \dots 2n-1]$$$, you randomly picked a segment and set $$$x$$$ as that segment's sum. This way you're not wasting time on some $$$x$$$ that doesn't even occur in the array. Nice solution! I'll try to find a proof for why it works so fast, but I doubt my math skill would be up to the task. Although, I'm also convinced that the number of occurrences of good $$$x$$$'s probably always significantly outweighs the occurrences of bad ones and the randomized solution should stumble upon one such good $$$x$$$ soon enough.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the onsite contest be pushed to the Gym?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem I has weak cases. Some overflowing solutions still give Accepted.

»
13 months ago, # |
Rev. 2   Vote: I like it +123 Vote: I do not like it

Hi! I'm not used to speak confidently in english so I couldn't say it directly during the SWERC, but I really wanted to thank Dariost for his amazing dedication and the whole organizing team.

In particular, as a problemsetter myself, I was extremely impressed by the quality of the problemset. So kudos to dario2994, cip999 and all judges for each one of these wonderful problems (and the balance between them as a whole set).

To be honest, after IOI 2019, I thought ICPC would be boring and my competitive programming career would end. SWERC 2021-2022 (with Ulm 3) and 2022-2023 (with Ulm 1) proved my wrong and gave me unforgettable memories. So once again, thanks to all the people who made this possible!

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Out of curiosity, what rating would you expect of problem B from the official contest ? I guess around 1600-1800 ?

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

My English sucks... Any short proof for Problem J?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Here is my summary of the proof:

    Vertices from $$$G_k$$$ can be written as $$$(u, b)$$$, where $$$u$$$ is a vertex from $$$G$$$ and $$$b$$$ is a length-$$$k$$$ bitstring.

    The edges in $$$G_k$$$ between copies of a vertex $$$v$$$ from $$$G$$$ form an hypercube graph.

    Let $$${u, v}$$$ be an edge from $$$G$$$. Consider a vertex $$$(u, b)$$$ from $$$G_k$$$, where $$$b$$$ is a length-$$$k$$$ bitstring.

    • if $$$u$$$ and $$$v$$$ have same color, $$$(u, b)$$$ is connected to $$$(v, b)$$$ (proof intuition: we always connect the same copies)

    • if $$$u$$$ and $$$v$$$ have different colors, $$$(u, b)$$$ is connected to $$$(v, \overline{b})$$$, where $$$\overline{b}$$$ is the bitwise negation of $$$b$$$ (proof intuition: we always connect to the different copy)

    Call a path in $$$G$$$ even (odd) if the number of multicolored edges it uses is even (odd), i.e. the number of times it walks to a vertex of a different color from the previous one

    The length of the shortest path between $$$(u, b_u)$$$ and $$$(v, b_v)$$$ is given by the shortest of the following:

    • The length of the shortest even path between $$$u$$$ and $$$v$$$ plus $$$\Delta(b_u, b_v)$$$, where $$$\Delta(\cdot, \cdot)$$$ is Hamming distance (proof intuition: go from $$$u$$$ to $$$v$$$ following an odd path and then take the shortest path in the hypercube graph, which is the Hamming distance)

    • The length of the shortest odd path between $$$u$$$ and $$$v$$$ plus $$$\Delta(b_u, \overline{b_v})$$$

    If the diameter is between $$$(u, b_u)$$$ and $$$(v, b_v)$$$ then there is another diameter between $$$(u, {\tt 00 \ldots 0})$$$ and $$$(v, b_v')$$$, for some $$$b_v'$$$ (proof intuition: the graph is symmetric, so "translate" this path to start in $$$(u, {\tt 00 \ldots 0})$$$).

    The distance between $$$(u, {\tt 00 \ldots 0})$$$ and $$$(v, b)$$$ for some $$$b$$$, is either the "shortest even path between $$$u$$$ and $$$v$$$" plus $$$|b|$$$, or "shortest odd path between $$$u$$$ and $$$v$$$" plus $$$k - |b|$$$ (proof intuition: either take an even path between $$$v$$$ and $$$u$$$ and then go from $$$b$$$ to zeros in the hypercube, or take an odd path between $$$v$$$ and $$$u$$$ and then go from $$$\overline{b}$$$ to zeros in the hypercube).

    The algorithm can now be described by: for all pairs of vertices in $$$G$$$, $$$u$$$ and $$$v$$$, compute maximum over $$$0 \leq x \leq k$$$ of minimum between "shortest even path between $$$u$$$ and $$$v$$$" plus $$$x$$$, and "shortest odd path between $$$u$$$ and $$$v$$$" plus $$$k - x$$$. You can compute these even/odd paths with a BFS, so this is $$$O(nm + n^2k)$$$.

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

I have reduced the TL of count-permutations to 5 seconds (without rejudging existing submissions). We have a solution which needs < 0.5s, but we want to be generous. Hopefully it is not possible anymore to get AC with super-fast quadratic solutions.

I invite strong contestants to give it a try, I believe it showcases an original idea.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem G's pretty nice, love it!!!

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

    can you help me understand the proof?

    I read the tutorial but didn't understand why Ll or Rr will be >= n

    like in this example for n = 4

    WRRRWRR

    x = 1

    if we took the interval [1,4] and check for r=5 Rr(the shortest interval ending with r) will be equal to 1 which is smaller than n

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best problemset I'd ever seen

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I use java in problem h i used arraylist at first and everytime it gave me wrong test case on test case 3 but when i used a normal array it got accepted... i dk why can anybody help

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

Forget about solving I am even unable to understand editorial