By awoo, history, 12 months ago, translation,

Hello Codeforces!

On May/16/2021 11:00 (Moscow time) Educational Codeforces Round 109 (Rated for Div. 2) will start. Please, note the unusual start time.

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 Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Dear Codeforces!

We are reaching out to make sure you have everything you need to begin your journey at Harbour.Space University. That’s why we are hosting our very first Virtual Open.Day on May 20th at 4:30 p.m. (CET).

This Open.Day is an opportunity for our university to open its doors (virtually) for you to get an idea of what to expect in terms of the academic experience, student life, living in Barcelona and asking any questions you might have.

Remember, we have a full scholarship available for competitive programming! This scholarship is for Bachelor’s and Master’s students wanting to join any of our tech-related programmes and our dynamic programming team. Joining the Open.Day is the perfect opportunity for you to ask questions and make sure Harbour.Space is the right place for you.

Register for our Virtual Open.Day and see first-hand what life is like as a Spacer and the success stories of our scholarship recipients.

Here is a sneak peek: https://www.youtube.com/watch?v=y6f999g7qFA

Register Today→

Good luck on your round, and see you next time!

Harbour.Space University

UPD: Editorial is out

• +196

 » 12 months ago, # |   -88 i hope i can get top 10 in this contest
•  » » 12 months ago, # ^ |   0 did you?
 » 12 months ago, # | ← Rev. 6 →   +71 Finally a contest
 » 12 months ago, # |   -30 When is the next contest?
 » 12 months ago, # | ← Rev. 3 →   +65 Necessary MemeUPD1:After seeing c8kbf's comment down below it has been decided that only trusted participants of the third division can reply to this comment.Regardless of whether you are a trusted participant of the third division or not,you can still upvote this comment.
•  » » 12 months ago, # ^ |   -8 I will choose the red pill. As my logic is right so I just need to optimize my code a little and boom Accepted.
•  » » » 12 months ago, # ^ |   +54 If you TLE on test 2, how are you sure your logic is right? TLE != slow AC... so getting TLE on test 2 is just as bad as WA on test 2.
•  » » 12 months ago, # ^ |   +13 WA on test 2 with CF Diagnostics because that could (possibly) be a silly mistake like array out of bounds.
•  » » 12 months ago, # ^ |   0 this is for you keertan
 » 12 months ago, # |   +17 "Please, note the unusual start time." bruhh
 » 12 months ago, # |   +3 A contest after so many days feels like an eternity
 » 12 months ago, # |   -27 finally madarchod!
 » 12 months ago, # |   +8 and our dynamic programming team
 » 12 months ago, # |   +12 I hope to become Expert this time.
•  » » 12 months ago, # ^ |   -8 did you?
•  » » » 12 months ago, # ^ |   +13 Probably yes.
 » 12 months ago, # |   -16 why my code is giving runtime error in CSES dp-7th problem (book shop)??.Please help me. link to code- https://cses.fi/paste/31a10089630000cd20d9fe/
•  » » 12 months ago, # ^ |   +3 It require ~762MB memory space for the long long DP[10^5][10^3] array which doesn't fit in the question's limitation. To reduce the space complexity,you need to use the technique called rolling array.The idea is like reusing two layer of array alternatively for the DP transition. My accepted code for reference:https://cses.fi/paste/27ef5df72fd9b9261f7b04/
•  » » 12 months ago, # ^ |   +3 you don't need to do rolling array. :) you can just use ints https://pastebin.com/FyM7fEV4
 » 12 months ago, # |   0 Notice the unusual start time!
 » 12 months ago, # |   0 Super unusual start time!
 » 12 months ago, # |   +157
•  » » 12 months ago, # ^ | ← Rev. 3 →   +41 Spoiler
 » 12 months ago, # |   0 Finally we have a contest!!
 » 12 months ago, # |   +6 long time no see "codeforces contests"..where were you?
•  » » 12 months ago, # ^ |   0 They were solving CodeChef Long Challenge Questions. lol
 » 12 months ago, # |   +8 I hope I manage to wake up
 » 12 months ago, # |   0 Contest time is very unusual.By the way,finally we have a contest!!
 » 12 months ago, # |   +20 Even if there are meteor showers tomorrow, please keep this round rated
 » 12 months ago, # |   +136 Life is hard on the west coast...
•  » » 12 months ago, # ^ |   +10 Will you participate, btw?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +51 Maybe, I woke up at 6:30 AM today for Code Jam and haven't slept since :P and I have exams next week, but contests are fun too :DUpd: Ended up taking!
•  » » 12 months ago, # ^ |   +76 Good time for people with fucked up sleeping schedules like me! :D
 » 12 months ago, # |   +5 finally a contest but the start time is really unusual
 » 12 months ago, # |   0 Yayy it feels like a fresh breathe of air! Thank you CF!
 » 12 months ago, # |   0 Can someone help me with this"The penalty for each incorrect submission until the submission with a full solution is 10 minutes"Does this mean if we submit the correct answer for a question then all the penalties from incorrect submissions on that question will get canceled?
•  » » 12 months ago, # ^ |   +16 No. It means that if you wrong answer N times and get accepted eventually, you get 10*N minutes penalty. But if you didn't get accepted, then you won't receive any penalty for the failed submissions.
•  » » » 12 months ago, # ^ |   0 Ok. Thankyou so much
 » 12 months ago, # |   +144 Upvote this comment if you also think that task $C$ was a piece of shit.
 » 12 months ago, # |   +11 C is my new favorite problem ever!
