Educational Codeforces Round 109 [Rated for Div. 2]

from Imgflip Meme Generator

4 years ago, # |

+144

Upvote this comment if you also think that task $$$C$$$ was a piece of shit.

→ Reply

SleepyShashwat

4 years ago, # |

+11

C is my new favorite problem ever!

→ Reply

Dozlion

4 years ago, # ^ |

I struggle on C for quite a long time... I wonder if there's solution that is easy to implement.

→ Reply

sharath101

4 years ago, # ^ |

Looks like it was just me who implemented a 150+ line abomination

→ Reply

harsh__h

4 years ago, # ^ |

Me too :(

→ Reply

rishabhdeepsingh

4 years ago, # |

crispy difficulty distribution.

→ Reply

phir

4 years ago, # |

← Rev. 2 →

sighs

→ Reply

Rahat_Khan_Pathan

4 years ago, # |

+73

;)

→ Reply

turzo_sawroop

4 years ago, # |

How to solve D?

→ Reply

nikich340

4 years 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][..]$$$)

→ Reply

aniket_lakhotia

4 years ago, # |

How to solve C?

→ Reply

4 years 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)

→ Reply

AvaraKedavra

4 years ago, # |

Can somebody explain to me the approach for problem B ? Thanks in Advance !

→ Reply

Rahat_Khan_Pathan

4 years ago, # ^ |

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.

→ Reply

Syntax_Sugar

4 years ago, # ^ |

← Rev. 2 →

hint : You can't take array of size n. but can take array of size n-1 and make it sorted array.

→ Reply

jalsol

4 years ago, # ^ |

← Rev. 3 →

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

→ Reply

_yuio_

4 years ago, # |

-7

C was nice.

→ Reply

Firse_CP_karni_padegi

4 years ago, # |

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)

→ Reply

anujdhillxn

4 years ago, # |

Man I should have looked at the last sample case for C. I was solving thinking that the coordinates were sorted. :(

→ Reply

vishaaaal

4 years ago, # |

← Rev. 3 →

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.

→ Reply

4 years ago, # ^ |

+15

Yes, i wrote this.

→ Reply

4 years ago, # ^ |

Could you please explain your solution?

→ Reply

4 years 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.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Wouldn't the number of edges between the $$$ones$$$ and $$$zeros$$$ be of the order O(n2)?

→ Reply

4 years ago, # ^ |

+22

There $$$n-1$$$ pairs of adjacent elements, so the number of these edges is $$$2*(n-1)$$$.

→ Reply

16204

4 years 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.)

→ Reply

4 years 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).

→ Reply

16204

4 years 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?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

If SPFA runs in $$$O(m)$$$, the total complexity is $$$O(n*m)$$$, because $$$|flow|$$$ is number of $$$ones$$$, which is $$$O(n)$$$.

→ Reply

16204

4 years ago, # ^ |

I see. That was stupid of me :)

→ Reply

4 years ago, # ^ |

TLE 36 with MCMF with Levit`s shortest path algo. What is wrong?

→ Reply

4 years ago, # ^ |

I used SPFA algo (Ford-Bellman with queue)

→ Reply

4 years ago, # ^ |

Is my problem in Levit`s algo? Swap it to dejikstra or what?

→ Reply

4 years ago, # |

I solved D with min-cost-max-flow, 0.7/2.0 seconds. Is it possible to hack?

→ Reply

Runtime_terror_

4 years ago, # |

← Rev. 2 →

Can anybody explain how to solve D

→ Reply

ZincJ

4 years ago, # ^ |

pD and Edu#97 pC is almost the same.

Maybe the Editorial here ( https://mirror.codeforces.com/blog/entry/84149 ) may help you.

→ Reply

old._.monk

4 years ago, # |

← Rev. 2 →

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

→ Reply

coder_aman001

4 years ago, # ^ |

← Rev. 2 →

0 0 1 1 0 1

WA on this test case

→ Reply

Doltferns

4 years ago, # |

Why is this O(N^2) code giving TLE on TC5? :( https://mirror.codeforces.com/contest/1525/submission/116381276

→ Reply

saksham441

4 years ago, # |

Can anyone tell me why my dp solution fails in D?

→ Reply

Subarna578

4 years ago, # ^ |

I tried greedy. It failed too. DP should work.

→ Reply

4 years 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.

→ Reply

bobbilyking

4 years ago, # ^ |

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.

→ Reply

Into_Your_Arms

4 years ago, # ^ |

I loved it However I was not able to solve it :)

→ Reply

4 years ago, # ^ |

+18

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.

→ Reply

4 years ago, # ^ |

+13

If you have experience in coding cleanly, then absolutely none of the things you listed should be more than trivial issues.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+24

I just hate this problem, so I tried to find some reasonable reasons to hate it :)

→ Reply

4 years 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!

→ Reply

SuperJ6

4 years ago, # ^ |

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.

→ Reply

kumasento

