By awoo, history, 6 months ago, translation,

Hello Codeforces!

The problems are based on the Southern Russia and Volga Cup 2021, which is a regional contest of ICPC. If you have participated in it or are planning to play it as a virtual contest, please refrain from taking part in the Educational Round.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

• +176

 » 6 months ago, # |   +25 NOTE THE UNUSUAL TIMING
 » 6 months ago, # |   0 eagerly waiting for the contest.
 » 6 months ago, # |   +20 Why Unusual timing again? :(
•  » » 6 months ago, # ^ |   -22 Now that's usual:(
 » 6 months ago, # |   0 Finally After 7 days. Thank You.
 » 6 months ago, # |   +4 Finally a cf contest after so long .....All the best to the fellow programmers !!
 » 6 months ago, # |   0 I look at the unusual timing of the contest. I take a mental note so that I do not miss the contest. I miss the contest anyway.
 » 6 months ago, # |   +1 contest after long time in unusual time , why in the last period the contests in unusual time :(
 » 6 months ago, # |   +54 On behalf of all Russian schoolers, I protest against the unusual timings on weekdays.
•  » » 6 months ago, # ^ |   +6 Isn't that just a good reason to skip school?)
 » 6 months ago, # |   +40 On behalf of myself I strongly support the unusual timing, it gives an opportunity for competitors around the world to participate :)
 » 6 months ago, # |   +8 Will try to perform better this time. let's hope for the best. Good luck everyone!
 » 6 months ago, # |   +5 Good luck everyone!
 » 6 months ago, # |   0 and for you!
 » 6 months ago, # |   0 I hope you will done the best
 » 6 months ago, # | ← Rev. 2 →   +37 Last week one contest this week five contest I am not complaining, but it would have been better if contests evenly spaced them in these two weeks. Lately, there has been a lot of inconsistency in contests either there are very few, or there is a lot in a 7 to 10 days period. Anyway, today is contest day, so best of luck to everyone.
 » 6 months ago, # |   0 Good luck for you! Good luck for me! Good luck for everybody ~
 » 6 months ago, # |   -38 Can you change the timing i have meeting from 4:00 to 4:30 pm , please
•  » » 6 months ago, # ^ | ← Rev. 2 →   +74 I need this much confidence
•  » » » 6 months ago, # ^ |   +9 lol,it was sarcasm ,xd
•  » » » » 6 months ago, # ^ |   +3 this comment made my day xddd
 » 6 months ago, # |   -12 Will the problems be arranged in the correct difficulty order? Or will it be shuffled as we see in icpc?
 » 6 months ago, # |   0 But Is It Rated?
»
6 months ago, # |
+9

# Mathforces

•  » » 6 months ago, # ^ |   0 cheatingforces
 » 6 months ago, # |   +10 How to solve D?
• »
»
6 months ago, # ^ |
-7

# mathforces?

 » 6 months ago, # |   +10 How to solve E?
•  » » 6 months ago, # ^ | ← Rev. 16 →   0 i did it using ternary search on the number of messages to be pinned , and then selected the books in a greedy way, got tle on tc 149 , but after one optimization it ran comfortably. Update: the solution was wrong
•  » » » 6 months ago, # ^ |   0 thx, got it
•  » » » 6 months ago, # ^ |   +5 Your function isn't parabola or convex. When T(len of answer) is [1; 20], ur function gets chaotic values. When T is [21; 2e5] fucntion decreases on all segment
•  » » » » 6 months ago, # ^ |   0 No wonder it got hacked
•  » » » 6 months ago, # ^ |   +3 Your ternary search solution has been hacked :)
 » 6 months ago, # |   -8 best contest i've ever done!
 » 6 months ago, # |   +58
 » 6 months ago, # |   0 Does anyone know the proof for why it's never optimal to select more than 20 pins in 1612E - Сообщения??