•  » » 12 months ago, # ^ |   +2 I struggle on C for quite a long time... I wonder if there's solution that is easy to implement.
•  » » 12 months ago, # ^ |   +6 Looks like it was just me who implemented a 150+ line abomination
•  » » » 12 months ago, # ^ |   0 Me too :(
 » 12 months ago, # |   +3 crispy difficulty distribution.
 » 12 months ago, # | ← Rev. 2 →   +7
 » 12 months ago, # |   +73 ;)
•  » » 12 months ago, # ^ |   0 A very familiar situation on round
 » 12 months ago, # |   +8 How to solve D?
•  » » 12 months ago, # ^ |   +10 $dp$[person number][max number of used seat] = answer, So if there are $m$ people, and $n$ seats answer will be $dp[m][n]$Transition:1) place $i$ is used originally: $dp[i][j] = dp[i][j - 1]$2) place $i$ is not used originally: let's try to use it and update result from previous person best result (where $i$ seat wasn't used): $dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + |seat_i - j|)$(initially make all dp values = $INF$, except $dp[0][..]$)
•  » » » 12 months ago, # ^ |   0 Thanks
 » 12 months ago, # |   +1 How to solve C?
•  » » 12 months ago, # ^ |   +14 Notice that you can split the problem. The points can intersect when they arr both even or odd. So now look on odd numbers (even will be the same). Sort all values and go from left to right and keep values in a stack in a such way.If now element goes to left. If stack is empty just add an element. If you now try to add an element that goes to the left and the last one in stack goes to the right you can update the answer for both values.((now - was) / 2). If both go to the left you also can update the answer for both of them((now - was) / 2 + was). And remove the last element from stack. If now element goes to the right you can keep it in stack. In the end there can be some cases. 1. Stack has one L and some R. Or all R. You finally can iterate stack from right to left and update answer. (try to find formula yourself)
 » 12 months ago, # |   0 Can somebody explain to me the approach for problem B ? Thanks in Advance !
•  » » 12 months ago, # ^ |   0 Hint: answer can be 0, 1, 2, 3
•  » » 12 months ago, # ^ |   +3 1 2 3 -> 0, if all are in position ans is 0.1 3 2 -> 1 2 1 3 -> 1, if first or last are in position ans is 1.3 1 2 -> 2, if first and last are not in position ans is 2.3 2 1 -> 3, if first is in the last position, and the last one is in the first, ans is 3.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 hint : You can't take array of size n. but can take array of size n-1 and make it sorted array.
•  » » 12 months ago, # ^ |   0 //if array is sorted print 0 if(arr[0]==1 || arr[n-1]==n) { cout<<1<
•  » » 12 months ago, # ^ | ← Rev. 3 →   +6 1: if array is sorted, then 02: if the first element is 1, swap [2; n] hence 13: if the last element is n, swap [1; n — 1] hence 1 (this is the 2nd case but reversed)4: if 1 and n are in the middle of the array, then you need one swap to bring 1 to the front, and one swap for [2; n] (which is the 2nd case), hence 25: if the first element is n and the last element is 1, then you need two swaps to bring 1 to the front, and the case is now exactly the 3rd case (1 at the front), so another 2, hence 3
 » 12 months ago, # |   -7 C was nice.
 » 12 months ago, # |   -43 Video Tutorial A:https://www.youtube.com/watch?v=CINI7MZH5zAVideo Tutorial B:https://www.youtube.com/watch?v=Pfhp9JEbBnA
 » 12 months ago, # |   0 Can anyone explain how to solve D? I learnt that we can solve it using Hungarian algorithm (by adding dummy rows since we have less rows) but that would take O(n^3)
 » 12 months ago, # |   0 Man I should have looked at the last sample case for C. I was solving thinking that the coordinates were sorted. :(
 » 12 months ago, # | ← Rev. 3 →   +1 Can D be solved using Flows? It might be an overkill but still..The idea to find the minimum cost matching of the bipartite graph formed between 1's and 0's. Just add an edge between every 1 and 0 whose weight is the distance between them. The number of edges in the graph are $O(n^2)$. I just don't know how to solve it but I can feel that it's some standard.
•  » » 12 months ago, # ^ |   +15 Yes, i wrote this.
•  » » » 12 months ago, # ^ |   0 Could you please explain your solution?
•  » » » » 12 months ago, # ^ |   +19 Add edges from sourse to $ones$ and from $zeroes$ to sink with $capacity = 1$ and $cost = 0$. Also add edges between adjacent elements with $capasity = inf$ and $cost = 1$.Now just search the flow.
•  » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 Wouldn't the number of edges between the $ones$ and $zeros$ be of the order O(n2)?
•  » » » » » » 12 months ago, # ^ |   +22 There $n-1$ pairs of adjacent elements, so the number of these edges is $2*(n-1)$.
•  » » » » » 12 months ago, # ^ |   +16 Is there a way to prove that it's faster than O(n3)? (I misread the problem into a version where the chairs are arranged in a circle, and this solution, if proven to be sufficiently fast, can solve that too.)
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   +17 I guess no, because exist graphs on which SPFA algo works in $O(n*m)$.But on non-specific graphs (like in this task) it works really fast, usually faster that Djikstra (I tested).
•  » » » » » » » 12 months ago, # ^ |   +16 I'm aware of that, but even if we consider that SPFA runs in O(m) (which was what I'm assuming actually, since in MCMF SPFA often reaches that complexity), shouldn't the complexity be O(n * m^2), and since m = O(n) it should be O(n^3)? I know that the constraints on the edges are quite... interesting, but I'm not sure if we can actually prove that those constraints would lead to a reduction in terms of flow pushes?
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   +9 If SPFA runs in $O(m)$, the total complexity is $O(n*m)$, because $|flow|$ is number of $ones$, which is $O(n)$.
•  » » » » » » » » » 12 months ago, # ^ |   0 I see. That was stupid of me :)
•  » » » 12 months ago, # ^ |   +3 TLE 36 with MCMF with Levits shortest path algo. What is wrong?
•  » » » » 12 months ago, # ^ |   +4 I used SPFA algo (Ford-Bellman with queue)
•  » » » 12 months ago, # ^ |   +3 Is my problem in Levits algo? Swap it to dejikstra or what?
•  » » 12 months ago, # ^ |   0 I thought of hungarian algorithm but it failed as it's time complexity is cubic.
 » 12 months ago, # |   0 I solved D with min-cost-max-flow, 0.7/2.0 seconds. Is it possible to hack?
 » 12 months ago, # | ← Rev. 2 →   +4 Can anybody explain how to solve D