4 years ago, # ^ |

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 :)

→ Reply

4 years 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.

→ Reply

MagentaCobra

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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.

→ Reply

Clix

4 years ago, # ^ |

+21

dude, the problem was fine & case handling was nice in my opinion and i liked the problem!

→ Reply

jimm89

4 years ago, # ^ |

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.

→ Reply

Subarna578

4 years ago, # |

What the hell is the "Test Case 8" for D?

→ Reply

bluescorp

4 years ago, # ^ |

+16

Something that fails for greedy and works for dp?

→ Reply

OleschY

4 years ago, # ^ |

My greedy attempt managed to pass up to testcase 31 :D

→ Reply

https://mirror.codeforces.com/blog/entry/84149

4 years ago, # ^ |

It was the first test case which don't work for greedy approaches.

→ Reply

Codeforcer

4 years 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.

→ Reply

SuperJ6

4 years ago, # ^ |

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.

→ Reply

Codeforcer

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

ZincJ

4 years ago, # ^ |

Hungarian algorithm may be the solution in O(n*log n).

I've seen the similar problem and solution in Edu#97 problem C.

→ Reply

4 years ago, # ^ |

I solved it using DP

→ Reply

4 years 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}$$$.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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?

→ Reply

4 years ago, # ^ |

Thanks, it got clarified here — https://mirror.codeforces.com/blog/entry/90729?#comment-791731

→ Reply

012199

20 months ago, # ^ |

Problem D:

Wrong ans on test 37

Can you pls tell me where i was wrong ?

Submission Link : 198729784

Thanks in Advance .

→ Reply

4 years ago, # ^ |

← Rev. 3 →

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

→ Reply

kumasento

4 years ago, # |

Nice contest! Really educational. I always thought this is for div3 (< div2 since it is educational) but apparently the difficulty is around div2.

→ Reply

Into_Your_Arms

4 years ago, # |

Hack my D! otherwise I may become Expert.

→ Reply

StArChAn

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

Into_Your_Arms

4 years ago, # ^ |

$$$Numbers\,Never\,Lies.$$$ If my potential is of expert level then I will definitely become someday. There is no hurry(I have huge patience).

→ Reply

StArChAn

4 years ago, # ^ |

That is true! All the best to you!

→ Reply

Makha

4 years ago, # |

+25

The problems diffucilty was like that :

→ Reply

4 years ago, # ^ |

+20

I think D was comparatively easier

→ Reply

rishavjnv12

4 years ago, # ^ |

I solved D faster than B

→ Reply

4 years 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 spoiler

→ Reply

ILoveBitches

4 years ago, # ^ |

+15

I was the victim of that bait :)

→ Reply

4 years ago, # ^ |

+46

I was a victim of that bait while introducing and preparing the problem.

→ Reply

4 years ago, # ^ |

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.

→ Reply

TheScrasse

4 years ago, # ^ |

Link to comment

→ Reply

4 years 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://mirror.codeforces.com/contest/1525/submission/116376637 if you need more detail.

→ Reply

Non-origination

4 years ago, # ^ |

← Rev. 2 →

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://mirror.codeforces.com/contest/1525/submission/116385486

→ Reply

TheScrasse

4 years ago, # |

← Rev. 5 →

+69

Solutions to A-E

1525A - Potion-making

Spoiler

1525B - Permutation Sort

Spoiler

1525C - Robot Collisions

Spoiler

1525D - Armchairs

Spoiler

1525E - Assimilation IV

Spoiler

→ Reply

4 years ago, # ^ |

For Problem D:

Any reason why this holds true?

The relative order of people remains the same in the optimal configuration.

→ Reply

TheScrasse

4 years 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.

→ Reply

4 years ago, # ^ |

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

→ Reply

threshold

4 years ago, # |

First time i able to solve D in any Educational round,

→ Reply

adiagr

4 years ago, # ^ |

How to identify if we have to apply dp on any problem? If i could figure this out i would have solved it too!

→ Reply

4 years ago, # ^ |

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.

→ Reply

Nawaz19

4 years ago, # ^ |

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

→ Reply

adhvana

4 years ago, # |

← Rev. 4 →

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)$$$

→ Reply

pranav.vinchurkar

4 years ago, # |

Lol E is easier than C and D

→ Reply

rananjay23

4 years ago, # |

← Rev. 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

→ Reply

harshitkapoor

4 years ago, # |

116407151 why I am getting RT at testcase 11 ?

→ Reply

Non-origination

4 years ago, # ^ |

Due to recursion limit in python. However, even after increasing recursion limit your solution TLE's in testcase 31 https://mirror.codeforces.com/contest/1525/submission/116412562

→ Reply

ajay_5097

4 years ago, # |

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.

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?

→ Reply

4 years ago, # ^ |

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.

→ Reply

sober_phoenix

4 years ago, # ^ |

← Rev. 8 →

consider this input :

0 0 0 1 1 1 0

