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:
- The amazing set of judges who proposed and prepared the problems: cescmentation_folch, cip999 (vice chief judge), gangsterveggies, Giove, gog.gerard, jinlifu1999, Petr, Simon, tap_tapii, Um_nik.
- The MIT team composed of antontrygubO_o, Rewinding, TLE for testing the round and Philae for proofreading the statements.
- Everyone involved in the organization of SWERC, in particular Dariost (director) and edomora97 (technical director).
- 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 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
- The contest is unrated, so your codeforces rating will not be affected.
- 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.
- We encourage participation as a team.
- 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.
UPDATE: We hope you liked the problems!
We uploaded the editorial of the contest (you can find it at https://mirror.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:
- ENS Ulm 1 -- École Normale Supérieure de Paris
- gETHyped -- ETH Zürich
- P+P+P -- Harbour.Space University
I wonder whether there ever will be a swerc problemset that MIT team can AK
.
lol bro
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!
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?
For n=2, make an Y how does it adapt for bigger n ?
dp 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.
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 😨
How to solve K?
I used log-exp trick, though get WA on test 21
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
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.
You can calculate sums of such type using https://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula
How to solve D?
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$$$.
.
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
Here it is: https://swerc.eu/2022/theme/scoreboard/public/
How To solve Problem H(Beppa and SwerChat ) please?
Use two pointers ia for a and ib for b and go backward and be greedy
When 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?
What you want is more or less a cut
Distinguish whether graph is complete or not
If 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 <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).
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://mirror.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
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.
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?
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:
Here
maxseg
is actually storing the total number ofW
s in the string, right? Or am I missing something in your template? From your comment I assumed that bymaxseg
you meant the maximum number ofW
s in a segment of lengthn
, in which casemaxseg
always works (as in the editorial).yes, maxseg is whole sum, but anyway my question is actual :)
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.
Will the onsite contest be pushed to the Gym?
Yes, we will do it soon!
Thanks for that!
still planned? "^^
I think problem I has weak cases. Some overflowing solutions still give Accepted.
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!
Out of curiosity, what rating would you expect of problem B from the official contest ? I guess around 1600-1800 ?
Field should not be empty
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 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)$$$.
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!!!
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
Best problemset I'd ever seen
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
Forget about solving I am even unable to understand editorial