Hi everyone!
2022 Southeastern Europe Regional Contest will take place tomorrow, on December 10. The contest was prepared by bicsi, antontrygubO_o, theodor.moroianu, lungualex00, eudanip.
Good luck to the official participants!
There will be a mirror of this contest this Sunday, December 11, 08:00 UTC. It will be held by the link https://seerc2022.eolymp.io/.
We hope that you will enjoy the contest! See you on the scoreboard.
UPD1: Congratulations to the winners of SEERC!
This year, the contest was held on two sites, Ukrainian and Romanian.
Standings and Top 5 of Ukrainian site:
Place | Team Name | Contestant 1 | Contestant 2 | Contestant 3 | Problems | Penalty |
---|---|---|---|---|---|---|
1 | [Ukraine] LNU Stallions | Yarema.st | mshcherba | PetroTarnavskyi | 9 | 1091 |
2 | [Ukraine] UzhNU_OLDS | Fekete | YaroslavBulyna | illyakr | 7 | 1129 |
3 | [Ukraine] LNU NextGen | FEREND | Ebiarat | RHplu51 | 6 | 916 |
4 | [Ukraine] KhNURE_(-_-(-_-)-_-) | log2win | Phys-mat_KCh | avoronoi | 6 | 1044 |
5 | [Ukraine] UzhNU_3yagoda | VasyaMer | tedi_2.0 | Happy.CoDer | 5 | 445 |
Standings and Top 5 of Romanian site:
Place | Team Name | Contestant 1 | Contestant 2 | Contestant 3 | Problems | Penalty |
---|---|---|---|---|---|---|
1 | [Serbia] Infinity | nikolapesic2802 | TadijaSebez | stefanbalaz2 | 11 | 1272 |
2 | [Cyprus] bird-cherry | buyolitsez | GrandFruit | step_by_step | 10 | 1516 |
3 | [Serbia] GII Klub | MladenP | milisav | Pajaraja | 10 | 1603 |
4 | [Romania] Echipa Sarata | alexandra_udristoiu | popabogdannnn | Stelutzu | 9 | 1268 |
5 | [Serbia] UoB R-Shuf | Djordjevic | VladaMG98 | JovanB | 8 | 1018 |
Once again, we invite you to the mirror tomorrow.
UPD2: Editorial
UPD3: The contest was uploaded to the gym: 2022 ICPC Southeastern Europe Regional Contest. I will add results of official participants soon.
anton is the best setter
It seems like we cannot sign up on the Eolymp platform currently. I hope this issue is resolved ASAP.
Thanks for the interesting contest... now to wait two years to hear about who proceeds to WF!
Is anyone able to sign up on the platform? Also why is the mirror not on CF instead? Probably would have been much easier to both participate and prepare the contest that way.
The API server is returning
400 (Bad Request)
since yesterday, and there hasn't been a fix yetI'm also getting a "bad request" error and am still unable to register on the site. I thought it would be open when the contest starts, but now it seems not.
This is bizarre, but I successfully created the Eolymp account from https://www.eolymp.com/en/, and the same account is valid on the seerc2022 site.
How to solve N?
you always want to guarantee youre able to reach the highest value while differing by at most m.
let a[i] be max(s[i], a[i+1] — m) for i from n to 1. This guarantees the least amount you have to assign to reach the peaks that come after.
let ans[i] = max(ans[i-1] — m, a[i]) for i from 1 to n. This represents taking the max of the least amount you have to assign and if you were to subtract m from previous.
Thanks!
Is there any solution to Gears which does not require hashing?
By considering the minimum element, there exists at most two candidate values for x1.
Got it, thanks!
btw, were you giving as a team or alone?
alone
Ohh nice.
For E, can someone please help me understand why this dynamic programming approach is incorrect.
Sorting the array and storing the indices in which these appear in the original array. If at any index 2*i-1 and 2*i, the elements weren't paired originally then we pair them, otherwise we either pair the elements at indices 2*i-1, 2*i with 2*i-3,2*i-2 or 2*i+1,2*i+2. Code: https://codeshare.io/6p9pmg
Thanks!
Sometimes you need to make "groups" of 6 elements, not just 2 or 4.
This is the case when you have 6 elements in the array, the first 2 elements are connected, the middle two are connected, and the last 2 elements are connected (order doesn't change when sorted). If you make one group of 4 elements in this case, you will not be able to pair the remaining 2 elements.
Because of this, you need a case in the DP when you make a group of 2, 4 and 6 elements. You will always be able to make groups of 4 and 6 (no matter the edge restrictions), so you just need a check for the 2 element group. A group here is some interval where there is an edge "above" the gap between every 2 adjacent elements.
Thanks a lot <3
What is the intended solution for D? Will there be an editorial?
The official editorials have just been finished (sorry for the delay). They will also be available in the Gym contest when it gets uploaded.
https://drive.google.com/file/d/1MS0R9gT6XGpM_R1DIslzvhQ-MCMR4tIV/view?usp=sharing
Very nice problems, I liked them very much. Although I've seen K already several times. For example on Petrozavodsk two years ago (graph was presented as the thin grid there though, but that does not change anything), but even there I already thought that it's known. At least this time it took me 17 minutes to solve from scratch, unlike half of the contest like on Petro xd. And I think D&C approach is definitely easier to think of and to code than the one from the editorial.
M: I think it is a bit cleaner if we binary search using Stern-Brocot tree. No doubles, no rounding, just one phase solution, same complexity (although my code is worse by log factor since I binary searched instead of solving quadratic inequality).
L: Much more natural approach would be to compute dp from left to right, but it does not work that well, because then we would need to wrap it with binary search on the starting health on top. I think it is good to emphasize how clever is reversing that and why is it needed, but it was not present in the editorial. Also, when I was solving this and tried to optimize the needed convolution I got the "convex hull" idea, but couldn't get rid of a log from the inside of it which I needed to intersect two functions, but you claim in the editorial that it could be done without that log. Could you elaborate?
EDIT: OK, I found this editorial https://codeforces.me/blog/entry/98663 . The answer is SMAWK xd. Though based on recent blog about it I am not sure if this will help :P
Also, it's funny to see the scoreboard snowball effect and for example how C turned to be one of the easiest for CF participants, but one of the hardest for onsite participants.
Btw "I will add results of official participants soon." — that was not done
Hello antontrygubO_o, maybe there is a mistake in the editorial of problem D. In the last case, $$$(2, 2, 2)$$$, you showed that it's not able to switch the parity only if the parities of degrees of $$$2, 3, 4$$$ are all equal and of $$$1, 5$$$ are opposite. It is right, but potentially incomplete. Assume a component that $$$k \ge 3$$$ vertices $$$u_1, u_2, \cdots, u_k$$$ instead of $$$2, 3, 4$$$, satisfing the condition (the parities of $$$u_1, u_2, \cdots, u_k$$$ are all equal). It seems that we cannot switch the parity no matter what the value of $$$k$$$ is. One of the scenarios I described is shown below:
This is a code that enumerats spanning trees written by dcmfqw. It shows that the answer for the case above is
NO
.192601989 this is a code also written by dcmfqw, following the approach I have described above.
I didn't find this case in your category discussion above. Maybe I misunderstood, but this hack does exist.
So is it your mistake? Or just where I did not see clearly?
Please forgive my poor English XD