Codeforces Round #787 (Div. 3)

Hello! Codeforces Round #787 (Div. 3) will start at Thursday, May 5, 2022 at 14:35UTC. You will be offered 6-7 problems 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 a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-7 problems and 2 hours and 15 minutes 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 participant of the third division, you must:

take part in at least five 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 our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, SixtyWithoutExam, me Vladosiya.

Also many thanks to avevad, yorky, UncleSema, vsinitsynav, GoracioNewport, Tvorozh0k, any_nickname, I.AM.THE.WILL and Jostic11 for testing the contest and valuable feedback.

Good luck!

• 2 days ago, # ^ | Can you explain what happens if pretests are weak? I'm new in Codeforces and exploring the rules.

  • 2 days ago, # ^ | Test cases which are used to check your solution during contest are pretests; subset of the actual test cases.So sometimes it happens that the solution pass the pretests but it's actually wrong.

    • 2 days ago, # ^ | Thank you so much for such a clear answer!! <3

  • 43 hours ago, # ^ | Because there are too many hacks in codeforces round 786，especially problem E

• 2 days ago, # ^ | Yeah,hope I will get to 700 after this contest!

  • 2 days ago, # ^ | All the best .

    • 2 days ago, # ^ | And to you. By the way, I want to ask,how are you able to send to messages in ten minutes?

      • 29 hours ago, # ^ | Just watching the notifications

• 2 days ago, # ^ | Such as me,and I hope all the young coders will get a good mark in this contest and be benifited.And best luck to all the coders!

• 2 days ago, # ^ | Good one dud. But if you are serious, try AKing a Div2 round or smth because it is virtually impossible to go from pupil to CM in one Div3 round.

• 9 hours ago, # ^ | My 3th contest! Good luck!

• 42 hours ago, # ^ | Yeah,participating in contests isn't just to increase your rating.What you must do is to learn more in the contsets,be honest,no cheating,and try your best!

• 2 days ago, # ^ | Hoping to reach Newbie! tourist

  • 39 hours ago, # ^ | When rating is calculated modulo 4000

    • 4 hours ago, # ^ | I suggest to modulo 4001 because it's a prime number.

• 2 days ago, # ^ | sir waht an abmitious goal! good luck!!1! next target is newbie????

• 2 days ago, # ^ | Unrated

• 44 hours ago, # ^ | I think you should cancel registeration and register again.

• 4 hours ago, # ^ | do you expect a more-than-1000 hacked problem?

• 39 hours ago, # ^ | Pray for upvote.

• 17 hours ago, # ^ | Same templates != plagiarism *Maybe they are learning from one sensei

  • 15 hours ago, # ^ | Look at commented code.

• 7 hours ago, # ^ | It's score distribution, not difficulty. Also, Div3 rounds do not have score distribution.

• 6 hours ago, # ^ | Bro how can everyone get a good rank?

• 6 hours ago, # ^ | Happy birthday Serval!

• 4 hours ago, # ^ | Happy birthday and wish you good luck in this round!

• 3 hours ago, # ^ | how did you solve it it's giving me TLE and I don't know why

  • 3 hours ago, # ^ | its infinite loop because you don't break when the element equals to 0 and keep divide by 2

    • 3 hours ago, # ^ | try this 3 2 2 2

      • 3 hours ago, # ^ | working gives 3

        • 3 hours ago, # ^ | ← Rev. 2 →   0 oh sorry i didn't try it in my ide but try this 3 3 0 0 0 first line is number of test cases + there is another bug in your code the loop should start from n — 2 not from n — 1 since you don't need to do anything for the last element edit : just realis you use 1 based index ignore the last line

          • 3 hours ago, # ^ | this gives -1 as well and I'm putting numbers on index 1 to n on the input loop so the last element is n and i'm using n -1

            • 3 hours ago, # ^ | ← Rev. 2 →   0 no way bro i tried your last submission and its goes in infinite loop with the above input i really don't know how its works in your side but i would advice you trying codeforces custom innovaction you didn't handle the case when you need to reduce the number and its already 0 as the case in the above if you still have a problem i can discuss it with u on talks edit : to be clear this is the submission i am talking about https://codeforces.com/contest/1675/submission/155987477

              • 3 hours ago, # ^ | i feel i am stupid i could show that easily by running it in ideone here the link: https://ideone.com/MEZYNY as i said before you need to handle when you can't divide anymore

• 3 hours ago, # ^ | ← Rev. 2 →   0 can you share your approach

• 3 hours ago, # ^ | ← Rev. 2 →   0 ?1?? This Tc give 3 I get this 45 min before end of the contest.