•  » » 12 months ago, # ^ |   +3 pD and Edu#97 pC is almost the same. Maybe the Editorial here ( https://codeforces.com/blog/entry/84149 ) may help you.
 » 12 months ago, # | ← Rev. 2 →   0 Could only solve A and B :/ Tried greedy in D but failed on the 7th pretest. Where did I go wrong? I tried to match every one on the nearest left or right zero. 116376030
•  » » 12 months ago, # ^ | ← Rev. 2 →   +1 60 0 1 1 0 1WA on this test case
 » 12 months ago, # |   0 Why is this O(N^2) code giving TLE on TC5? :( https://codeforces.com/contest/1525/submission/116381276
 » 12 months ago, # |   0 Can anyone tell me why my dp solution fails in D?
•  » » 12 months ago, # ^ |   +1 I tried greedy. It failed too. DP should work.
 » 12 months ago, # | ← Rev. 2 →   +50 It seems that I may have overcomplicated C a bit. A quick question to all those who think it's just annoying implementation — do you think it would be better if the robots were sorted in the beginning, or do you dislike the problem for some other reason? Because I agree that dealing with unsorted coordinates can be a bit annoying, and I'm sorry I've noticed that it would be better to sort them beforehand during the contest; but if it's not the reason why you dislike the problem, I'd like to hear why.
•  » » 12 months ago, # ^ |   +3 lots of room for bugs imo, but implementation (concept wise translating into code) should not be too terribly bad. It's probably because it's a 4am contest (at least for me) + deques rarely pop up (at least in my experience so I kept fucking up ordering of removal) is why it was kinda frustrating, but that's just coding experience not rly an issue w/ the problem. also yeah sorted at beginning would be kinda nice but not rly that important.
•  » » 12 months ago, # ^ |   0 I loved it However I was not able to solve it :)
•  » » 12 months ago, # ^ |   +18 I dislike this problem because:0). Stupid annoying implementation problem1). Bad input format: $x1, L, x2, R, x3, R$ better than $x1, x2, x3, L, R, R$.2). Unsorted coordinates.
•  » » » 12 months ago, # ^ |   +13 If you have experience in coding cleanly, then absolutely none of the things you listed should be more than trivial issues.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +24 I just hate this problem, so I tried to find some reasonable reasons to hate it :)
•  » » 12 months ago, # ^ |   +11 I don't think having the coordinates sorted would make much of a difference, since I think most stack-based solutions still have to keep track of the indices anyway.I personally thought that the implementation was nontrivial but not especially annoying. I was honestly quite surprised to see that more people solved D than C.For what it's worth, I really liked the problem!
•  » » 12 months ago, # ^ |   0 Likely people did not handle the case of going off walls well, resulting in painful casework. This could be easily avoided however with nice implementation where you do the classic stack idea and just move starting position of leftward moving values when they don't collide with something right away.
•  » » 12 months ago, # ^ |   0 Unsorted positions didn't annoy me much. I just found it difficult to deal with the boundaries. My idea was building 4 sets, two for odd/even positions of robots moving right, the other two for those moving left. Those moving left will have a reflected one out of the boundary moving to the right, so for those initially moving left, e.g., robot at 1 moving L will introduce a {1} in the left-odd set, and {-1} in the right-odd set.And then check the closest pairs between two sets of opposite direction but same odd/even property. However, I cannot deal with those around the boundary, e.g., the closest for robot at 1 moving left will be -1 moving right, which is itself...It could be a wrong idea tho. Let's see what the editorial says :)
•  » » 12 months ago, # ^ |   +10 I gave up working on it after having analyzed some cases...Odd positions, even positions, direction of movement, does the parity of M has to be considered? From my point of view it is that casework which makes it uncomfortable to work on this problem. Independent of the initial sorting.
•  » » 12 months ago, # ^ |   +4 Probably the most annoying thing about the problem is the casework formulas for calculating collision times. To be honest though, it wasn't enough to ruin it, I just wish there was a way to introduce the same problem ideas in a way that made implementation a little more appropriate for 2C.
•  » » » 12 months ago, # ^ |   +6 To get rid of some cases in these formulas, I suggest to try treating the left wall as a mirror. Mirroring the robot that goes to the left wall helps a lot here.
•  » » 12 months ago, # ^ |   +21 dude, the problem was fine & case handling was nice in my opinion and i liked the problem!
•  » » 12 months ago, # ^ |   +6 I think it’s a nice problem, with room for some of the smaller improvements that others have suggested, but I think perhaps it was too big a jump from B to C. It seems that 90% of participants were unable to tackle it, which is quite high for problem C.
 » 12 months ago, # |   -19 10/10 for the timing. Wish other contests can be scheduled at a similar time.
 » 12 months ago, # |   +6 What the hell is the "Test Case 8" for D?
