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
Good luck on your round, and see you next time!
Harbour.Space University
UPD: Editorial is out
i hope i can get top 10 in this contest
did you?
When is the next contest?
UPD1: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.
I will choose the red pill. As my logic is right so I just need to optimize my code a little and boom Accepted.
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.
WA on test 2 with CF Diagnostics because that could (possibly) be a silly mistake like array out of bounds.
this is for you keertan
"Please, note the unusual start time." bruhh
A contest after so many days feels like an eternity
I hope to become Expert this time.
did you?
Probably yes.
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/
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/
you don't need to do rolling array. :) you can just use ints https://pastebin.com/FyM7fEV4
Notice the unusual start time!
Super unusual start time!
Finally we have a contest!!
long time no see "codeforces contests"..where were you?
They were solving CodeChef Long Challenge Questions. lol
I hope I manage to wake up
Even if there are meteor showers tomorrow, please keep this round rated
Life is hard on the west coast...
Will you participate, btw?
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 :D
Upd: Ended up taking!
Good time for people with fucked up sleeping schedules like me! :D
finally a contest but the start time is really unusual
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?
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.
Upvote this comment if you also think that task $$$C$$$ was a piece of shit.
C is my new favorite problem ever!
I struggle on C for quite a long time... I wonder if there's solution that is easy to implement.
Looks like it was just me who implemented a 150+ line abomination
Me too :(
crispy difficulty distribution.
;)
How to solve D?
$$$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][..]$$$)
How to solve C?
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)Can somebody explain to me the approach for problem B ? Thanks in Advance !
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.
hint : You can't take array of size n. but can take array of size n-1 and make it sorted array.
1: if array is sorted, then 0
2: if the first element is 1, swap [2; n] hence 1
3: 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 2
5: 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
C was nice.
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)
Man I should have looked at the last sample case for C. I was solving thinking that the coordinates were sorted. :(
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.
Yes, i wrote this.
Could you please explain your solution?
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.
Wouldn't the number of edges between the $$$ones$$$ and $$$zeros$$$ be of the order O(n2)?
There $$$n-1$$$ pairs of adjacent elements, so the number of these edges is $$$2*(n-1)$$$.
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.)
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).
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?
If SPFA runs in $$$O(m)$$$, the total complexity is $$$O(n*m)$$$, because $$$|flow|$$$ is number of $$$ones$$$, which is $$$O(n)$$$.
I see. That was stupid of me :)
TLE 36 with MCMF with Levit`s shortest path algo. What is wrong?
I used SPFA algo (Ford-Bellman with queue)
Is my problem in Levit`s algo? Swap it to dejikstra or what?
I solved D with min-cost-max-flow, 0.7/2.0 seconds. Is it possible to hack?
Can anybody explain how to solve D
pD and Edu#97 pC is almost the same.
Maybe the Editorial here ( https://codeforces.me/blog/entry/84149 ) may help you.
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
6
0 0 1 1 0 1
WA on this test case
Why is this O(N^2) code giving TLE on TC5? :( https://codeforces.me/contest/1525/submission/116381276
Can anyone tell me why my dp solution fails in D?
I tried greedy. It failed too. DP should work.
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.
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.
I loved it However I was not able to solve it :)
I dislike this problem because:
0). Stupid annoying implementation problem
1). Bad input format: $$$x1, L, x2, R, x3, R$$$ better than $$$x1, x2, x3, L, R, R$$$.
2). Unsorted coordinates.
If you have experience in coding cleanly, then absolutely none of the things you listed should be more than trivial issues.
I just hate this problem, so I tried to find some reasonable reasons to hate it :)
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!
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.
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 :)
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.
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.
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.
dude, the problem was fine & case handling was nice in my opinion and i liked the problem!
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.
What the hell is the "Test Case 8" for D?
Something that fails for greedy and works for dp?
My greedy attempt managed to pass up to testcase 31 :D
It was the first test case which don't work for greedy approaches.
Was D some assignment problem or hungarian algorithm BledDest ? Same idea of question was also asked in infosys coding test a while back.
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.
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.
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.me/blog/entry/84149
I solved it using DP
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}$$$.
For Problem D: Let's consider 1-indexing.
Let's say the
empty_index = [1,2,4,5]
andfilled_index = [0,3,6]
, then why don't we choose for index2
in thefull_index
array(whose value is 3), a choice of index1
(whose value is 1) in theempty_index
array in our dp calculation?Thanks, it got clarified here — https://codeforces.me/blog/entry/90729?#comment-791731
Problem D:
Wrong ans on test 37
Can you pls tell me where i was wrong ?
Submission Link : 198729784
Thanks in Advance .
I solved it using DP but can it be solved using flows? Isn't Hungarian O(V3) ?
2147483648 has solved using flows, but I couldn't understand his/her solution 116362662
Nice contest! Really educational. I always thought this is for div3 (< div2 since it is educational) but apparently the difficulty is around div2.
Hack my D! otherwise I may become Expert.
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.
$$$Numbers\,Never\,Lies.$$$ If my potential is of expert level then I will definitely become someday. There is no hurry(I have huge patience).
That is true! All the best to you!
The problems diffucilty was like that :
I think D was comparatively easier
I solved D faster than B
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,
n <= 20
seems to suggest bitmask, but that's just a bait! My solution used linearity of expectation.I was the victim of that bait :)
I was a victim of that bait while introducing and preparing the problem.
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.
Link to comment
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.
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.me/contest/1525/submission/116376637 if you need more detail.
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.me/contest/1525/submission/116385486
Solutions to A-E
1525A - Potion-making
The 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
It'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
Consider 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
The 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
The 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!}$$$.
For Problem D:
Any reason why this holds true?
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.
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
First time i able to solve D in any Educational round,
How to identify if we have to apply dp on any problem? If i could figure this out i would have solved it too!
You can implement a dp if you find a dp. Just formulate dp[i][j]=... something that makes sense
You 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.
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
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)$$$
Lol E is easier than C and D
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
116407151 why I am getting RT at testcase 11 ?
Due to recursion limit in python. However, even after increasing recursion limit your solution TLE's in testcase 31 https://codeforces.me/contest/1525/submission/116412562
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 link
My 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.
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?
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.
consider this input :
7
0 0 0 1 1 1 0
sober_phoenix
<spoiler summary=" ~~~~~ #include <bits/stdc++.h> using namespace std; using namespace std::chrono; #define int long long #define endl '\n' const int nax = 1e5 + 9; const int MOD = 1e9 + 7; struct Node { public: int val; }; //comparator for min heap bool operator<(const Node& lhs, const Node& rhs) { return lhs.val > rhs.val; } //priority_queue Q; void test_cases() { int n; cin >> n; set s; vector vec(n + 5); for (int i = 1; i <= n; ++i) { cin >> vec[i]; if(!vec[i]) s.insert(i); } int ans = 0; for (int i = 1; i <= n; ++i) { if(!vec[i]) continue; auto lower_it = upper_bound(s.begin(), s.end(), i); if(lower_it == s.end()) { --lower_it; ans += abs(i — *lower_it); s.erase(*lower_it); } else if(lower_it == s.begin()) { ans += abs(i — *lower_it); s.erase(*lower_it); } else { auto another = lower_it; --another; if(abs(i — *lower_it) >= abs(i — *another)) { ans += abs(i — *another); s.erase(*another); } else { ans += abs(i — *lower_it); s.erase(*lower_it); } } } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int t = 1; // cin >> 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.
please put your code in spoilers. Otherwise it makes the comment section unnecessary lengthy.
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!!!
can any one tell why i am getting tle on test case 26 in Problem D Armchairs. 116422974
while passing the vectors in the function use call be reference method otherwise the whole vector will be copied in every function call. 116426242
You're missing this line if(dp[i][j]!=-1){ return dp[i][j]; }
Still same issue
Firstly you need to initialize every element of dp with -1. Then only that check will work
Your problematic line is
setrecursionlimit(10**6)
.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.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).
Do failed hacks decrease my place/rating?
No
The hacks do not affect your score in div3/edu rounds.. I learnt it the hard way
i think problem C was so hard for being C in div2
Problem D was easier than the problem C.
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)
It's really strange.
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.
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.
Why is this competition unrated?
Wait.System test is still pending.
When will the final ratings for this contest be released?
OK,thank you.
D is uses same idea https://codeforces.me/problemset/problem/830/A
Please can someone explain me in an easy way to solve D.
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 here
Now 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.
Thanks for explaining the solution.
When will the ratings be updated
System test is still pending. Once it will get complete ratings will get updated. (We should ask for editorials rather than updating ratings)
Is the System test done?
Not yet started
Thanks. But hacking phase was over well before 6 hrs. I guess. I thought it was done. Thanks for clarifying.
why didn't i get points after i finish the competition? (1 ranked 3500) please help me. i'm new here
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.com
It's pretty accurate.
it did not work it show Good luck & high rating! every time
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
Is the editorial released for this contest?
Can someone explain the problem D for me ? like the state and the transition of the dp !
Thanks
https://codeforces.me/blog/entry/90729?#comment-791594
Check this comment.
You can refer to my code for the implementation part. 116414468
You can see my solution : 116400573
Hope explanation gives you some feel of intuition.Thanks!
Can anybody give me a test case where my code for problem C will be wrong? 116456536
Or if you can notice any mistake, that'll be helpful too.
I am under 2100 but my rating didn't change, can someone tell me why is that?
And why is there no editorial?
i think the raing will update soon.
Thanks
editorial?
No editorial?
When will we see the rating change for this round?
Eagerly waiting for editorial .
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Tutorial available now !!!
Why I think D is much harder than C and E?
Can anyone give me any suggestions on how to learn dp well?
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
. Calldp[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 leastN/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 beINF
, indicating 'impossible'.Yep. My suggestion.
When will rating change
Finally, system tests are about to end
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
I thought it took so long because you removed the cheaters
I solved two problems why i get -14 ? :((
The rating is given according to your place, not number of solved problems. You were too slow to get your expected place.
What happened !! My previous rating was before this contest 1481 why it's 1424 after it's rolled back it should be 1481
Problem D :
Wrong Answer on test 37
Submission link 198713081
Can you pls tell why it's wrong ?
Thanks in Advance.