did you?

I will choose the red pill. As my logic is right so I just need to optimize my code a little and boom Accepted.

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

Скорее всего да, время старта совпадает

did you?

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

They were solving CodeChef Long Challenge Questions. lol

Will you participate, btw?

Good time for people with fucked up sleeping schedules like me! :D

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.

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

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

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)

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

Yes, i wrote this.

pD and Edu#97 pC is almost the same.

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

6

0 0 1 1 0 1

WA on this test case

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

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.

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.

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.

Something that fails for greedy and works for dp?

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

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.

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

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

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.

I think D was comparatively easier

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.

For Problem D:

Any reason why this holds true?

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

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

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

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

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]; }

Your problematic line is setrecursionlimit(10**6).

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

No

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

Problem D was easier than the problem C.

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.

Wait.System test is still pending.

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.

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