•  » » 12 months ago, # ^ |   0 I am just hoping it's something really tricky... Coz if it's not, then I'll kill myself.. :(
•  » » 12 months ago, # ^ |   +16 Something that fails for greedy and works for dp?
•  » » » 12 months ago, # ^ |   +1 My greedy attempt managed to pass up to testcase 31 :D
•  » » 12 months ago, # ^ |   0 It was the first test case which don't work for greedy approaches.
 » 12 months ago, # |   0 When I solved C I was assuming there would have been atleast 4k submissions for it.
 » 12 months ago, # | ← Rev. 2 →   +13 Was D some assignment problem or hungarian algorithm BledDest ? Same idea of question was also asked in infosys coding test a while back.
•  » » 12 months ago, # ^ |   0 Nope, just straight dp. The idea is to hold dp[i] is best solution using prefix up to i, and you transition by considering taking a range and moving all values forward or all values backwards plus the dp value before the range. You have to make sure it is possible to move all values forward or all values backward with something similar to parentheses prefix sums making sure it is always greater than 0. Hopefully my code makes it clear what I mean.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Never thought like that, what I did was make 2 vectors of containing positions of 1's and 0's then made a cost matrix from that using cost[i][j] = abs(p1[i]-p0[j]) then we have to solve it like an assignment from N workers(number of 1's) to M jobs(number of 0's) each having a cost. It is a standard assignment problem. After solving A,B in like 15 minutes I spent the rest of time reading on Hungarian algorithm and transportation problem lol.
•  » » » » 12 months ago, # ^ |   0 Hungarian algorithm may be the solution in O(n*log n).I've seen the similar problem and solution in Edu#97 problem C.https://codeforces.com/blog/entry/84149
•  » » 12 months ago, # ^ |   0 I solved it using DP
•  » » 12 months ago, # ^ |   +27 It was dp.Let's say that the starting position of people are $x_1, x_2, \dots, x_k$ (in sorted order) and ending positions of people are $y_1, y_2, \dots, y_k$ (also in sorted order). It's always optimal to match these starting and ending positions in sorted order: the leftmost starting position is matched with the leftmost ending, the second starting position is matched with the second ending, and so on.Using this fact, we can implement the following dynamic programming: $dp_{i, j}$ is the minimum time if we considered $i$ first positions and picked $j$ of them as the ending ones. Transitions are the following: we either take the current position as the ending one (if it's not a starting one), match it with the $j$-th starting position and go to $dp_{i+1, j+1}$, or we skip the current position and go to $dp_{i+1,j}$.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 For Problem D: Let's consider 1-indexing.Let's say the empty_index = [1,2,4,5] and filled_index = [0,3,6], then why don't we choose for index 2 in the full_index array(whose value is 3), a choice of index 1(whose value is 1) in the empty_index array in our dp calculation?
•  » » » » 12 months ago, # ^ |   0 Thanks, it got clarified here — https://codeforces.com/blog/entry/90729?#comment-791731
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 I solved it using DP but can it be solved using flows? Isn't Hungarian O(V3) ?ACCOUNT_FOR_BAD_ROUNDS has solved using flows, but I couldn't understand his/her solution 116362662
•  » » » 12 months ago, # ^ |   0 Its O(mn + n^2logn) average but could not find any implementation online.
 » 12 months ago, # |   0 Nice contest! Really educational. I always thought this is for div3 (< div2 since it is educational) but apparently the difficulty is around div2.
 » 12 months ago, # |   +7 Hack my D! otherwise I may become Expert.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 If you are sure, your solution will be correct, then you are already an expert. Since you are an expert, you should be listened to and your solution will be hacked. Do you really want this? But then you will not reach Expert and people will ignore you and the loop begins... which keeps running forever. EDIT: Added the TLE criterion and fixed small error.
•  » » » 12 months ago, # ^ |   0 $Numbers\,Never\,Lies.$ If my potential is of expert level then I will definitely become someday. There is no hurry(I have huge patience).
•  » » » » 12 months ago, # ^ |   0 That is true! All the best to you!
 » 12 months ago, # |   +25 The problems diffucilty was like that :
•  » » 12 months ago, # ^ |   +20 I think D was comparatively easier
•  » » » 12 months ago, # ^ |   0 I solved D faster than B
 » 12 months ago, # | ← Rev. 3 →   0 Why my A failed anyone please help?? During contest i checked for all values and it was correct in my ide. The output defers in my codeblocks and on CF compiler. Durin
 » 12 months ago, # | ← Rev. 2 →   +41 I really liked the contest problems! I thought they were fun (even though I didn't manage to solve F). The implementation for C isn't even that bad if you have nice ideas. Seriously, too many people bash out the first ugly casework idea that comes to mind, then blame the problem setters for "annoying" implementation problems. Typical...On another note, I especially liked how in E, E spoilern <= 20 seems to suggest bitmask, but that's just a bait! My solution used linearity of expectation.
