Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### vovuh's blog

By vovuh, history, 4 months ago, translation, ,

UPD: The editorial is published!

<almost-copy-pasted-part>

Hello! Codeforces Round #598 (Div. 3) will start at Nov/04/2019 16:15 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

• +157

 » 4 months ago, # |   0 thank you for holding a div3 contest!!
•  » » 4 months ago, # ^ |   +1 Thanks!
 » 4 months ago, # |   -10 I hope the statements will be short and clear and problems will be balanced. Good luck everyone :)
 » 4 months ago, # |   +6
 » 4 months ago, # |   0 How to register unofficially ? I clicked on register, but it only allows for ratings less than 1600.
•  » » 4 months ago, # ^ |   0 I think he means by unofficially after the contest is over, for when it will not be rated.
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 You get a big ugly warning message that you will be registering "out of competition" (i.e. unrated), but you should still be able to click past the agreement and then solve the problems during contest time
•  » » 4 months ago, # ^ |   -8 solve question ...you will be registered unofficially !!
 » 4 months ago, # |   +2 Imagine Vovuh were a super cool meme-lord...then these posts would have had dope memes after the closing bracket and everyone would have literally waited for every Div 3 announcement holding their breath...
 » 4 months ago, # |   -30 I think Vovuh's round better than Pikmike's
 » 4 months ago, # |   0 after a long time div 3 will be held.Thanks to Vovuh!
•  » » 4 months ago, # ^ |   -9 u are welcome! good Luck.
 » 4 months ago, # | ← Rev. 2 →   -13 Nice time.
 » 4 months ago, # |   -14 Let's hope for the best .-.
 » 4 months ago, # |   0 A person with a rating of 1599 can enter the competition but a person with a rating of 1600 cannot This makes the second person fall far behind
•  » » 4 months ago, # ^ |   0 That's what divisions are all about.
•  » » 4 months ago, # ^ |   0 when they allowed people which has rating of 1500 and lower, you said that "a person with a rating 1499 can enter, but 1500 not".
 » 4 months ago, # |   +1 this is my first out of competition contest :)))
 » 4 months ago, # |   -8 I had to wake up on my alarm clock on my day off so as not to oversleep the contest ( -_-)"
 » 4 months ago, # |   -8 I am happy that we don't have to stay up ( qvq
 » 4 months ago, # | ← Rev. 2 →   -8 Hope it to be like previous div2 597 round contest That was really amazing....
 » 4 months ago, # |   +7 i need only 3 points to be pupil ..please
•  » » 4 months ago, # ^ |   +11 it will be hilariously sad if you get only two points
•  » » » 4 months ago, # ^ |   +15 it will be really sad if i getdown !
•  » » » 4 months ago, # ^ |   +11 And he got +2. Really sad
•  » » » » 4 months ago, # ^ |   0 F
•  » » » » 4 months ago, # ^ |   0 F
•  » » 4 months ago, # ^ |   +8 i hope you will get 2 points for this contest ^^
•  » » » 4 months ago, # ^ |   +15 whyyyyyyyyyy
•  » » » 4 months ago, # ^ |   0 for now 1 point (cf predictor) :)
•  » » » » 4 months ago, # ^ |   0 I will get down
•  » » » » » 4 months ago, # ^ |   0 You solved only first problem, this might be a demote
•  » » » » » 4 months ago, # ^ |   0 Hello darkness!, my old friend.
•  » » 4 months ago, # ^ |   +1 It seems that you get 2 points.emmmmmmmmmm That's so interesting
•  » » » 4 months ago, # ^ |   +18 Not interesting anymore i really shocked
 » 4 months ago, # | ← Rev. 2 →   -19 dislike it if yo wanna lose ur rating
•  » » 4 months ago, # ^ |   0 QWQ
 » 4 months ago, # | ← Rev. 2 →   -18 When will the DDOS attack begin?;)
 » 4 months ago, # |   0 i hope this will be a great round
•  » » 4 months ago, # ^ |   0 maybe)
•  » » 4 months ago, # ^ |   0 Yeah.We are all ready for this...We all will give are best..
 » 4 months ago, # | ← Rev. 2 →   0 10 minutes delay returns
 » 4 months ago, # |   +3 Delayed :/
 » 4 months ago, # |   0 I look forward to glory and honor. The competition may begin.