•  » » 6 months ago, # ^ |   +2 If $s_i$ is the sum of all $k_i$ with $m_i = i$, then the expected return you get from including $i$ is equal to $\frac{s_i}{t}$ if $t \geq 20$. Note that you greedily want to select the largest $t$ values of this for the messages, and you can show that this value is greatest when $t = 20$ (since averages decrease since you're taking lower and lower sums).
•  » » » 6 months ago, # ^ | ← Rev. 3 →   -24 I mean many people made the guess for first 20 but I wasn't smart enough ig.
•  » » 6 months ago, # ^ |   +8 If you take 20 best messages out of $m$ taken in terms of expected value contribution and leave just them, their expected value will increase proportionally to $\frac{m}{20}$. But since they were maximal total EV will not decrease.
•  » » » 6 months ago, # ^ |   0 Alright thanks this is pretty helpful!
•  » » 6 months ago, # ^ |   0 Suppose we have selected the $y$ messages with the max $x$, where $y$ $\geq$ $20$, and $\sum{k_i}$ $=$ $x$ for all $i$ where $i$ is one of the chosen messages. If we select the $(y+1)_{th}$ message $msg$ where $\sum{k_j}$ $=$ $z$ for all $j$ where $m_j$ = $msg$, the first $y$ messages are still the best, and their total expected value decreased from $\frac{x}{y}$ to $\frac{x}{y+1}$, that is, decreased by $\frac{x/y}{y+1}$. However, $msg$ only introduced $\frac{z}{y+1}$, and $z$ $\leq$ $\frac{x}{y}$, otherwise it would be one of the best $y$ messages.
 » 6 months ago, # |   +37 idk how many guys pass G, I want to say that F is much easier than G
•  » » 6 months ago, # ^ |   +34 When I began solving G, it had 17 solves while F had like 3.Most people who reached F/G didn't have time to solve both, so it was probably just an observer effect here.
•  » » 6 months ago, # ^ |   +6 Hi, can you please give some hints on how to solve F? For me G seemed easier than F.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 You can just optimize bfs.The queue contains tuples $(a, b, d)$ ($d$ is the number of moves to reach $(a, b)$). Let $(a, b, d)$ be a useless tuple if there exists a tuple $(a', b', d)$ in the queue, with $a' > a$ and $b' > b$. If you remove useless tuples from the queue (e.g. by rebuilding the whole queue if its size is $> 2 \cdot 10^5$), the bfs is fast enough.
 » 6 months ago, # |   +1 How to solve D ? I called gcd(difference, maximum number % difference), but if the difference is larger, then it gets executed huge number of times...
•  » » 6 months ago, # ^ |   +3 Basically, the numbers you can reach are everything reached by the Euclidean algorithm for a and b.
•  » » » 6 months ago, # ^ |   0 [user:Agnimandur]can u plz see my C solution I tried it in O(1) can u plz try this approach and tells whats wrong i spend about an hour but didn't got anything thnx in advance
•  » » 6 months ago, # ^ |   0 I guess resultant number was eventually max-min*k such that max-min*k>=min after that max and min will change so you just have to check whether x%min==max%min otherwise pass for min,max%min
 » 6 months ago, # |   +6 Hmm... I think G is easier than E. E was difficult to translate.
 » 6 months ago, # |   +23 nice code
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 bruh xD
 » 6 months ago, # | ← Rev. 2 →   +3 I dont know how total accepted submissions of problem D went from around 1200 to 1700 in last 20 minutes ;_;
•  » » 6 months ago, # ^ |   +11 Maybe it's just cheating again...
 » 6 months ago, # |   +1 traditional -100 for me kekw
•  » » 6 months ago, # ^ |   +25
 » 6 months ago, # | ← Rev. 3 →   -13 EDIT: ok i got the mistake.
 » 6 months ago, # |   -9 i should've been prepared more before joining this round
•  » » 6 months ago, # ^ |   -6 Same buddy
 » 6 months ago, # |   0 Can Anyone provide the intuition behind D, it ate up my whole hour, still couldn't find a logic.
•  » » 6 months ago, # ^ |   +9 When assignment operations are only based on substraction of two no.s . Think GCD .
•  » » » 6 months ago, # ^ |   0 i tried GCDs, but idk how to actually solve
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +1 Go through the same procedure as GCD , and before recurring for GCD(b%a,a) check that whether (b%a)+(j*a) is equal to x or not , j is from 0->r such that (b%a)+((r+1)*a) is greater than b . For clearity refer this https://codeforces.cc/contest/1612/submission/136448350
•  » » » » » 6 months ago, # ^ |   0 Great, Many thanks to you
•  » » » » » 6 months ago, # ^ |   0 Can you please explain this part? I would be very thankful to you. Code lli z=b%a; lli x1=x-z; if(x1>=0 and x1%a==0 and x<=b) { flag=true; return 0; } 
•  » » » » » » 6 months ago, # ^ |   0 As I said before if x's value is b%a+(j*a) where j is 0 to r , then x is achievable . So x=(b%a)+(j*a) => x-(b%a)=j*a => (x-(b%a))%a=0 , as j*a%a=0
 » 6 months ago, # |   0 Should E really pass in $O(nlogn*20)$? I did write a solution which passes but with a high execution time. Can someone hack it?
 » 6 months ago, # |   0 Did anyone observed precision handling error in python in question 3
