BledDest's blog

2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest [Online Mirror, ICPC Rules]
By BledDest, 9 days ago, In English

Note that initially this contest was scheduled on a different day. Due to technical difficulties, we had to postpone the online mirror. We are sorry about that; if you planned to participate, but are no longer able because the contest day has changed, you can use the virtual participation option.

Hello Codeforces!

The Southern and Volga Russian Regional Contest was held in Saratov State University yesterday, on 12th of November. This contest was used to qualify the teams from Southern Russia and Volga region to the Northern Eurasia Finals.

On Nov/18/2024 13:35 (Moscow time), we will conduct the online mirror of this contest. It will last for 5 hours and is best suited for teams of three people, although it is not forbidden to participate in teams of smaller/larger size. The mirror will use ICPC rules, the same as the offline contest.

The contest was prepared by adedalic, awoo, dmitryme, elena, Neon, DmitryKlenov, MikeMirzayanov, Ferume and me. Big thanks to the contest testers: Kuroni, ashmelev, bthero, KIRIJIJI, Kniaz, vladmart, JanPlovLagman, H3nTa1, pshenikita. I would like to express my gratitude to MikeMirzayanov for not only participating in the preparation process himself, but also making Polygon, which made our work much easier.

As the chief judge of the contest, I hope you enjoy the problems!

Of course, the contest will be unrated.

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

»
9 days ago, # |
  Vote: I like it -31 Vote: I do not like it

ohk...

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to see rated 5 hours long team contests in codeforces in future?

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think it is hard because how could a team perfomrance an indication for every member's level. But I believe that it will be interesting if codeforces add a new feature of rating for teams and then introduce this new type of contests.

    → Reply
»
9 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Excuse me, in the online mirror, is it valid for the team members to use different computers at the same time? For the past ICPC-style contests on Codeforces, there are both cases of "yes" and "no".

→ Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Sorry for the long wait, I was unable to reply faster.

    This contest is most suitable for solving it using only one computer per team (same as during the onsite event). However, we cannot enforce this rule, so it is not forbidden to use multiple computers.

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much! :D

      → Reply
»
8 days ago, # |
  Vote: I like it -13 Vote: I do not like it

but why only 7 comments?

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i am looking for a team...

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hi, are you still looking for team i mean not for this contest but for future contest

    → Reply
»
5 days ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Sorry

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Exuse me, what does it mean that the registration screen number box is red?

→ Reply
»
4 days ago, # |
  Vote: I like it +19 Vote: I do not like it

it is not forbidden to participate in teams of smaller/*larger size*

Codeforces tells me "You should select between 1 and 3 team members" :thinking:

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Woohoo!

→ Reply
»
4 days ago, # |
  Vote: I like it +17 Vote: I do not like it

H is quite cool

→ Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

Thank you for participation! We hope you enjoyed the problems.

You can access the solution slides (ordered according to the difficulty level, or at least how we perceived it) here: in Russian, in English.

Problems were authored and prepared by:
→ Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

wrong answer Provided points do not form a rectangle with sides parallel to axes: (94, -50), (94, -39), (94, -32), (94, -29) (test case 5518)

why?

ok understood now but atleast give definition of degenerate rectangle in problem statement, I thought like triangle collinearity assures degneration

→ Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

for L bridge renovation, is it a direct greedy? or do permutations for order of operations which take as many as possible ? and is dp possible?

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's direct greedy. You won't need dp or anything complicated.

    → Reply
»
4 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Can F be solved without FFT? Otherwise I find it really weird that so many teams solved it in contest. Like, how is this about as solved as problem I which could have been literally done with some simple hashes??

→ Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    FFT isn't that hard

    → Reply
    • »
      »
      »
      40 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It kind of depends on what you are training for, I guess. Like in icpc style where you have documentation and university people participate it is quite decent to have FFT problems as not very hard ones. I for instance am currently in high school, training for IOI like contests where FFT problems are very rare (actually pretty inexistent) so probably that is where my surprise comes from

      → Reply
»
4 days ago, # |
← Rev. 3   Vote: I like it -6 Vote: I do not like it

Can someone can provide a proof for the solution claim in Problem G :

  • For each character, except the last, there is a next character — 1 or 0.
  • Based on this, we can ask the following queries — 1, 11, and 10.
  • After each 1, except the last, there will be a character, so if the answer to the first query equals the sum of the other two, then the last character is not 1
→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    everytime a one occurs, the element next to it can be 1 or 0. in a string where there is 0 at last, no of 1s = no of 10 + no of 11 follows. in a string where there is 1 at last, the sum will be no of ones -1

    → Reply
»
3 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi! I'm just curious — according to official standings, nobody has solved C and G, but they were quite easy here.

Image

So what was the original order?

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +27 Vote: I do not like it
    Original problem order
    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I referred to Jiangly's submission 292165413. He made all the elements of array equal and less than 3 (if possible) while storing the count of number of operations required on each index and if it's possible the minimum operations can be achieved by simply subtracting minimum value of an operation on any index times n from total number of operations......

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    // this is solution ?

    I solved it a bit differently. Let $$$f[i]$$$ be the number of operations you apply at $$$i$$$. Note that $$$f[i]$$$ is cyclic, meaning $$$f[i] = f[i + N]$$$. Let the final element be $$$x$$$. Then, we must have:

    $$$ a[i] - 2f[i] + f[i - 1] = x. $$$

    If you solve this equation for $$$f[i]$$$ (I took $$$N = 5$$$ as a reference), you find:

    $$$ f[i] = -x + \frac{a[i + 1] + 2a[i + 2] + 4a[i + 3] + \cdots + 2^{N - 1}a[i]}{2^N - 1}. $$$

    Let the second term be $$$q[i]$$$, where:

    $$$ q[i] = \frac{a[i + 1] + 2a[i + 2] + 4a[i + 3] + \cdots + 2^{N - 1}a[i]}{2^N - 1}. $$$

    Observe that $$$q[i]$$$ satisfies the recurrence:

    $$$ q[i] = 2q[i + 1] - a[i + 1]. $$$

    Thus, we can compute $$$q[N - 1]$$$ first and then evaluate all $$$q[i]$$$. However, if $$$q[N - 1]$$$ is not an integer, we immediately print $$$-1$$$.

    Additionally, since $$$f[i] \geq 0$$$ for all $$$i$$$, it follows that $$$x \leq q[i]$$$. The final answer is:

    $$$ \sum_{i=0}^{i = N - 1} f[i] = -Nx + \sum_{i=0}^{i = N - 1} a[i]. $$$

    Hence,

    $$$ x = \min_{i = 0}^{N - 1} q[i]. $$$

    After this, we check whether $$$x$$$ is non-negative and then print the final answer.

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D : Is it possible for Java code to fit in the 3s time limit? (Tried lots of optimization, still got TLE)

→ Reply
»
3 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How to prove K? That there exists an optimal path passing through x, y, where x, y are maximal coordinates such that gcd(a,x) = 1 and gcd(b,y) = 1.

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    (I misread, so ignore, sorry) the path forms a sort of an reversed L(goes right and then down)

    I am going to part from the fact that gcd(x,a) = 1 and gcd(y,b) = 1, and that the lower bound is

    $$$(x - 1) + (y - 1) + \sum_{i=1}^{x} gcd(i, a) + \sum_{i=1}^{y} gcd(i, b)$$$

    Then the cost of the path (goes right and then down) is

    going from $$$(1, 1)$$$ to $$$(1, y)$$$ costs $$$\sum_{i=1}^{y} gcd(1,a)+ gcd(i, b)$$$, and

    $$$\sum_{i=1}^{y} gcd(1,a)+ gcd(i, b) = \sum_{i=1}^{y} 1 + gcd(i, b) = y + \sum_{i=1}^{y} gcd(i, b)$$$

    and going from $$$(1, y)$$$ to $$$(x, y)$$$ costs $$$\sum_{i=2}^{x} gcd(i, a) + gcd(y, b)$$$, and recall that $$$gcd(y, b) = 1$$$, so we have

    $$$\sum_{i=2}^{x} gcd(i, a) + gcd(y, b) = \sum_{i=2}^{x} gcd(i, a) + 1 = -1 -1 + x \sum_{i=1}^{x} gcd(i, a)$$$

    So the cost along all the path can be expressed as

    $$$(x - 1) + (y - 1) + \sum_{i=1}^{x} gcd(i, a) + \sum_{i=1}^{y} gcd(i, b)$$$

    Which is the lower bound, hence it is optimal

    → Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Let's look at "border" $$$(n, y) - (x, y) - (x, n)$$$. Any path from $$$(1, 1)$$$ to $$$(n, n)$$$ crosses it.

    WLOG, let's say that the path crosses the border at cell $$$(x, y')$$$ where $$$y \le y' \le n$$$.

    Let's find the minimum path from $$$(1, 1)$$$ to $$$(x, y')$$$. It's easy to see that we can go from $$$(1, 1)$$$ to $$$(x, 1)$$$ and then to $$$(x, y')$$$ since $$$\gcd(x, a) = 1$$$.

    So, the path $$$(1, 1) - (x, y')$$$ goes through cell $$$(x, y)$$$ for any $$$(x, y')$$$.

    → Reply
»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D: i need another editorial or explaination

→ Reply