dario2994's blog

By dario2994, history, 6 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

• +351

 » 6 weeks ago, # | ← Rev. 2 →   +83 I wonder whether there ever will be a swerc problemset that MIT team can AK
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   -8 .
•  » » » 5 weeks ago, # ^ |   +3 lol bro
•  » » » » 5 weeks ago, # ^ |   -24 please vote me up, thx.
 » 5 weeks ago, # |   0 I wonder whether there ever will be a swerc problemset that MIT and THU team can AK
•  » » 5 weeks ago, # ^ |   0 Maybe yes
 » 5 weeks ago, # |   +2 good luck everyone!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 .
 » 5 weeks ago, # |   0 Good luck))
 » 5 weeks ago, # |   -43 I hope that the round will be good and we will score a lot of points
•  » » 5 weeks ago, # ^ |   +3 very very bad comment. Stupid
 » 5 weeks ago, # |   +20 thanks to problemsetters for the contest! I think J is a nice problem
 » 5 weeks ago, # |   +3 Not able to view solutions , please check the bug
 » 5 weeks ago, # |   +4 Problem B, G seem cool. Surely gonna learn something from them. Btw, how to approach problem B?
•  » » 5 weeks ago, # ^ |   +8 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
 » 5 weeks ago, # |   +62 Pretty nice contest, but a lot of the problems could be solved by making wild guesses and getting proof by AC.
 » 5 weeks ago, # |   0 Any hints on L ,Tried a lot on it and ended up in tle
•  » » 5 weeks ago, # ^ |   0 Same brother. I submitted so many times, still TLE on test4
 » 5 weeks ago, # |   +162 Thanks for the contest, the problemset is wonderful! By the way, I hate problems with real numbers.
•  » » 5 weeks ago, # ^ |   +54 How is it humanly possible to solve B in 9min 😨
•  » » 5 weeks ago, # ^ |   -88 Judging by your comment, you are far from programming. So you're a stupid copywriter. Try to put a dislike. lol:)
 » 5 weeks ago, # |   +11 How to solve K?
•  » » 5 weeks ago, # ^ |   +6 I used log-exp trick, though get WA on test 21
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +20 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
•  » » 5 weeks ago, # ^ |   +9 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 You can calculate sums of such type using https://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula
 » 5 weeks ago, # |   +42 How to solve D?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +19 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$.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 .
 » 5 weeks ago, # |   +8 where can i find the official scoreboard ?
•  » » 5 weeks ago, # ^ |   0 It should be there soon :icpc website Furthermore you should be able to know it from the stream of the closing ceremony
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3
•  » » 5 weeks ago, # ^ |   0 Now the results are available both on the ICPC website and on the official SWERC website.
 » 5 weeks ago, # |   0 How To solve Problem H(Beppa and SwerChat ) please?
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 I liked the problems even though they were hard for me (⁠ ⁠≧⁠Д⁠≦⁠). Can someone give me a hint for problem F?
•  » » 5 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ |   0 If there's a vertex u with degree
•  » » 5 weeks ago, # ^ |   0 Thanks bcollet and YocyCraft for the help
 » 5 weeks ago, # |   0 How to solve E,N ?
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   +5 java.util.Scanner is extremely slow when dealing massive input. Maybe you can try to use java.io.BufferedReader instead.
 » 5 weeks ago, # |   +25 Will contest with official problems with same exact order from onsite be uploaded to gym?
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # |   +13 Uploaded the editorial, see the announcement.
 » 5 weeks ago, # |   -13 participated as individual，solved 3 simple problems and ranked 634
 » 5 weeks ago, # |   -10 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; } 
 » 5 weeks ago, # |   +54 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?
•  » » 5 weeks ago, # ^ |   +54 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.
•  » » » 5 weeks ago, # ^ |   +70 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?
 » 5 weeks ago, # | ← Rev. 3 →   0 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?
•  » » 5 weeks ago, # ^ |   0 Maybe I am not understanding, x = maxsum is the solution.
•  » » » 5 weeks ago, # ^ |   0 yes)) our maxsum == all sum, not on segment of length n
•  » » 5 weeks ago, # ^ |   0 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).
•  » » » 5 weeks ago, # ^ |   0 yes, maxseg is whole sum, but anyway my question is actual :)
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 5 weeks ago, # |   -11 loser you
 » 5 weeks ago, # |   0 Will the onsite contest be pushed to the Gym?
•  » » 5 weeks ago, # ^ |   +14 Yes, we will do it soon!
•  » » » 5 weeks ago, # ^ |   0 Thanks for that!
•  » » » 9 days ago, # ^ |   0 still planned? "^^
 » 5 weeks ago, # | ← Rev. 3 →   -16 .
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 .
 » 5 weeks ago, # |   -19 It should be rated.
 » 5 weeks ago, # |   0 I think problem I has weak cases. Some overflowing solutions still give Accepted.
 » 5 weeks ago, # | ← Rev. 2 →   +123 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!
 » 5 weeks ago, # |   -13 Just?????
 » 5 weeks ago, # |   0 Out of curiosity, what rating would you expect of problem B from the official contest ? I guess around 1600-1800 ?
 » 5 weeks ago, # |   +3 My English sucks... Any short proof for Problem J?
•  » » 5 weeks ago, # ^ |   +26 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)$.
 » 5 weeks ago, # |   -18 exp+=3
 » 5 weeks ago, # |   0 Do you guys know who kkksc03 is?
 » 5 weeks ago, # |   +8 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.
 » 5 weeks ago, # |   0 problem G's pretty nice, love it!!!
 » 4 weeks ago, # |   0 后排中文（？
 » 4 weeks ago, # |   0 Best problemset I'd ever seen