→ Reply

ajay_5097

4 years ago, # ^ |

← Rev. 2 →

-24

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.

7
0 0 0 1 1 1 0

→ Reply

aryan57

4 years ago, # ^ |

please put your code in spoilers. Otherwise it makes the comment section unnecessary lengthy.

→ Reply

sah10

4 years 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!!!

→ Reply

adarshsinghkushwaha

4 years ago, # |

can any one tell why i am getting tle on test case 26 in Problem D Armchairs. 116422974

→ Reply

sudharsansrikanthan

4 years ago, # ^ |

while passing the vectors in the function use call be reference method otherwise the whole vector will be copied in every function call. 116426242

→ Reply

harshitkapoor

4 years ago, # |

116419179 why I am getting MLE ?

→ Reply

i.am.pratik

4 years ago, # ^ |

You're missing this line if(dp[i][j]!=-1){ return dp[i][j]; }

→ Reply

harshitkapoor

4 years ago, # ^ |

Still same issue

→ Reply

i.am.pratik

4 years ago, # ^ |

Firstly you need to initialize every element of dp with -1. Then only that check will work

→ Reply

pajenegod

4 years ago, # ^ |

← Rev. 2 →

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).

→ Reply

4 years ago, # |

Do failed hacks decrease my place/rating?

→ Reply

alamkhan

4 years ago, # ^ |

→ Reply

sam000013

4 years ago, # ^ |

The hacks do not affect your score in div3/edu rounds.. I learnt it the hard way

→ Reply

-3en_7oras-

4 years ago, # |

i think problem C was so hard for being C in div2

→ Reply

4 years ago, # ^ |

Problem D was easier than the problem C.

→ Reply

huikang

4 years ago, # |

← Rev. 2 →

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)

→ Reply

4 years ago, # ^ |

It's really strange.

→ Reply

sam000013

4 years ago, # ^ |

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.

→ Reply

jimm89

4 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

Ilnay

4 years ago, # |

Why is this competition unrated?

→ Reply

alamkhan

4 years ago, # ^ |

Wait.System test is still pending.

→ Reply

jsambhav5

4 years ago, # ^ |

When will the final ratings for this contest be released?

→ Reply

Ilnay

4 years ago, # ^ |

OK,thank you.

→ Reply

Evil_Hunter

4 years ago, # |

← Rev. 2 →

+12

D is uses same idea https://mirror.codeforces.com/problemset/problem/830/A

→ Reply

saisanjith

4 years ago, # |

Please can someone explain me in an easy way to solve D.

→ Reply

coderboss

4 years ago, # ^ |

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.

→ Reply

saisanjith

4 years ago, # ^ |

Thanks for explaining the solution.

→ Reply

apoorva222g

4 years ago, # |

When will the ratings be updated

→ Reply

4 years ago, # ^ |

System test is still pending. Once it will get complete ratings will get updated. (We should ask for editorials rather than updating ratings)

→ Reply

4 years ago, # |

Is the System test done?

→ Reply

mr_no_code

4 years ago, # ^ |

Not yet started

→ Reply

4 years ago, # ^ |

Thanks. But hacking phase was over well before 6 hrs. I guess. I thought it was done. Thanks for clarifying.

→ Reply

10000point

4 years ago, # |

why didn't i get points after i finish the competition? (1 ranked 3500) please help me. i'm new here

→ Reply

ZincJ

4 years ago, # ^ |

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.

→ Reply

aksingh123

4 years ago, # ^ |

← Rev. 2 →

it did not work it show Good luck & high rating! every time

→ Reply

HemantKumar01

4 years ago, # ^ |

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

→ Reply

iamarjun45

4 years ago, # |

Is the editorial released for this contest?

→ Reply

Log_ZOOM

4 years ago, # |

Can someone explain the problem D for me ? like the state and the transition of the dp !

Thanks

→ Reply

https://mirror.codeforces.com/blog/entry/90729?#comment-791594

4 years ago, # ^ |

Check this comment.

You can refer to my code for the implementation part. 116414468

→ Reply

multibagger

4 years ago, # ^ |

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!

→ Reply

4 years ago, # |

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.

→ Reply

Haok

4 years ago, # |

I am under 2100 but my rating didn't change, can someone tell me why is that?

→ Reply

Haok

4 years ago, # ^ |

And why is there no editorial?

→ Reply

Last_whisper

4 years ago, # ^ |

i think the raing will update soon.

→ Reply

Haok

4 years ago, # ^ |

Thanks

→ Reply

abhinavxd

4 years ago, # |

editorial?

→ Reply

ZaiaF_Rahman

4 years ago, # |

No editorial?

→ Reply

flea_bag

4 years ago, # |

When will we see the rating change for this round?

→ Reply

4 years ago, # |

-7

Eagerly waiting for editorial .

→ Reply

4 years ago, # |

← Rev. 2 →

-8

→ Reply

awoo

4 years ago, # |

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply