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.
ohk...
Is it possible to see rated 5 hours long team contests in codeforces in future?
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.
In history a group rating change already happened in codeforces, you can see here
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".
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.
Thank you very much! :D
but why only 7 comments?
i am looking for a team...
hi, are you still looking for team i mean not for this contest but for future contest
Sorry
Exuse me, what does it mean that the registration screen number box is red?
Codeforces tells me "You should select between 1 and 3 team members" :thinking:
true
true
true
Woohoo!
H is quite cool
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.
A: Proposed and prepared by DmitryKlenov
B: Proposed by the judges collective, prepared by Neon
C: Proposed by BledDest, prepared by dmitryme
D: Proposed and prepared by Ferume
E: Proposed and prepared by adedalic
F: Proposed and prepared by adedalic
G: Proposed and prepared by BledDest
H: Proposed and prepared by BledDest
I: Proposed by BledDest, prepared by awoo
J: Proposed and prepared by elena
K: Proposed and prepared by adedalic
L: Proposed and prepared by adedalic
M: Proposed and prepared by BledDest
N: Proposed and prepared by BledDest
B was so cool, thanks.
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
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?
It's direct greedy. You won't need dp or anything complicated.
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??
FFT isn't that hard
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
Can someone can provide a proof for the solution claim in Problem G :
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
Thanks,got it.Just missing these trivial observations.
Hi! I'm just curious — according to official standings, nobody has solved C and G, but they were quite easy here.
So what was the original order?
A. Bridge Renovation
B. Divide OR Conquer
C. Barrels
D. Bonus Project
E. Alternative Platforms
F. Fixing the Expression
G. Galactic Council
H. Grid Walk
I. Guess One Character
J. Make It Equal
K. Polyathlon
L. DIY
M. Royal Flush
N. Waiting for...
How to solve B?
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......
Problem D : Is it possible for Java code to fit in the 3s time limit? (Tried lots of optimization, still got TLE)
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.
(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
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
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
So the cost along all the path can be expressed as
Which is the lower bound, hence it is optimal
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')$$$.
Thanks for the proof, great problem!
Problem D: i need another editorial or explaination