• 3 hours ago, # ^ | My solution was O(nm2)O(nm2)

  • 3 hours ago, # ^ | I use dp[total number][last number] as status. How to improve?

    • 3 hours ago, # ^ | Convert the array aa into array bb where aiai is the frequency of ii. Then, the dp state should be (current_index, number of sections, length of section ending in the current_index). Submission (sorry for the bad explanation, hope you can understand from my code)

    • 3 hours ago, # ^ | ← Rev. 3 →   0 Let p[i][x][y]p[i][x][y] be the minimum of dp[i][x][1]dp[i][x][1] to dp[i][x][y]dp[i][x][y], and papa be the prefix sum of aa. Then dp[i][x][y]=p[i−1][x−y][y]+abs(pa[i]−y)dp[i][x][y]=p[i−1][x−y][y]+abs(pa[i]−y). Note that yy is not greater than n/in/i when enumerating, so the final time complexity is O(nmlog(m))O(nmlog⁡(m)). Here is my code: 156012337

      • 3 hours ago, # ^ | I guess I implicitly used the n/i condition so it is reduced to O(NM^2logM) at least.

        • 77 minutes ago, # ^ | I had an idea to do, like reverse the then problem will turn into minimum operations to make a non decreasing array then apply slope trick Optimization.. something like that. Is it possible ?

• 3 hours ago, # ^ | a common idea in problems where you increase a[i]a[i] at the cost of a[i+1]a[i+1] or a[i−1]a[i−1] is to consider prefix sums/suffix sums. in this problem, consider the prefix sum array pref[]pref[]. Each move of type a[i+1]a[i+1] to a[i]a[i] increases pref[i]pref[i] by 11, and leaves all other values unchanged. Similarly, a[i]a[i] to a[i+1]a[i+1] decreases pref[i]pref[i] by 11 and leaves everything else unchanged. Converse is also true: every increase/decrease of pref[i]pref[i] corresponds to some move in the original array. [for i<ni<n , since pref[n]pref[n] remains same]. So problem is transformed to one operation which increments or decrements an index of the prefix array. Then you get the necessary and sufficient condition CC: a[i]≥a[i+1]⟺pref[i]≥2∗pref[i−1]−pref[i−2]a[i]≥a[i+1]⟺pref[i]≥2∗pref[i−1]−pref[i−2]. Then you can define dp[j][j1][j2]dp[j][j1][j2] to be the minimal cost to convert pref[1...j]pref[1...j] so that pref[j]==j1pref[j]==j1 and pref[j−1]==j2pref[j−1]==j2, then you can figure out the states using condition CC.

  • 3 hours ago, # ^ | Oh I got it. Thanks

  • 3 hours ago, # ^ | ah, I saw a problem recently that used this idea. Still, I couldn't remember it during the contest. Explains why I am still blue :(

• 3 hours ago, # ^ | ← Rev. 3 →   0 you will go into dead loop when both numbers are 0

  • 3 hours ago, # ^ | I don't think I understood what you meant to say. Can you please give an example?

    • 3 hours ago, # ^ | Try 3 2 2 2

      • 3 hours ago, # ^ | It's printing -1. I think that's the correct output right?

        • 3 hours ago, # ^ | How about 0 0 0?

    • 3 hours ago, # ^ | 0 0 3 will result in infinite loop

• 3 hours ago, # ^ | https://codeforces.com/contest/1675/submission/156012745 modified your code to get accepted. it was stuck in a loop when both numbers are 0 since dividing 0 will also yield 0 it goes on forever

• 2 hours ago, # ^ | So true

• 111 minutes ago, # ^ | It seemed hard but it was a fun question to think of. So I was stuck to it and solved it.

• 3 hours ago, # ^ | ← Rev. 2 →   +1 your observation is correct. You just have to go from s(0) to s(n-1) in order and converting characters to lowest possible conversion at that point, you just have to maintain an array of size 26 to check how many characters you have already converted you can check one of the way in my solution :

  • 2 hours ago, # ^ | Can you please explain the main logic. I mean the lowest possible conversion at that point means what ? Third part I understood that like if suppose 7th char was 's' and we did the calculation for it's conversion then if we get 20th or any further char again 's' then we will simply ignore that since 's' calculation is already done

    • 2 hours ago, # ^ | suppose n = 5, k = 4, string = cgdfb, c -> a g -> e (thats the best conversion for this stage) d -> d(there is no conversion possible as k is used up) f -> e b -> a thats what i meant if k was 6 you could convert g -> c -> a

      • 99 minutes ago, # ^ | Thanks, I understood now..I have to use already converted char value afterwards also..like if string is "ek" then ( e-> a in 4 moves & k->e in 6 moves & we already have e->a before so we will ignore this so total 10 moves for "ek" to "aa"...)..Thanks :)