•  » » 12 months ago, # ^ |   +15 I was the victim of that bait :)
•  » » 12 months ago, # ^ |   +46 I was a victim of that bait while introducing and preparing the problem.
•  » » 12 months ago, # ^ |   0 Would you like to write down a formular how calculations in E work? For me it is hard to understand. I thought about to calc the propability foreach point to be occupied after ith turn, and from that find expected number of points... but that did not work out somehow.
•  » » » 12 months ago, # ^ |   0
•  » » » 12 months ago, # ^ | ← Rev. 4 →   +22 Because of linearity of expectation, we can independently consider the probability that each point will be occupied, then sum all those probabilities up.So, we can essentially rephrase the question as, "For some point, find the number of permutations such that this point is occupied." Let's instead solve for the complement---find the number of permutations such that the point is not occupied.We note that for point $j$ to not be occupied, we must have $p[i] \geq (n+2)-d_{i,j}$ for all $i$. Let $options[d]$ be the number of $i$ such that their position must be $\geq d$. Then, we can use the following loop. LL total = 0; for(int d = 1; d <= n; d++) { total += options[d]; ans = (ans*total)%MOD; total--; } Basically, count the number of guys you can put at each position, put one there, and multiply over all positions.Please tell me if you have more questions :))You can inspect my full submission at https://codeforces.com/contest/1525/submission/116376637 if you need more detail.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +6 The approach is to count the number of permutations of the cities in which each point gets conquered. We don't have to check all permutations for this. We first count the frequency of distances of every point from all the cities. For the given example, the frequency array will be: freq[ith point][number of cities at j distance] $=[[3, 0, 0, 0], [0, 0, 0, 3], [1, 0, 0, 2], [0, 0, 1, 2], [0, 1, 1, 1]], 1<=i<=m, 1<=j<=n+1$.We will count the number of permutations in which the $i$ th point doesn't get conquered for all $1<=i<=m$. (We will subtract this count from $n!$ for the valid count).Observe that for a point not to be conquered, it must not be conquered by each of the cities. Hence for any point $i$, with $freq[i][j]$ cities at a distance $j$. All these $freq[i][j]$ cities must have their permutation values belonging to the set {$1,2,...,j-1$} of maximum distance that can be covered by them(i.e. these correspond to building a museum in these cities in the $n,n-1,...n-(j-1)+1$ th turn). So the number of choices for the $j$ th city is $(j-1)P(freq[i][j])$ (where $nPr=n!/(n-r)!$).However, for the next city we're considering, we can't choose the $freq[i][j]$ values previous city which we've already considered. We keep a variable counted which stores the number of distinct distance values(i.e. the distinct turn numbers) already counted. So the formula will be $(j-1-counted)P(freq[i][j])$ for the $j$ th city. We increment counted by $freq[i][j]$ each time.The total number of ways the $i$ th point cannot be conquered is just the product of values of the above expression for all values of $j$.(Note that if at any iteration $freq[i][j]>=j-counted$, that point can never be not conquered). Subtract $n!$ from this to get the number of ways the $i$ th point can be conquered. Sum of this value for all the points is the required answer($x$). $y$ is just the total number of permutations($n!$).You can see this for reference https://codeforces.com/contest/1525/submission/116385486
 » 12 months ago, # | ← Rev. 5 →   +69 Solutions to A-E1525A - Potion-making SpoilerThe solutions are $e = mk$, $w = m(100 - k)$ for some $m$. As $e, w$ are integers, the minimum possible $m$ is $1/\gcd(k, n - k)$. The result is $100 / \gcd(k, n - k)$.1525B - Permutation Sort SpoilerIt's optimal to always sort subarrays $[1, n-1]$ and $[2, n]$. If the array is already sorted, you need $0$ operations. Otherwise, if $a_1 = 1$ or $a_n = n$, you need $1$ operation. Otherwise, if $a_1 \neq n$ or $a_n \neq 1$, you need $2$ operations (in the first operation you can get $a_1 = 1$ or $a_n = n$). Otherwise you need $3$ operations.1525C - Robot Collisions SpoilerConsider even and odd coordinates independently. If there is a pair of adjacent robots ${\text{R}, \text{L}}$, they collide. The remaining robots are ${\text{L}, \text{L}, \dots, \text{R}, \text{R}, \dots}$. If there is a pair of adjacent robots ${\text{L}, \text{L}}$ on the left or ${\text{R}, \text{R}}$ on the right, they collide. The remaining robots are at most $2$. If they are exactly $2$, they collide.1525D - Armchairs SpoilerThe relative order of people remains the same in the optimal configuration. Let $dp_{i,j}$ the minimum cost if person $i$ goes in position $j$. Let $pm_{i,j}$ the minimum cost if person $i$ goes in a position $\leq j$ (it's a prefix minimum). If $a_j = 1$, $dp_{i,j} = \infty$. Otherwise, $dp_{i, j} = |b_i - j| + pm_{i-1,j-1}$. Let $k$ be the total number of people, the result is $dp_{k, n}$.1525E - Assimilation IV SpoilerThe problem is equivalent to "calculate the expected number of $j$ such that there exist a $i$ such that $d_{i,j} \leq a_i$, if $a$ is a random permutation of ${1, 2, \dots, n}$". Because of linearity of expectation, you can calculate the expected values independently for each $j$, and add them up. For each $j$, sort the $a_{i,j}$ and calculate for each $i$ the probability that $d_{i,j} > a_i$, given that $d_{k,j} > a_k$ for each $k < i$. Since the $a_k$ are all $< d_{i, j}$, the possible values of $a_i$ are $\max(0, d_{i,j} - i)$. Hence, the expected value for each point is $1 - \frac{\prod_{i=1}^{n} \max(0, d_{i,j} - i)}{n!}$.
•  » » 12 months ago, # ^ |   0 For Problem D:Any reason why this holds true? The relative order of people remains the same in the optimal configuration.
•  » » » 12 months ago, # ^ |   +12 If $l_1 < r_1$ and $l_2 < r_2$, $|l_1-l_2|+|r_1-r_2| \leq |l_1-r_2|+|l_2-r_1|$. Hence, you shouldn't have any pair of people with a different relative order.
•  » » » » 12 months ago, # ^ |   0 Great, this makes a lot of sense!During the contest, I was worried about how would I tackle the case if the ordering is reversed, as I would have needed to store the previous indices which are not used.This certainly simplifies the DP recurrence relation. Thanks :D
 » 12 months ago, # |   +7 First time i able to solve D in any Educational round,
