### dario2994's blog

By dario2994, history, 5 weeks ago,  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 icpc, Comments (76)
 » 5 weeks ago, # | ← Rev. 2 →   I wonder whether there ever will be a swerc problemset that MIT team can AK
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   .
•  » » » lol bro
•  » » » » 4 weeks ago, # ^ | -24 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup button { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } please vote me up, thx.
 » I wonder whether there ever will be a swerc problemset that MIT and THU team can AK
•  » » Maybe yes
 » good luck everyone!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   .
 » Good luck))
 » I hope that the round will be good and we will score a lot of points
•  » » very very bad comment. Stupid
 » thanks to problemsetters for the contest! I think J is a nice problem
 » Not able to view solutions , please check the bug
 » Problem B, G seem cool. Surely gonna learn something from them. Btw, how to approach problem B?
•  » » hint 1For n=2, make an Y how does it adapt for bigger n ? hint 2dp in O(n^3) find solution for each contiguous subarray of x_i and compute how to merge them
 » Pretty nice contest, but a lot of the problems could be solved by making wild guesses and getting proof by AC.
 » Any hints on L ,Tried a lot on it and ended up in tle
•  » » Same brother. I submitted so many times, still TLE on test4
 » Thanks for the contest, the problemset is wonderful! By the way, I hate problems with real numbers.
•  » » How is it humanly possible to solve B in 9min 😨 •  » » Judging by your comment, you are far from programming. So you're a stupid copywriter. Try to put a dislike. lol:)
 » How to solve K?
•  » » I used log-exp trick, though get WA on test 21
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   we want to compute first 250 coefficents of ((1+x/1)*(1+x/2)*...*(1+x/(n-1))/n with good precisionwe 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
•  » » 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   You can calculate sums of such type using https://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula
 » How to solve D?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   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$.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   .
 » where can i find the official scoreboard ?
•  » » It should be there soon :icpc website Furthermore you should be able to know it from the stream of the closing ceremony
•  » » 4 weeks ago, # ^ | ← Rev. 2 →
•  » » Now the results are available both on the ICPC website and on the official SWERC website.
 » How To solve Problem H(Beppa and SwerChat ) please?
•  » » Hint1Use two pointers ia for a and ib for b and go backward and be greedy Solutioniina = -1 iinb = -1 s = 0 while iina+n>=0: if a[iina]==b[iinb]: iinb -= 1 else: s+=1 iina-=1  Proof of solutionWhen 2 values are equal, it's possible this person didn't reconnect, let's say so. Elsewise increment answer by one. Order in b gives a possible order of last connections of people.
 » I liked the problems even though they were hard for me (⁠ ⁠≧⁠Д⁠≦⁠). Can someone give me a hint for problem F?
•  » » HintWhat you want is more or less a cut case disjunctionDistinguish whether graph is complete or not SolutionIf graph is incomplete choose a vertex who isn't neighbour of everyone. Company 1 get all edges linked with this node Company 2 get the rest If graph is complete Company 1 get the edge from 1 to 2 Company 2 get the other edges linked with 1 Company 3 get the remaining edges
•  » » If there's a vertex u with degree
•  » » Thanks bcollet and YocyCraft for the help
 » How to solve E,N ?
 » 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
•  » » java.util.Scanner is extremely slow when dealing massive input. Maybe you can try to use java.io.BufferedReader instead.
 » Will contest with official problems with same exact order from onsite be uploaded to gym?
 » 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.
 » Uploaded the editorial, see the announcement.
 » participated as individual，solved 3 simple problems and ranked 634
 » I feel like I solved H in a much simpler way than the editorial.I worked through a lot examples and noticed that we just need to keep track of whenever indices of the element of the right element was previously before the element. Than add that + 1 as the answer.I lazily did a lookup of indices for elements in the original array a: void solution() { int n, ans = 0; cin >> n; vector a(n); vector b(n); vector indices(n + 1, 0); for (int i = 0; i < n; i++) { cin >> a[i]; indices[a[i]] = i; } for (int i = 0; i < n; i++) { cin >> b[i]; } for (int i = 0; i < n - 1; i++) { if (indices[b[i + 1]] < indices[b[i]]) { ans = i + 1; } } cout << ans << endl; } 
 » 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?
•  » » 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. Implement different solutions performing the operations differently. If they agree (to the desired precision), then it is likely that they are both accurate enough. 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. If you ask for precision $\epsilon$, make sure that your solutions have precision $\epsilon/10$ or better. 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.
•  » » » 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?
 » 4 weeks ago, # | ← Rev. 3 →   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?
•  » » Maybe I am not understanding, x = maxsum is the solution.
•  » » » yes)) our maxsum == all sum, not on segment of length n
•  » » 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).
•  » » » yes, maxseg is whole sum, but anyway my question is actual :)
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   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.
 » loser you
 » Will the onsite contest be pushed to the Gym?
•  » » Yes, we will do it soon!
•  » » » Thanks for that!
•  » » » still planned? "^^
 » 4 weeks ago, # | ← Rev. 3 →   .
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   .
 » It should be rated.
 » I think problem I has weak cases. Some overflowing solutions still give Accepted.
 » 4 weeks ago, # | ← Rev. 2 →   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!
 » Just?????
 » Out of curiosity, what rating would you expect of problem B from the official contest ? I guess around 1600-1800 ?
 » My English sucks... Any short proof for Problem J?
•  » » 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 oneThe 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)$.
 » exp+=3
 » Do you guys know who kkksc03 is?
 » 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.
 » problem G's pretty nice, love it!!!
 » 后排中文（？
 » Best problemset I'd ever seen