• 3 hours ago, # ^ | cheaters?

  • 3 hours ago, # ^ | I don't think so, maybe we are missing out on something easy observation.

    • 2 hours ago, # ^ | I solved A-E, and short 10 minutes to submit F. This contest is harder than previous div3, but judging from the number of AC submission, I'm sure there are a tons of cheaters.

      • 2 hours ago, # ^ | Exactly . There is no way 7000 ppl would solve C and only 2500 solves on E. It's all because of cheaters.

        • 105 minutes ago, # ^ | C has fairly simple observations. There is a prefix of 1s, a postfix of 0s. So the thief is between (including both) the last 1 and the first 0.

      • 95 minutes ago, # ^ | I don't think the contest was tough, Problem A : Implementation Problem B : Start from back Problem C: prefix should not have any '0' and suffix should not have any '1' Problem D: Basic dfs Problem E: Just do whatever is written, decrease current character as much as you can Problem F: I have seen these types of problems many times, fix the root and then every required edge will be visited twice except between the path from x to y (So, basically again a normal dfs with some basic dp involved) Problem G: It involved a nice DP, but it's fine, the last problem can be on the tougher side. Problems were of the same level as of a normal Div3 contest.

      • 81 minute(s) ago, # ^ | ← Rev. 2 →   +4 I didn't mean the questions were tough. I meant it should have smaller ACs compared to previous Div3. Also recently there are people who uploaded solution on YT mid contests. I don't see why it wouldn't happen again.

• 3 hours ago, # ^ | true! lol , I spent around like 40 min on this question but still didn't get how the test cases are working , so I solved A , B , D , E

• 3 hours ago, # ^ | Problem D implementation was difficult. But the idea was simple. Problem C implementation was super easy. But getting the idea was very tough.

  • 109 minutes ago, # ^ | Can you explain your idea for problem D. I was getting TLE

    • 87 minutes ago, # ^ | Steps: Find the Leaf nodes Hint Create a map to store the parent nodes of each of these leaf nodes. For each of these leaf nodes, put it's parents in the map Starting from the leaf node, navigate till the parent (using DFS), and store the list of integers Make sure that you don't add already visited values (as it is mentioned that each vertex belongs to exactly one path) Loop through all these items in this map, and print the parent nodes in reverse order. We are reversing this because, it is mentioned that paths always lead down. My Submission — 155988440 There could be some other simpler solution. If anyone else can comment on this thread, on how this can be improved, that would be great.

    • 80 minutes ago, # ^ | determine the root vertex first. it's easy, because it's the only one vertex with a[i] = i. then run dfs from the root and start writing the path to an array, and we end the path if and only if we came to the leaf node (there is no way to continue it). So, we return current path to the main function and do same thing again unless all vertices are visited. sorry for my poor english :P Here is the implementation https://codeforces.com/contest/1675/submission/156019404

• 3 hours ago, # ^ | answer is pretty simple, I think most people guessed it right instead of knowing how it passed

  • 2 hours ago, # ^ | you mean problem C?

  • 2 hours ago, # ^ | answer : pos(first(0)) — pos(last(1)) + 1

• 2 hours ago, # ^ | solved C in 10 min and didn't try to solve D banging my head hard on B all the time thinking it shouldn't be that tough and finally solved only 2 :( I even tried solving in O(n) but turns out brute force will work just with few corner cases

• 3 hours ago, # ^ | It will time out eventually Think of on the ideas of dp

• 3 hours ago, # ^ | You may choose visiting order. So this solution is wrong even not TLE.

  • 3 hours ago, # ^ | ← Rev. 2 →   -10 But the algorithm I mentioned will give the correct answer, no?

• 104 minutes ago, # ^ | I am not sure if I can explain better than the problem description. We have to make the given string lexicographically minimum, by performing the given operation maximum k times. Operation: Choose any character in the String, and replace all of it by the previous character. For example, replace all 'c' with 'b' or replace all 'a' with 'z'. For String cba with k=2, we can perform 2 operations as below. cba -> bba -> aaa Note: Checking the test case below might be considered as a HINT. 3rd Test Case steps

  • 93 minutes ago, # ^ | thanks a lot

• 2 hours ago, # ^ | Can you please explain to me the test cases for C, I couldn't even understand how the test cases are working! May be I am getting something seriously wrong on this problem, for test case -> ? ? 0 ? ? how the answer is 3? Should it not be 5?

  • 2 hours ago, # ^ | first and second one maybe the theif third one as well but the fourth and fifth can't be since the painting was already missed when the third one reported if he tell the truth and if its wasn't missed that means third one is the theif and also fourth and fifth one can't be the theif sorry for my bad english

  • 2 hours ago, # ^ | 3rd person says that there is no picture in the room. so the only possible thieves will be 1st,2nd, and 3rd one

  • 2 hours ago, # ^ | ? ? 0 ? ? We only have information from the third person Either someone stole the painting before they entered the room (0), or they are the thief (and are lying). Therefore the thief must be one the first 3 people

    • 2 hours ago, # ^ | oh yeah, that's right once 0 is said it means that he is either lying or telling the truth. So overall I just have to check before how many '?' marks I have until 1 appears. Now this '1' can also be a victim so we have to include '1' too! This problem was nice! Thanks man!

  • 2 hours ago, # ^ | If friend 3 was the thief and lying, the painting was definitely taken then so it would not be there for 4 or 5. If friend 3 was honest, the painting was taken by friend 1 or 2 (it had already been taken) so it was definitely taken before 4 or 5 came.

    • 2 hours ago, # ^ | yep! I messed up my contest for this 1 problem :p though its a nice one!

  • 2 hours ago, # ^ | Apart from the existing comments, let me try to explain how I interpreted this problem C for Testcase ? ? 0 ? ?. May be it helps someone. If 1st person is thief : persons 2,4,5 can't remember — so, no issues person 3 didn't see the picture — which is true VALID If 2nd person is thief : persons 4,5 can't remember — so, no issues person 3 didn't see the picture — which is true VALID If 3rd person is thief : person 1,2,4,5 can't remember — so, no issues VALID If 4th person is thief : person 1,2,5 can't remember — so, no issues person 3 didn't see the picture — which becomes a false statement which makes that 4th person is not the thief. So, INVALID. If 5th person is thief : person 1,2,4 can't remember — so, no issues person 3 didn't see the picture — which becomes a false statement which makes that 5th person is not the thief. So, INVALID.

• 2 hours ago, # ^ | will you please share the approach to the problem F

  • 87 minutes ago, # ^ | My approach is as follows. Consider a rooted tree with root in xx. Let important vertices be the ones that we will have to visit. First, mark the input vertices as important, and also the vertex yy. Now, a vertex is important if it is marked or at least one of its children is important. This characteristic can be found recursively with a single DFS. So, we got a subtree TT of the original tree: we have to visit every vertex of TT, and don't have to go anywhere else. Now, think what would we do if we had to return to xx in the end. Naturally, we would traverse each of the edges of TT exactly twice: once going from the root and the second time going back. Remember now that we don't have to return to xx, just end up at yy. Naturally, we will consider a path that ends up moving from yy to xx, and then omit that last part. The number of steps is therefore twice the number of edges in TT minus the distance from xx to yy. To me, the beauty of the problem is that some parts above can be omitted, leading to more and more tedious (but still quite working) solutions. So, the participant has a choice to either start implementing what they have, or ponder more to maybe cut out quite a bit of work. If a solution needed all of the above to pass at all, that beauty would have been lost.

• 86 minutes ago, # ^ | Me after solving C Spoiler

• 2 hours ago, # ^ | Probably running out of stack due to recursion? Test 7 appears to be a single path with every node on it.

  • 2 hours ago, # ^ | I thought so too, but here is my submission with increased recursion limit, but got the same. https://codeforces.com/contest/1675/submission/155959621

    • 119 minutes ago, # ^ | That just stops python giving a recursion limit error, you can still run out of memory and crash.

      • 112 minutes ago, # ^ | ← Rev. 3 →   0 "you can still run out of memory and crash" That yields a "Memory Limit Exceeded" (e.g.): https://codeforces.com/contest/1675/submission/155991461 Which is different from the "Runtime Error" in the submission shared by khanter_

        • 61 minute(s) ago, # ^ | This works: https://codeforces.com/contest/1675/submission/156020448 I added a generator function called bootstrap. This takes a recursion and processes it as a stack instead. It's extremely useful in python for large N recursion problems. I use C++ now but when I used python I always used bootstrap for recursion and strongly advise you to do the same.

          • 9 minutes ago, # ^ | Got it, thanks a lot!

• 51 minute(s) ago, # ^ | Depends on what else we have before and after '0'. Give more detailed information/sample, please

• 40 minutes ago, # ^ | Before 0, if any ? occurs, he/she will be considered as Thief. Anything after 0 is only not considered as thief. Answer for ???????000 is 8. (Only last 2 person can't be considered a thief) I have tried to explain that in this comment — here.

  • 33 minutes ago, # ^ | If you speak about '?' considering a thief you have to keep in mind what you have on both sides too. There might be some '1' in between or '0' before '?' that break the logic

    • 16 minutes ago, # ^ | Yes. Got it. But, I was just trying to reply to that comment which was specific to the string that has a 0, and has ?s before it. If we have to consider all scenarios, then: Full logic for Problem C.