•  » » 6 months ago, # ^ |   0 Yeah, got a WA on test 3...
•  » » 6 months ago, # ^ |   0 Yes — do use from decimal import Decimal to handle floating point numbers with higher precision in Python.
 » 6 months ago, # |   0 What's the approach for E?
•  » » 6 months ago, # ^ | ← Rev. 4 →   +4 Observation 1: if you're going to pick X messages, it's obviously optimal to choose the mi such that sum(min(ki,X)) is maximised (why? consider how you would write the expectation calculation as an equation). So the first thing we want to do is sort the messages by the sum of ki values assigned to that value of mi.Observation 2: it's never optimal to go beyond 20 messages (or, more specifically, max(ki) messages). Why? Suppose we have exactly max(ki) messages. Then our expected value is E20 = sum(ki)/20 for the users whose messages are in this set of 20. If we add another message, the expected value E21 = sum(ki_prev)/21 + sum(ki_21)/21 = E20*(20/21) + sum(ki_21)/21. Suppose E21 > E20. Then we have sum(ki_21)/21 > E20*(1/21) = sum(ki_prev)/(20*21), and hence sum(ki_21) > sum(ki_prev)/20. This means that the 21st message has a greater sum of ki values than the mean of the first 20. But this is impossible because the 21st message has a sum of ki values less than or equal to the first 20 values.So it's proven we will never go beyond 20 messages. Now we just try all possible values from 1 to 20, and find which gives the greatest expectation. There's a tricky nuance (which I believe I got wrong in contest) where you have to sort each time according to sum(min(ki,X)), rather than just sorting according to sum(ki).Code
•  » » » 6 months ago, # ^ |   +5 And you don't even have to make the second observation, I, for one, completely missed it. You can just sort all E20 highest to lowest and check all prefixes of this order.
•  » » » 6 months ago, # ^ |   0 I Was looking for this proof precisely, Thank You for the clear explanation !
 » 6 months ago, # |   -6 who wants to be my friend? round was goooooood_)
 » 6 months ago, # |   +3 How to solve C?
•  » » 6 months ago, # ^ |   0 You can use binary search method in which search space is 1 to 2*k-1. For any i>=1 if its possible to send message then any j where 1>=j
•  » » » 6 months ago, # ^ |   0 Why the answer is not min(x,2*k-1)?
•  » » » » 6 months ago, # ^ |   0 Problem asked the line number in which count of message if greater than or equal to x.
•  » » » » » 6 months ago, # ^ |   0 https://codeforces.cc/contest/1612/submission/136463493 i tried in O(1) using alot of maths in copy i got equation but it gave wa in tc 2 can anyone figure out mistake or tell same solution as i wasnt able to come up with binary search approach
•  » » 6 months ago, # ^ |   0 for me i change that problem to math and solve the quadratic equation
 » 6 months ago, # | ← Rev. 2 →   +4 Regarding this submission: https://codeforces.cc/contest/1612/submission/136484148If I'm not wrong, it's complexity is clearly $O(t * 10^6)$ for cases which results in -1 -1. So, it must exceed the given time limit easily (as $t \leq 3000$), but on Custom Invocation I have tried and it runs in $\sim 1500$ ms.Can anyone kindly explain me why it is so?
•  » » 6 months ago, # ^ |   +4 Because 3e9 operations can be fast enough
 » 6 months ago, # |   0 How to solve F?
 » 6 months ago, # |   +2 Can someone explain their approach to Problem D
 » 6 months ago, # |   +5 What's the hack case on E?
 » 6 months ago, # |   +7 Here are the video Solutions to the first 5 Problems In case you are interested.
•  » » 6 months ago, # ^ |   +1 Thanks for the video editorial found it very helpful, especially for D!!
•  » » 6 months ago, # ^ |   0 Great Explanation
 » 6 months ago, # |   +3 Thanks for the good sample tests to avoid overflow in problem C.
 » 6 months ago, # |   +3 Here's a heuristic solution for problem F: https://codeforces.cc/contest/1612/submission/136557294The idea is that it's generally much better to replace the smaller number to increase our power quickly (which greatly overpowers any gain from synergies), but for small values this might not be the best option. We take all possible choices for the first 6 moves, and then apply the following: If $x$ or $y$ is already maximized, then replace the other. If one of $x$ or $y$ can be maximized on the next move, then do that. Otherwise, do whatever will increase power the most. This passes all test cases but I highly doubt it is correct, and would welcome a valid hack.
 » 6 months ago, # |   +37 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
 » 6 months ago, # |   0 I panicked in this contest and lost a bunch of ratings. My biggest drop yet (-100). I couldn't even solve A. Is there anything I can do to get a better grip of my nerves in a contest and not panic when I see an implementation heavy or math problem in the contest?
•  » » 6 months ago, # ^ |   +11 Keep participating in contests
•  » » 6 months ago, # ^ |   -13 do not make submission and you will not lose rating
 » 6 months ago, # |   0 164 pretests in E and still they do not have tc that fails the most obvious wrong solution)
•  » » 6 months ago, # ^ |   0 Now you can still HACK others, right?
•  » » » 6 months ago, # ^ |   +5 Yeah, purple+ can uphack for 7 days after round end iirc
•  » » » » 6 months ago, # ^ |   0 I don know that!Thank you.
 » 6 months ago, # |   0 What kind of time of sending tutorial is normal? Looking forward to the solution.QWQ
 » 6 months ago, # |   -13 who made this fucking problem write in the comments!
 » 6 months ago, # |   -12 My solution coincides with another user know what can i do ?
 » 6 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 6 months ago, # | ← Rev. 2 →   +20 I received a System mail saying that my solution 136459207 matches with idkmyname_ submission 136471505. I believe this is because we both have used nor's publically available BigInt library I had also put this link as a comment in my code, as one should do while copying third-party code. MikeMirzayanov please look into this
•  » » 6 months ago, # ^ |   +23 I'll revert the punishment
•  » » 6 months ago, # ^ |   +3 Please look into this matter MikeMirzayanov
•  » » 6 months ago, # ^ |   0 why does this kind of coincidences always happens to indians?
•  » » » 6 months ago, # ^ |   +3 At least compare my solution with others before demeaning India or its coders.
•  » » » » 6 months ago, # ^ |   0 yesyou just changed the names of the variablesjust another dirty indian still lying after being caught
•  » » » » » 6 months ago, # ^ |   +3 Yes Sir It was my bad to argue with you. You are absolutely correct! :)Though your mind is still filthy like your DP.
•  » » » » » » 6 months ago, # ^ |   0 ohno i smell dead bodies!!did you took a bath in the Genzies river today?
•  » » » » » » » 6 months ago, # ^ |   +3 Haha Nothing like that existsDon't even know the names of rivers. Poor boy
•  » » » » » » » » 6 months ago, # ^ |   0 its the river that all indians uses as a toilet and throughes away dead bodies and drinks from it
 » 6 months ago, # | ← Rev. 3 →   0 I have received a mail from the system stating that my code for 1st,2nd, 3rd and 4th question coincide. First question, was easy it was simple geometry question, so same thinking can be possible. In the second question, I have used visited array(bfs type approach) which can come in many peoples mind and as it's an algorithm so coincidence in code can happen. For 3rd question I have used binary search template which I get from leetcode I have to write check(condition function) function so it may be possible many people are using that template. For the 4th question, I have used swapping and modulus to check whether the number is x-magic pair or not, which can come in many people's mind. I have not used any public Ide, I have used vs code in the contest. MikeMirzayanov, please consider it, I have not copy or share my code anywhere, It is merely coincidence.
 » 6 months ago, # |   0 When will they roll out the rating for this contest?
 » 6 months ago, # |   0 MikeMirzayanov I got an email from the system that one of my solutions for this round coincides with many others. Although I still can't understand why it happened;The main concern is that All the problems for this contest were skipped from evaluation but still, my rating went down by -108. If the contest was skipped; shouldn't the rating neither increase nor decrease?Please look into it and return my rating like before this contest. Thank You
•  » » 6 months ago, # ^ |   0 that's because it's not the first time that you've cheated.
•  » » » 6 months ago, # ^ |   0 F
 » 6 months ago, # |   0 SOMEBODY HELP! https://codeforces.cc/blog/entry/97183
 » 6 months ago, # |   0 I want to ask question F, if I just think about q=0, does it have the same number of answers as it has the right answer? How long does it take for the Fibonacci number to form Max of m,n
 » 6 months ago, # |   0 Hello everybody. Can anybody tell me what is the main point to solve problem E? Thank you for your answers. Link to the problem. And also thank you for the contest. awoo