•  » » 12 months ago, # ^ |   0 How to identify if we have to apply dp on any problem? If i could figure this out i would have solved it too!
•  » » » 12 months ago, # ^ |   0 You can implement a dp if you find a dp. Just formulate dp[i][j]=... something that makes senseYou are expected to do this in kind of every problem as part of the analysis. Of course there are more points to consider, but that is definitly one of them.
•  » » » 12 months ago, # ^ |   0 When ever the question asks for optimal solution. Dp comes into play. Yeah many questions will be solved by greedy approach also. And the constraints in the question will help you judge as in D question.. The constraints were 5000 so.. N^2 solution is accepted. From that you can judge how it's related to dp
•  » » » 12 months ago, # ^ |   0 Same question was mine i used to ask from seniors still i am not good at this, but one thing i can say it all comes through only practice, practice dp questions rating wise, i did this little bit
 » 12 months ago, # | ← Rev. 4 →   0 C++17(64-bit) is really fast(For $E$ TC-15 takes more than 2000ms while same code runs in 841ms on C++17 on TC-15), I managed to AC $E$ in $O(n^{3}m)$
 » 12 months ago, # |   0 A and B were nice but C question was very tricky.
 » 12 months ago, # |   +8 Lol E is easier than C and D
 » 12 months ago, # | ← Rev. 3 →   0 Can anyone tell me why my code can't be compiled? It works fine in my ide and custom invocation.Link to my submissionCan't compile file: C:/Programs/mingw-w64-7/bin/../lib/gcc/i686-w64-mingw32/7.3.0/../../../../i686-w64-mingw32/bin/ld.exe: final link failed: No space left on device collect2.exe: error: ld returned 1 exit statusSame code gives AC now
 » 12 months ago, # |   0 Can somebody help me with TLE in the following submission for problem D. 116403094
 » 12 months ago, # | ← Rev. 3 →   +3 Could some one please provide small counter test case to my submission of problem D. Test case 44 is very big. dp[i][j] means minimum answer to accommodate all 1's till position $i$ in such a way that they remain within $1$ and $j$.UPD : I found the mistake. This was counter test case : 10 0 1 0 0 1 1 1 1 0 0
 » 12 months ago, # |   0 116407151 why I am getting RT at testcase 11 ?
•  » » 12 months ago, # ^ |   0 Due to recursion limit in python. However, even after increasing recursion limit your solution TLE's in testcase 31 https://codeforces.com/contest/1525/submission/116412562
•  » » » 12 months ago, # ^ |   0 But same code in pypy give memory limit
 » 12 months ago, # |   0 I really liked the 4th/D problem. I had encountered the problem with the same idea on Leetcode. I tried solving the problem using set but end up failing on pretest 8. During the contest, I wasn't able to give proof to myself that greedy approach would fail. Leetcode problem linkMy approach to solve problem D:Insert all the empty seats into set. traverse from left, and do the upper_bound to find the next available seat for current occupied seat. it = upper_bound(i) pick the seat from it, or --it whichever gives the minimum answer.If there is a tie between it, and --it then select --it to give priority to the first available pointer.Can someone help here why is it failing?
•  » » 12 months ago, # ^ |   0 Consider input like 000111000011111000, ie a gap in the middle. You do not know for which of the persons in the two blocks of 1s it is optimal to move them left, or move them right.What you are basically doing is moving them all to the left (or right, depends on implementation). Consider further that there can be severeal such "gaps" next to each other...foreach one the same problem, youc annot know if it is better to move the people left or right.
•  » » 12 months ago, # ^ | ← Rev. 8 →   0 consider this input : 70 0 0 1 1 1 0
•  » » » 12 months ago, # ^ | ← Rev. 2 →   -24 sober_phoenix> t; while(t--) { test_cases(); } return 0; } ~~~~~"> ... Above is the implementation which I did during the contest. seems to be giving the wrong answer on the test case. 7 0 0 0 1 1 1 0 
•  » » » » 12 months ago, # ^ |   0 please put your code in spoilers. Otherwise it makes the comment section unnecessary lengthy.
 » 12 months ago, # |   -14 Can anyone please share the DSA problems sheet for leetcode(like we have of Dr. Mostafa Saad Ibrahim for CP)?
 » 12 months ago, # |   +16 Guess who just showed up at 8pm on a Sunday night to give the contest only to realize it was at an unusual time. One more contest to reach 1200 Let's goooo!!!
 » 12 months ago, # |   0 can any one tell why i am getting tle on test case 26 in Problem D Armchairs. 116422974
•  » » 12 months ago, # ^ |   +6 while passing the vectors in the function use call be reference method otherwise the whole vector will be copied in every function call. 116426242
•  » » » 12 months ago, # ^ |   0 ok got it, thanks
 » 12 months ago, # | ← Rev. 2 →   0 Completing all my work as soon as possible, getting prepared for the round. since this contest happened after a week, opened the code forces with huge excitement, then I closed the website."The contest ended before 6 hours"
•  » » 12 months ago, # ^ |   0 now again wait 4 days next round is on 20th.
 » 12 months ago, # |   0 116419179 why I am getting MLE ?