•  » » 4 months ago, # ^ |   +3 My worst contest ever. :/I should have solved all, but did fiddling on B for like two hours. Really loosing the fun of this.
•  » » » 4 months ago, # ^ |   0 me_irl
•  » » » 4 months ago, # ^ |   0 haha true was an easy question but implementation was not quite easy for me
 » 4 months ago, # |   +1 delay 10m?
•  » » 4 months ago, # ^ |   0 Yes
 » 4 months ago, # |   0 Alright, let's do this. I hope to solve atleast 4 questions tonight.
•  » » 4 months ago, # ^ |   0 Good luck to you
•  » » 4 months ago, # ^ |   0 Dang, I was close. Let's hope for next time.
 » 4 months ago, # |   -20 Div.3! Great! Li Linjiang Tian Xia Di Yi!
 » 4 months ago, # |   -29 this was unbalanced one ..
•  » » 4 months ago, # ^ | ← Rev. 3 →   +23 no it was, you think like that only beacuse you did just two problems. Problems were really good!
•  » » 4 months ago, # ^ |   +5 If you swap D and C it's actually relatively balanced, maybe the difficulty between A and B is a bit too wide though.
•  » » 4 months ago, # ^ |   0 In these type of contests you have to keep your mind cool constantly while implementation.
•  » » » 4 months ago, # ^ |   0 I lost my cool on B.
 » 4 months ago, # |   +15 I like that contest.
 » 4 months ago, # |   0 here's no system testing?
•  » » 4 months ago, # ^ |   0 No, in div3 and educational contests tests aren't divided into pretests and tests and there are no hacks during the contest time, so your code runs on all the tests during the contest. After that there's a 12hr hacking phase before the final results are announced.
•  » » » 4 months ago, # ^ |   0 thx!
 » 4 months ago, # |   +2 Does anyone know why a runtime error may occur on 15th test in problem D?
•  » » 4 months ago, # ^ |   +2 k can be up to 10^12
 » 4 months ago, # |   +10 How to solve F?
•  » » 4 months ago, # ^ |   +42 If the strings don't have the same letters, answer NO. If some letter appears at least twice, you can swap those two letters to be adjacent, then swap them in the first string and make an arbitrary swap in the second string, therefore we can answer YES. Now assume duplicate letters don't appear, and consider the strings as permutations.You can do any even number of swaps of adjacent elements to one string without changing the other. Also, every inversion of some intervals either doesn't change the parity of the permutations or changes the parity of both permutations. If the parities are equal, we can make the strings equal with an even amount of swaps, therefore we answer YES. If they are not equal, they cannot be made equal, and therefore we answer NO.Code: 64228071
•  » » » 4 months ago, # ^ |   0 Do you calculate parity in O(n^2) ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 You can do bubble sort and count how many swaps you make or check for every number how many numbers are higher to the left.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +1 parity function will check parity of strings if there is no repeated character. That means length of strings should be less than 26 .It is simple pigeonhole principal
•  » » » » » 4 months ago, # ^ |   0 lol thanx! I did not get that it is only 26 =)
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Number of adjacent swaps can also be calculated in O(NlogN). Although it is not needed here since in that case we have N<=26.
•  » » » 4 months ago, # ^ |   0 "Every inversion of some intervals either doesn't change the parity of the permutations or changes the parity of both permutations."How to prove this ? Which permutation is being selected in both of the strings ?
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   +3 Consider any segment $T$ of a string $S$. There are $3$ types of inversions Both characters in $S$ One in $S$ and one in $T$ Both characters in $T$ Only type $2$ is affected by reversing a segment. If the length of the segment is $L$ and there are $x$ inversions, the number of inversions becomes $L(L — 1)/2 — x$If the first term is even, the parity remains the same. Otherwise, the parity flips.Amazingly, the parity flips based on the length of the chosen segment and not at all on the permutation we use :). This is a mind-blowing fact :)Here are my solutions to this contest and here is my detailed editorial :)
 » 4 months ago, # |   -14 Hello div2! Is that you ?
 » 4 months ago, # | ← Rev. 2 →   +18 B, C & D are easy to come up with the idea, but the implementation is not trivial, I don't like these kind of problems.
•  » » 4 months ago, # ^ |   +6 Just get the indexing right, again and again and again. Boring and frustrating.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Honestly, very boring
•  » » 4 months ago, # ^ |   0 Problem A? Implementation is not trivial ?
 » 4 months ago, # | ← Rev. 2 →   +8 I submitted problem C with MS Visual 2017 compiler (I use Visual Studio 2017), and it gave me WA on the 2nd test case while it's working on my computer and on GNU compiler, I got AC with the same code after the contest.with MS C++ 2017with GNU C++ 2017So I think something is wrong with MS C++ 2017 compiler.
•  » » 4 months ago, # ^ |   +1 You might be doing something that's undefined behavior
•  » » 4 months ago, # ^ |   +1 Yep, undefined behaviorClang++17 Diagnostics says: p71.cpp:12:7: runtime error: index -1 out of bounds for type 'int [1001]' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:12:7In a[qan - 1] when qan is 0
 » 4 months ago, # |   0 Is a solvable with binary search?
•  » » 4 months ago, # ^ |   0 Ternary search if you want
•  » » » 4 months ago, # ^ |   0 How? Can you explain a bit? :) Also why Binary search can't works. Thanks :)
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 It seems ternary search works.
•  » » 4 months ago, # ^ |   0 It can be solved in O(1) time. 64209894
•  » » » 4 months ago, # ^ |   0 I need the bimary search solution.
•  » » » » 4 months ago, # ^ |   0 I used binary search
•  » » » » » 4 months ago, # ^ |   0 Can you explain your solution a bit? :) Thanks :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Binary search on the number of coins of value n. So lower_limit = 0, upper_limit = aif mid*n > total then upper_limit = mid — 1else find the number of coins of value 1 (total-mid*n). If this value is <= b then "YES" else lower_limit = mid + 1 Code : 64218027
 » 4 months ago, # | ← Rev. 2 →   0 How to solve B?
•  » » 4 months ago, # ^ |   0 use greedy and keep array of positions where you swapped.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 I did exactly this and somehow messed up lol.LOL I should've just added check if I actually need to swap elements
•  » » 4 months ago, # ^ |   0 Set range_begin to be the beginning of the vector. Endless loop 2.1. Find the minimum number (mn) and its index (mn_i) in a range [range_begin, vector_end) 2.2. Print the mn 2.3. If mn_i is in the end of the vector (i.e. vector_end - 1), then loop is done 2.4. Else if mn_i is equal to range_begin, then range_begin++, since you've just printed this number 2.5. Else print all the numbers in vector in range [range_begin, mn_i - 1), swap numbers at positions mn_i and mn_i - 1, set range_begin to mn_i The idea behind this is that since you can only perform 1 swap for each index, it means you can carry to the first position the minimum number in the list, and then you'll have only swaps in range [mn_i, vector_end], thus find the minimum in this range and use some swaps to carry this miminum as much as you can. Repeat until you've no swaps.
 » 4 months ago, # |   +27 MikeMirzayanov Just a little suggestion from me, could you add contest timer in m1 / m2 site during the contest? I know that you can estimate the remaining time yourself, but it could be more convenience (at least for me) to see the timer directly. Thank you.
•  » » 4 months ago, # ^ |   0 Me too.
 » 4 months ago, # |   +5 If you hack something, will this give you points?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +1 No. Not for Div 3s and Educational Rounds where it is open hacking. But best hackers for opening hacking will be featured in the blog post.
 » 4 months ago, # | ← Rev. 2 →   0 Great Contest. Thanks for this round. Clear Statements! Keep up the good work.
•  » » 4 months ago, # ^ |   0 B to D, greedy. Not that standard. D could be harder.
 » 4 months ago, # |   +5 I couldn't access codeforces last 20 minutes. Did anyone have a same problem? I confirmed some of Japanese contestant couldn't.
