antontrygubO_o's blog

By antontrygubO_o, 23 months ago, In English

ICPC Logo

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.

  • Vote: I like it
  • +130
  • Vote: I do not like it

| Write comment?
»
23 months ago, # |
  Vote: I like it +59 Vote: I do not like it

anton is the best setter

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

It seems like we cannot sign up on the Eolymp platform currently. I hope this issue is resolved ASAP.

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

Thanks for the interesting contest... now to wait two years to hear about who proceeds to WF!

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

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.

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

    The API server is returning 400 (Bad Request) since yesterday, and there hasn't been a fix yet

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

    I'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.

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

    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.

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

How to solve N?

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

    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.

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

Is there any solution to Gears which does not require hashing?

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

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!

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

    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.

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

What is the intended solution for D? Will there be an editorial?

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

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

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

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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

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.

code

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