•  » » 12 months ago, # ^ |   0 You're missing this line if(dp[i][j]!=-1){ return dp[i][j]; }
•  » » » 12 months ago, # ^ |   0 Still same issue
•  » » » » 12 months ago, # ^ |   0 Firstly you need to initialize every element of dp with -1. Then only that check will work
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Your problematic line is setrecursionlimit(10**6). Using setrecursionlimit(10**6) takes a lot of memory on PyPy. 768 * n bytes to be exact (where n = $10^6$ in your case). That is the reason why you are getting MLE. Even if you had enough memory to run setrecursionlimit(10**6) it still wouldn't allow you to recurse to depth $10^6$ because of the default stack size being very limited. C++ also has this same exact issue, but in the case of C++ it is fixed by compiling it with the flag --stack=268435456. So how do you do deep recursion in Python? A while back I made this to basically allow for infinite recursion. You can read about it here. Here is your submission using it 116495993. (Unfortunately it gets TLE since $O(n^2)$ with $n=5000$ in Python requires fast running code).
 » 12 months ago, # |   0 Do failed hacks decrease my place/rating?
•  » » 12 months ago, # ^ |   +1 No
•  » » 12 months ago, # ^ |   +3 The hacks do not affect your score in div3/edu rounds.. I learnt it the hard way
 » 12 months ago, # |   0 i think problem C was so hard for being C in div2
•  » » 12 months ago, # ^ |   +1 Problem D was easier than the problem C.
 » 12 months ago, # | ← Rev. 2 →   +3 Has systests started?My solution was hacked for TLE, but I used the same hack on my solution and it did not TLE (1933ms / 2000ms)
•  » » 12 months ago, # ^ |   0 It's really strange.
•  » » 12 months ago, # ^ |   +3 There are different runtime randomisations done which affect the runtime of a program every time it is ran differently.. It can be analysed that since the solution just passed the time limits barely, this may have been the cause.
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 I believe that the hacks have not yet been added into the tests. I reran a couple of mine and found that they were subject to exactly the same set of tests. My guess is that they will be added soon and then a full system test will follow.
 » 12 months ago, # |   0 Why is this competition unrated?
•  » » 12 months ago, # ^ |   0 Wait.System test is still pending.
•  » » » 12 months ago, # ^ |   +4 When will the final ratings for this contest be released?
•  » » » 12 months ago, # ^ |   0 OK,thank you.
 » 12 months ago, # | ← Rev. 2 →   +12 D is uses same idea https://codeforces.com/problemset/problem/830/A
 » 12 months ago, # |   +3 Please can someone explain me in an easy way to solve D.
•  » » 12 months ago, # ^ |   +4 Suppose the sequence is as follows 001001101110. Let the number of 1's be k here. Just invert the sequence 110110010001. Let the number of 1's be m hereNow think like this.The number of 1's in the inverted sequence must be k.So the problem reduces to choosing k ones from the m ones in the inverted sequence.We can use dp to solve this.I have designed dp[i][j] as following: dp[i][j] stores the minimum number of minutes to attain the situation that uptil i index the number of 1's in the inverted sequence is j.Example dp[4][2] implies that uptil position 4 if there are 2 ones what is the minimum number of minutes I have to spend.As we can see in the inverted sequence till position 4 '1101' is possible. The 2 ones could be anywhere.dp[4][2] could have attained minimum at any of the following configurations which we are calculating using dp: '1100','1001','0101'.So we can see that we are choosing just 2 '1's out of the 3 positions where 1 can be put and finding dp[4][2].I know its a little complicated ,but once you understand what dp[i][j] means I guess you can understand the way I am approaching.You can check my solution for the complete code.
•  » » » 12 months ago, # ^ |   +1 Thanks for explaining the solution.
 » 12 months ago, # |   0 When will the ratings be updated
•  » » 12 months ago, # ^ |   +3 System test is still pending. Once it will get complete ratings will get updated. (We should ask for editorials rather than updating ratings)
 » 12 months ago, # |   0 Is the System test done?
•  » » 12 months ago, # ^ |   0 Not yet started
•  » » » 12 months ago, # ^ |   0 Thanks. But hacking phase was over well before 6 hrs. I guess. I thought it was done. Thanks for clarifying.
 » 12 months ago, # |   0 why didn't i get points after i finish the competition? (1 ranked 3500) please help me. i'm new here
•  » » 12 months ago, # ^ |   +7 The rating result sooner or later will came out, Don't worry about that. You can check out the unofficial rating prediction in https://cf-predictor-frontend.herokuapp.comIt's pretty accurate.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 it did not work it show Good luck & high rating! every time
•  » » » » 12 months ago, # ^ |   +4 It(the extension) changes the html of the website and you need not click it. Just go to standings page on codeforces and as last column of the standing table you can see rating changes. In their website you can directly see rating changes of everyone
 » 12 months ago, # |   +3 Is the editorial released for this contest?
 » 12 months ago, # |   0 Can someone explain the problem D for me ? like the state and the transition of the dp !Thanks
•  » » 12 months ago, # ^ |   0 https://codeforces.com/blog/entry/90729?#comment-791594Check this comment.You can refer to my code for the implementation part. 116414468
•  » » 12 months ago, # ^ |   +7 Firstly you have to store indices of '1' in array A and indices of '0' in array B in sorted manner. Now every element of array A will have to be paired with exactly one element of Array B (Note : any element of array B can be paired up with only one element of array A also) for reaching required final condition. dp(i,j) where i is the current index of array A and j is the current index of array B gives minimum time to reach final condition from current position (i,j). For position (i,j) we will have two option :- (1) Pair up i with j and move to (i+1,j+1). (2) Leave j and move to (i,j+1). and dp(i,j) will be minimum of above two. Final answer will be dp(0,0) (i.e minimum time required to reach final condition from initial position (0,0)). You can see my solution : 116400573 Hope explanation gives you some feel of intuition.Thanks!
•  » » » 12 months ago, # ^ |   0 Excellent thank you
•  » » » 12 months ago, # ^ |   0 Very nice approach
 » 12 months ago, # |   0 Can anybody give me a test case where my code for problem C will be wrong? 116456536Or if you can notice any mistake, that'll be helpful too.
 » 12 months ago, # |   0 When guides will be available?
 » 12 months ago, # |   0 I am under 2100 but my rating didn't change, can someone tell me why is that?