•  » » 4 months ago, # ^ |   +1 use lightweight sites (m1.codeforces.com) (m1/m2/m3)
•  » » 4 months ago, # ^ |   +1 yeah. I faced this for half an hour.
•  » » 4 months ago, # ^ |   +1 Yeah, my fellow Indian contestants and I were also not able to access the contest, but it was accessible using m2.codeforces.com
•  » » » 4 months ago, # ^ |   0 I accessed with m1.codeforces.com. But, you can't say the current standings.
•  » » » 4 months ago, # ^ |   0 Actually, I couldn't reach codeforces even the contest is end. but, I found that some of discussion was posted when we couldn't access codeforces. whats going on!?
•  » » » » 4 months ago, # ^ |   +1 That I didn't know before, I guess it must have been a problem for us Asians only.
•  » » 4 months ago, # ^ |   +1 I had same problem and I thought this contest would be unrated. I tried to access another web site but unfortunately I forget my password. Zzz
 » 4 months ago, # |   0 LOGIC OF A:- Check for largest multiple of n just below S and then check how many coins are required for it if(it is less than available coins then it is case 1:- now m=((s/n)*n)/n; if(a>=m) { j=s-k;//final money left to pay after making payment with type n coins } else { l=a*n; j=s-l;//final money left to pay after making payment with type n coins } Now final Answer is  if(j>b) cout<<"NO\n"; else cout<<"YES\n"; } Now for B the following is a big hint SpoilerNow we need to check in every pass minimum value in between a particular set of indices i to n and place it at front at i and shift each value one step beyond.... for example we have 5 4 1 3 2 now when we traversed for first time we got minimum value as 1 and at index 2 so we swap indices 2 and 1 then indices 1 and 0 to get 1 in front then in another pass we will start from indices 2 to indices n and then find the minimum again as at index 4 then we will swap indices 4 and 3 then indices 3 and 2 to get the final array 1 5 2 4 3 to satisfy the condition that no two indices can be swapped again.Now FINAL D //C I DON'T TRIED hint for DTHIS PROBLEM is almost similar to B but there it is constraint on the value of total swaps but no condition to swap same indices at most once ,SO really this was pretty much simpler then B because what we were required is to get as many 0s in front as possible first I searched whole array and kept track of indices of all zeroes ,now just take as a variable current denoting position and put zeroes in forward of ones until k is greater than 0 for the last 0 that can be shifted find how much values it can come forward with the help of remaining K
 » 4 months ago, # |   0 greedy and greedy. C and D would have been more classical.
 » 4 months ago, # |   0 Some swapping problems! I like problem D.
 » 4 months ago, # |   0 How to solve problem E. I can't get any idea.
•  » » 4 months ago, # ^ |   +7 Okay, My approach is , first of all sort the array. Now we have to split the array into such sub-segments that each segment is consists of at least 3 numbers. Now, Let our answer be ans. At first we can say that ans = arr[n-1]-arr[0] . Now for each valid splits in position i, we can improve our answer by arr[i]-arr[i+1] . we have to find a set of such i, that summation of all arr[i]-arr[i+1] is as lowest as possible. Let it be Sum . So , our final answer will be , ans= arr[n-1] — arr[0] + Sum . How do we find such Sum ? Just used dp on every i where i>=2 && n-i<=3
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 I did it like this- First sort the array Now the obervation is that each segment would of atleast length 3 and atmost length 5. It makes sense because if we have a segment of length 6 then we can split it into two segments of 3 and we are sure to get the smaller sum because the array is sorted.now we can use dp , here dp(i,j) is the min cost if we have a segment of length j ending on ith index. Of course only 3 values of j are possible. Since you could not get idea, I am not writing the complete equations and mentioning only the state. You can look at my solution if you want.ps: I hope this passes the sys tests too.
•  » » » 4 months ago, # ^ |   0 Thanks. I got it..
•  » » » 4 months ago, # ^ |   0 Very nice observation. :)
•  » » » 4 months ago, # ^ |   0 Thats a great observation!
 » 4 months ago, # |   +11 A very nice lexicographicallySmallestForces contest!
 » 4 months ago, # |   0 Codeforces was not opening for the last 45 mins, and I literally thought there has been a DDoS attack,for which I left doing the contest.
 » 4 months ago, # |   +1 Anyone please tell me what's wrong with my code 64271656 for problem B?
 » 4 months ago, # |   0 can someone please explain problem E dp state and transition
•  » » 4 months ago, # ^ | ← Rev. 2 →   +4 First, Sort array $a$ in increasing order. Each team contains at least 3 members and you want to minimize the total diversity of all teams. So, there is no reason to build a team more than 5 members because you always can split the teams (>5 members) into smaller teams and reduce the diversity. Now, you can solve problem with DP technique in linear time.Let $dp(i)$ be the minimal total diversity of the school which consists of first $i$ members.Transition: $dp(i) = max \begin{cases}dp(i-3) + a[i] - a[i-2] \\dp(i-4) + a[i] - a[i-3] \\ dp(i-5) + a[i] - a[i-4]\end{cases}$Base case: $dp[1] = dp[2] = Infinity$ $dp[3] = a[3] - a[1]$ $dp[4] = a[4] - a[1]$ $dp[5] = a[5] - a[1]$ Run transition to calculate $dp[i]$ with $6 \leq i \leq n$.The answer is $dp[n]$. You can construct the configuration by yourself.
 » 4 months ago, # | ← Rev. 3 →   0 I can't find my mistake... where is "wrong answer each team should consist of at least three students"??? https://codeforces.com/contest/1256/submission/64279213 It was incorrect teamcount....
 » 4 months ago, # | ← Rev. 2 →   0 In problem E, I came up with the solution using DP but I can't construct the configuration in time =)))
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 you can construct the configuration after getting the answer, by checking all the state from dp[n] to dp[1],details can be referred to my code.
•  » » » 4 months ago, # ^ |   0 Thank you, I will check your solution.
 » 4 months ago, # | ← Rev. 2 →   0 Waiting for system test to become blue again... Edit:FST on C..weak pretests..to be more careful next time..
•  » » 4 months ago, # ^ |   0 me too,,,, but it doesn't seem to be system testing.
•  » » » 4 months ago, # ^ |   0 Waiting to be specialist. But, system testing is going on and on.......
•  » » » » 4 months ago, # ^ |   0 Not today
•  » » » » » 4 months ago, # ^ |   0 haha.
 » 4 months ago, # |   +10 In problem C I wrote `p+d
•  » » 4 months ago, # ^ |   0 Yeah, really bad pretests in this contest !
 » 4 months ago, # |   0 congrats. system testing is done
•  » » 4 months ago, # ^ |   0 It's not going to be done today. haha
 » 4 months ago, # |   0 I solved 4 questions in contest and 2 of them failed system testing ! Why are the pretests so weak !!! And that too for a Div3 round this is not how it should be, I understand that while coding one should consider all cases but shouldn't that be tested in Div2 then?
 » 4 months ago, # |   +4 It's the first time I become Expert, I'm so happy now =)))
•  » » 4 months ago, # ^ |   +3 Congrats
 » 4 months ago, # |   +1 How could a O(n^2) solution passed for F? I don’t get it. Please someone explain it to me. TIA.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +3 Well, if string has 2 or more equal letters in it, then the answer is YES. In other case the length of string is not more then 26
•  » » » 4 months ago, # ^ |   0 Thanks man. I got it.
 » 4 months ago, # | ← Rev. 4 →   0 I have a doubt regarding the problem "Minimize the Permutation". My approach was that I iterate from 1 to n and try to bring the smaller elements(from 1 to n) forward, and do the same for next element if, I have either brought my current element(say i) to the 'i-1'th position or I could not swap it anymore(to bring to a lower index) for that I maintain a 'swapped' vector.But, my solution didn't work because I didn't add the condition "arr[j-1]>arr[j]" for the while loop(i.e we have to swap only if the element on the left is bigger). And works fine if I add it. Can you please help me understand that why do we need to add this condition, is it not obvious? Can someone please explain to me with a small test case?This doesn't work. This works.
•  » » 4 months ago, # ^ |   0 Yes bro , I have experienced same issue. Can anyone please explain the above with a small test case ?
•  » » 4 months ago, # ^ |   0 consider the case: 4 4 2 1 3
•  » » » 4 months ago, # ^ |   0 But that is not a valid permutation according to the question. Read it again.
•  » » » » 4 months ago, # ^ |   0 the permutation is [4, 2, 1, 3]. The first 4 is the size, and my line-breaks were eaten. After the first iteration of the number 1 and number two, it is ok that the sequence turns to [1, 4, 2, 3]. In the second iteration, 2 will not be moved because there has been a swap in the first iteration. It gets into trouble when a new iteration of the number 3. 2 and 3 would be swapped if you do not compare them, and the result would be [1, 4, 3, 2].
•  » » » » » 4 months ago, # ^ |   0 Thanks bro!