•  » » 12 months ago, # ^ |   +1 And why is there no editorial?
•  » » » 12 months ago, # ^ |   +4 i think the raing will update soon.
•  » » » » 12 months ago, # ^ |   +3 Thanks
 » 12 months ago, # |   +8 editorial?
 » 12 months ago, # |   +7 No editorial?
 » 12 months ago, # |   +6 When will we see the rating change for this round?
•  » » 12 months ago, # ^ |   0 Now the editorial is out. Soon it will change.
 » 12 months ago, # |   -7 Eagerly waiting for editorial .
 » 12 months ago, # | ← Rev. 2 →   -8
 » 12 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 12 months ago, # |   -8 Tutorial available now !!!
 » 12 months ago, # | ← Rev. 3 →   0 Why I think D is much harder than C and E?Can anyone give me any suggestions on how to learn dp well?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +8 I have found improving my DP one of the most difficult things — you are not alone. The key to thinking about it for me is defining a 'state' of some description. How can I use the variables I have to define a particular state? The best way to improve this thinking is just lots of practice, and reading editorials.I then need to work out 3 things: the base state: this is usually the position we start from the end state: what position are we trying to reach? how do I transition between states (and which variables do I iterate over, and in what order)? There is no 'algorithm' to define the states. This is the difficult bit. What makes sense? What information do I have?In this case the information I have is the number of people I have already moved, and where I have moved them to; in particular, what is the furthest right 0 I have used? I can therefore set up a two-dimensional array iterating over these variables: dp[i][j] = the minimum cost of moving i people into positions ending no further right than position j. I need to use the information of previous states, and the information of the starting positions, to define what an acceptable transition looks like. This is detailed in the editorial.What are the base states? I can move 0 people at no cost, ending at any position. So dp[0][j] = 0 for all j. Call dp[i][j] = INF for i > 0 initially. If it is not possible to achieve i transitions to the first j spaces, this value will not change.What is my final answer? I need all the people to move (say there are X ones in the original array), and I don't mind where the furthest right position is, so my answer is min(dp[X][j]) for all j. Since we know there are at least N/2 free positions, we are guaranteed a solution, so the answer will not be INF. If there were < N/2 free positions, the answer would be INF, indicating 'impossible'.
•  » » 12 months ago, # ^ |   0 Yep. My suggestion.
 » 12 months ago, # |   +18 Rating update
 » 12 months ago, # |   +3 When will rating change
•  » » 12 months ago, # ^ |   0 System Testing has started, ratings will be updated real soon
•  » » » 12 months ago, # ^ |   0 Ohh okay..thanks a lot
•  » » » 12 months ago, # ^ |   0 Can you tell me how can we get to know that system testing has started
•  » » » » 12 months ago, # ^ |   0 10minutes ago, Veridict of my submissions, which were accepted in orevious rounds, was changed to "in queue" That is how I knew that they are in queue for system testing Now their verdit is again changed to "accepted" So system testing is almost over Rating will be updated very soon now
•  » » » » » 12 months ago, # ^ |   0 okayy!! thanks! happy coding!
 » 12 months ago, # | ← Rev. 2 →   0 Finally, system tests are about to end
 » 12 months ago, # |   +11 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
•  » » 12 months ago, # ^ |   +8 I thought it took so long because you removed the cheaters
 » 12 months ago, # |   0 I solved two problems why i get -14 ? :((
•  » » 12 months ago, # ^ |   0 The rating is given according to your place, not number of solved problems. You were too slow to get your expected place.
•  » » » 12 months ago, # ^ |   0 ok thank you :(
 » 12 months ago, # | ← Rev. 2 →   0 For Problem D, I wrote a Recursive + Memoization approach in Python. But it is getting TLE in Test Case -31. can you please help me identify why it's getting TLE?My Submission Link : https://codeforces.com/contest/1525/submission/116522631I am using the exact same logic as https://codeforces.com/contest/1525/submission/116387891 written in C++ by others.
 » 12 months ago, # |   +3 What happened !! My previous rating was before this contest 1481 why it's 1424 after it's rolled back it should be 1481
 » 12 months ago, # |   0 I have received an email about cheating. As far as I understand it is acceptable to use content published before the contest.I took help of these 2 websites for the D Questionhttps://math.stackexchange.com/questions/414182/finding-minimum-sum-of-absolute-differences-betweens-values-of-two-sets/536050https://github.com/AliOsm/CompetitiveProgramming/blob/master/SPOJ/DCOWS%20-%20Dancing%20Cows.cppWas it a violation of the rules about third-party code??
»
12 months ago, # |
0

can anyone find what's the problem in my code i code it for problem b i make a logic that i convert a[i] =a[i]/(i+1) and whenever a[i] turns out to be zero i count that no i get rigth answer when i put indivially or single array but when i apply whole test case it give wrong answer please help me out my code is

# include

using namespace std; int main() { int p; int count =0; cin>>p; while (p--) {int n; cin>>n; int a[n] ; for (int i = 0; i <n; i++) { cin>>a[i]; } for (int i = 0; i < n; i++) {
a[i]= a[i]/(i+1); if (a[i]==0 ) { count++; } } cout<<count<<endl; } return 0; }