Огромное спасибо всем, кто участвовал! Это правда важно для меня. Если после разбора у вас остались какие-то вопросы, не стесняйтесь писать мне на codeforces/в вк/gmail.
877A - Леша и сломаный контест
Разбор задач Codeforces Round 442 (Div. 2)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
What is test 49 in D(it is long hence not visible)? NOTE: Ignore got it.
if you have figured it out can you tell me the case?
Not sure, but after finding the way to pass this test i got AC.
How is BFS too slow for D? 31650245 is BFS, but it doesn't time out.
Nice, the essential part in this submission is to stop when
!(dist[i][y]>=dist[x][y]+1)Wow, I got mine to pass when I added that, but I don't understand why that works. Could you give a little explanation?
When
dist[i][y] < dist[x][y] + 1all the consecutive points either have been updated from i,y already or will be updated from i,y in the future. Thus we can stop.My solution for D (O(n*m)):
http://mirror.codeforces.com/contest/877/submission/31659168
can you please explain a little !
it will be helpful for beginners:)
Any specific reason for deque? I guess the logic works fine without that as well ?
Basically, a BFS works because always elements in the queue are ordered by distance, for the I_LOVE_NICKY_MINAJ's implementation when you are in a state is possible to go to another state in which your distance isn't affected, that is your new distance is equal to the current distance, so to maintain your queue ordered, you need to add the next state to the front of the queue. Using a deque is a useful trick for some BFS.
My solution for D (O(n*m*k) ) =).
http://mirror.codeforces.com/contest/877/submission/38798575
If someone would be kind enough to tell me what went wrong with my E submission (http://mirror.codeforces.com/contest/877/submission/31648193). Thanks
see your accepted code . problem is when you are propagating lazy down you are not checking whether it is leaf. see the code you can see yourself , it is a minor mistake
Can you provide a java solution for problem F that passes the time limit? I think this submission is the same as described in the editorial and it gets TLE.
Man, you should have known that java is bit slower than c++. I think usage of inappropriate language is only your problem.
Arrays.sort()can work up to O(n2)Never. If the passed array is a primitive array, then the used sorting algorithm is Quick sort which has the worst-case complexity as you just mentioned. If the passed array is an object array, then Merge sort is used which is the case in my submission. You can jump into which Arrays.sort() function called by the code and check yourself.
NO
When I run this solution on all tests, it gets a lot of REs with the following error:
I believe that is the problem that causes TLs as well. C++ solutions work 200-500ms, I don't think Java solution will work more than 5 times slower.
I got the problem. There was a bug in the implementation of the comparable function. Thanks!
Well, your sorting is just incorrect for Mo's algorithm. It should sort by
block, but it sorts byl.Yes, exactly
Problem D
Test case 31?
invalidfunction also checks for visited points, but there might be some unvisited reachable points which are farther than first visited point. Do not think that reordering of direction array will help :)thx
the visit order may be the cause. So you need to memorize the direction too, seen[f][c][d] and that should fix it.
Can you please explain why do we need to save direction, too?
Well, one of the reasons is because you can calculate the cost in order and be sure is good calculated. What I mean is, if you keep moving in the same direction, you go with cost 0, but if you change the direction, your cost increases in one. (Now you can use bfs 0-1). Now, note that if you don't do this (only save row and column), it can be possible that you reach a cell with a cost greater than other, and because you reached that cell first (because of bfs) with greater cost, you assume that is the best way to reach that cell, but that might not be the best option.
So basically you need to separate the two kinds of costs, 0 for same direction, 1 for other direction.
I'm thinking maybe if you use a heap instead of queue to process in order, the dimension of the directions may be not needed (Is a thought. You can test it. Because basically the bfs 0-1 is a dijsktra but with special costs.)
Is it clear?
Thank you a lot for such a great response & I'm really sorry for my so long one.
Everything is pretty clear, but I still didn't get the idea why I should save direction.
Because let's assume that we stay in state (x, y), and we'll just brute force some count in range[1; k] and anyway we'll do +1 to our adjacents to which we can go in one step.
Well, Actually it depends on how you implement your solution, can you show me your code?
I remember the first solution I submitted I tried to only save x and y, but I had a mistake about when to stop (check this comment and the response ), because if we do what you say, we will got TLE, right?
here's my submission: 36150483
I did some modifications to your code (here). The thing is that the stop condition was wrong.
Now, you have good the idea, but the order of checking the cells may be wrong in some cases. Look at my code (here) Basically what I do is use another dimension to do the for-loop that you have, is like doing the for-loop but implicit.
So the problem is some like this:
You can arrive position {x,y} in 2 ways and with the same cost. But depending how many movements of k you had used they are different and you can't break the for-loop.
Wow, thank you so much, I struggled with this problem for a long time!
Thanks Temirulan and -osdajigu-. Got AC
Any implementation as mentioned in Editorial..... Thanks.
Does anyone have any idea why this- http://mirror.codeforces.com/contest/877/submission/31647784 gave WA on test 49?
Why didn't it give TLE?? My implementation is almost same but i get TLE on test 48.
http://mirror.codeforces.com/contest/877/submission/31654408 If you can point out the mistake that would be really helpful
While you are taking k steps from the current cell(the one currently at the front of the queue), if you come across a cell that is already visited, you break out of the loop. That is incorrect because you are expecting the cells beyond that visited cell to get their distance equal to the distance of visited cell +1. However the distance of visited cell could have been one more that the distance of current cell. Answer for all the unvisited cells beyond the visited cell could end up being one more than it was supposed to. I made the same error. You can check out the codes
Incorrect Correct
LOL, For 5 seconds I was waiting to load the tutorial of problem C. :P
Proof of optimality for Problem C ?
The problem is equivalent to finding a string S such that for all 1 < i ≤ n, i - 1 precedes i somewhere in the string and i precedes i - 1 somewhere in the string.
Now observe that for some i, it occurs either 1 or 2 times in the optimal string. If it is more than 2 times, we can erase the middle ones and obtain a better string.
If for some i, the number of times is 1, then i + 1 must occur (at least) 2 times: to the left of this location and to the right. If i occurs 2 times, then i + 1 must occur (at least) once (in between the two occurences).
From this, you can build the string 2,4,6,... 1,3,5,..., 2,4,6, ... which is therefore optimal.
At every step we get some partial string with all the numbers from 1 to i. Inductively you can show that this is optimal at every transition to i + 1.
Can you please explain, how did you reduced the given problem to equivalent string problem?
Suppose there are 2 tanks at every location i. Suppose on first hit, the first tank moves to the left, the other moves to the right. This is the worst case of tank positioning, so if this case is handled by the string, it is handled by every configuration of tanks.
To erase the first tank from location i, we have to bomb location i. After this, the first tank moves to location i - 1 so this one has to be bombed after i is bombed. Likewise, to bomb the second tank, we have to bomb location i at some point, and after that we still have to bomb i + 1. You can substitute i with i - 1 to obtain that i - 1 has to precede i at some point in the string.
The optimal bombing will fix this situation I described here, so it will obey the cosntraints on the string I described. On the other hand, if the constraints are met for a string S, then a bombing plan will be a 'good' bombing plan.
It is easy to notice that we have to hit atleast 3 times in each pair of neigbor cells.
That is why answer is atleast 3*n/2 (+1 if n is odd).
Can someone provide the recurrence formula for B with DP?
Never mind, figured it out!
Could you provide the formula? Brute force soln in tutorial is n^2 and gets Timed out.
The same code when written in C++ passes with a time of 46 ms, but gives TLE in python. From what I have read online, Python is only 5 times slower than C++. Why does this happen? 31662096 31662142
On other platforms like Codechef, for Python time is 5x of C/C++ Anyway, I see a lot of solution with single loop, but cannot understand the logic :(
Still, even without the multiplier, the python code should be roughly 5x slower. And it should easily pass O(n^2) for n=5000
Actually no. python is roughly 100 times slower.
DP Solution O(N): I hope this is quite clear! 31663633 Simple Bruteforce O(N^2): 31642282
I know u probably dont care since this contest is 2 months old but thanks for posting your dp solution. I had a tough time trying to come up with the dp solution, i got close tho :( Btw i think
dp[2][i]doesnt gives u the max count of (b) unless u makedp[2][i + 1] = max(dp[1][i] + s[i]=='b', dp[2][i]) + (s[i] == 'a')Actually I had to go through it again to remember what my recurrence were lol xD. My idea was to find the best that ends with prefix
(a, ab, aba)in that specific order. That modification you made was already handled in the second line where it was supposed to end withb, it's unnecessary! Thanks for bringing that interesting problem again to my mind :)А можно нормальное доказательство C ?
For problem C what if i throw bombs on all cells starting from last to first and then again in the 2nd cell.It gives n+1 as my answer.
What if the tank is in the cell 2 and moves to cell 3?
I think it's given in the question that a tank in cell n can move to only cell n-1 except for 1 wherein it moves to 2
A tank in cell n can move to n - 1
A tank in cell 1 can move to 2
A tank in cell 2 ≤ i ≤ n - 1 can move to either i - 1 or i + 1
I have the same doubt, for 4 cells shouldn't the optimal placement of bombs be, 2 4 3 1 2 ?
When you hit cell 3, the tank inside it might move to cell 4 and not get hit after that.
can someone please provide the code for D
I am totally missing the point of how the sets are used.
I don't get it. Isn't the following also easy? (PSEUDOCODE)
It is easy to find all unvisited cells from the current cell (ri, ci) in O(n). Right?
It looks like I fundamentally don't understand what we are looking for and why do we need sets for that.
Ultimately we need to fill the matrix dist[N][M] and we can reach every single one of dist[r][c] from adjacent cell in O(1).
I know that dist[r1][c1] = 0 and all of the vertical cells dist[r1 ± i][c1] and horizontal cells dist[r1][c1 ± i] have distance 1 (unless they aren't too far from (r1, c1)). This is the point zero in my current understanding. Could you please, elaborate what do we do starting from that understanding?
First, simple, but slow BFS solution: just connect each cell to the cells with distance no more, than k, in each direction and simply run BFS on this graph. This will run in O(nmk), because for every n·m node we will check O(k) adjacent nodes.
So for each row and column, let's put all nodes, that are not already reached by our bfs process, into set. Then, when we take node from queue, we look to the nearest not reached neighbour in each direction (can be done with log(set size) via
set::lower_bound) and if the distance is no more, than k, extract it from its both sets, put into queue and continue looking for the new nearest neighbour. So in each step we look at 4 + number of extracted in this step nodes. And total sum of extracted nodes is no more, than total nodes count (after we extract node, we will never look at him again).Hi! As a tester, I enjoyed solving the problems. Thanks to the author (Livace), the contest was really good in my thought.
It could be better to swap D and E. Anyway, E and F were technical problems (i.e. E needed fenwick Or segment tree, F needed MO), D was creative, and maybe hard to code, A, B and C were straight-forward.
To summarize, I think it was the best contest I've tested if I remember correctly.
Can you please explain how to flip 1 and 0 using fenwick and then get the count of 1? i solved it using segment tree but would like to know solution using fenwick trees(i know how to do range updates in fenwick like if i wish to add a particular value to a range l to r but cant get any idea of how to flip)
Sorry, I wrote fenwick accidentally, I haven't a solution with fenwick for this problem. Sorry again.
Oh, no problem, i thought it could be done using fenwick as in this link also in description it was mentioned it could be done using fenwick.
Hi! In D BFS with some breaks passed in 77 ms. Proof. Was this intended? Because I can understand the solution from editorial and why it works, but face some problems trying to estimate complexity of such bfs.
This condition
if(ans[ni][nj] < ans[v.fi][v.se] + 1) break;gives you O(nm) complexity. Because consider cell's ans is x, than throught entire algorithm's work you will visit this cell no more than 4 times: one for each of 4 directions from the nearest cell in this direction with ans = x - 1.I think D can be solved in O(nm) simply by using BFS 01. If we add a coordinate to the matrix where we remember the direction from which we came from, 0 — 3. So now simply every time we change the direction we add one to the solution and when we keep the direction we treat it as a 0 edge and add it to the front of the deque.
UPDATE: My mistake. Seems like I didn't read the problem statement carefully enough.
How do you make sure you won't move more than k steps in one direction?
I think that you have to save 4 values for each element inserted in the queue, row, column, direction, and movements. So every time you pop an element from the queue, you can make a movement in the same direction iff movements < k, or start a new movement in other direction. And you only memorize the row, col, and direction. If you change direction, it cost 1, but go in the same direction, 0
Hi, what is necessary you remember the direction, why not simply do a for(loop), for each position up to K in 4 directions and if you get an already visited cell, stop the loop?
UPDATE: I found a case when it is necessary
Actually this is the solution I used in the contest, but you shouldn't stop the loop when you reach a visited cell, you should stop when you reach a visited cell with distance less than or equal to your current distance.
for problem number C. let's assume n = 6. now throw bombs in all even positions now all tanks are in 1 3 and 5 positions. now throw bombs in 1, 3, 5 positions. now the tanks are in 2 and 4 positions, isn't it? cause it's said that tanks in the cell n can be moved only to n-1 position and tanks in cell 1 can be moved only to 2 cell.now throw bombs in 2 and 4 positions. please tell me why I throw a bomb in position 6 again? why I waste a bomb? why is the answer not 8?
5 ≠ n
tank can move from 5 to 6
why? it's said in the problem statement that tanks on position n can be moved only to position n — 1.
(a tank in the cell n can only move to the cell n - 1, a tank in the cell 1 can only move to the cell 2)
in the cell n, not in the cell i
get it. thanks:).
Could someone please explain how B can be solved in Linear time? I get Time Limit exceeded for the editorial solution which is O(n^2)
nmax = 5000, so some languages could be not fast enough for solving this problem.
How could people implement E in 10-15 minutes during the contest? I used segment tree with lazy propagation, and it took like 1 hour to code, and another 1 to debug. The latter could be avoided, but even if I coded faster, 10-15 minutes seems impossible.
I checked fast solvers submissions, but they used one character variable names, and unusual spacing, so I couldn't really understand their solution.
Could someone explain a faster to implement solution? Or did they have pre-implemented lazy prop?
It's a pretty famous problem. click
Well, this lazy propagation is kinda straightforward :)
Check mine: 31644977
Coded it in 18 mins.
If you solve some (10+ at least) tasks which require implementing segment tree with slice operations (which require lazy propogation), you'll be able to implement it much faster and much more bugless.
Can you list some of them , maybe on SPOJ or somewhere
BFS is enough for D number. http://mirror.codeforces.com/contest/877/submission/31656756
For me straightforward bfs passed too, in 1560 ms. Looks like constraints should have been a tad higher if bfs was not an intended solution.
Can you give some explanation why it works?
BFS nice, but can someone prove that it's enough?
Можете объяснить, что такое Эйлеров обход?
Это последовательность вершин в порядке захода дфса в них.
Спасибо
why i keep getting memory limit exceeded on problem D? is it because too many queue?
31659292 877B - Никита и строка Hey can somebody help me find out what is wrong with my solution to B — Nikita and String. I got wrong answer in test case 37. Thanks.
You missed the case when the string contains only letter "a"s. You are always trying to take the number of 'b's on a non-empty substring.
Any implementation of problem D as mentioned in Editorial. Thanks...!
in F how left border can be moved easily??
let current left is l, updating l to l + 1 removes a[l] from all prefixes so all cnt values should be updated which should be O(r — l).
how is this done efficiently?? or i'm missing smthng.
No,you don't need to update all content values. Remember, you store the prefixes of the complete array. If your l changes, the prefixes are still all correct. However now you look for indices i>l with presum[i] — presum[l] = k. So you need to add cnt[k + presum[l]] instead of cnt[presum[r] — k] to your result.
thanks got it!!
Why is my code giving RE for test 5 in [problem:D].
You can compare with my code http://mirror.codeforces.com/contest/877/submission/31849869
I think that E can be solved using sqrt decomposition but I can't do it.
Can someone help me please each time I submit this 31659189 code I get RE on a different test. I don't know what's wrong and the code is working on my mechanic. When I get RE on some test I use the test in costume test and it works. It's really weird.
I found what's wrong now I'm getting WA on 14 if someone could help I would really appreciate it. here's my new submission 31687428.
I used unorder_map instead of map for F,but I still got TLE.I want to know unorder_map is very slow on codeforces?
Sometimes using reserve and max_load_factor can reduce the time of unordered map .
mapname.reserve(1<<16);
mapname.max_load_factor(0.25);
Arpa's blog has a nice tutorial about it .
unordered_map has a big overhead. Quite often it will even be slower than map, even though the complexity is better.
why did my solution get TLE http://mirror.codeforces.com/contest/877/submission/31697709 for F? \n used unordered_map
In problem E,Can someone guide me on how to form segment tree from given tree ?
Use the dfs order where a subtree will be in a continuous range.
Can you elaborate your idea a bit more pls?
Dfs order is a sequence obtained by recording every node when it's searched using dfs. (I am not sure whether people outside China call it dfs order.) Then we find out that all nodes of a subtree are in a continuous range in that sequence. Now it's changed into a sequence problem which can be done with a segment tree.
Can you provide me some useful link (english)?
maybe this one can help you.
thank you
No problem.
BFS why i have Memory limit exceeded on test 5 ? 31660164
and why i have AC if i use std::set<std::pair<int, std::pair<int, int> > > ? 31660401
It could be because of duplicate elements in your
std::queue.First looking at the solution for D and E, I think it is very unclear. But then after thinking for a while, i got the answer.
We can solve F by using Mo's algorithm if we discretize the numbers first..
Could someone tell what test case number 46 for D is? :| I've been thinking on it for a long time with no avail :/ http://mirror.codeforces.com/contest/877/submission/31757764
Here is my thought on the problem div2E (div1C): http://robezhang.blogspot.com/2017/10/segment-tree-with-lazy-propagation.html
Regarding Problem D solutions
which do not use ordered sets mentioned in the tutorial.
I tried to understand why we can not stop early (after we encountered a cell which had been assigned a non-infinity value already).
Finally, I found this test case useful:
where
sanddare the source (x1, y1) and the destination (x2, y2) correspondingly, K > 1.I suggest that this test case (in its eight versions) is a good way to quickly check an early stopping solution for correctness.
I think it would be better if all of these were present in tests (the right answer is obviously
2for K > 1, badly optimized solutions will return3on one or more of these tests):For those interested
32651366 is my example of a wrong optimization. Changing break to continue on the following line will pass the #31 test:
(It will then unsurprisingly fail on #48 due to time limit, as in 32653183.)
A working solution is 32658046 (78 ms). There are now two matrices where we maintain achieved costs (one for horizontal directions, one for vertical ones).
The queue size is also doubled.
Honestly, I do not know (can not prove) why that works. (Please help if you do know.)
The following is the workaround for this kind of a case:
Stop iterating over the neighbors not when you reach an already visited cell but when you reach a visited cell with distance less than or equal to your current distance (more precisely if a vertex's distance is not equal to the current vertex's distance + 1). Here and here are the submissions for this way and here is the reason why it works in O(n * m) time.
how u solved F ? roll_no_1
I understood it from the editorial and coded it. It requires the knowledge of MO's algorithm which you can read about here.
Hi, I know this is an old contest but I've been trying to do problem E for days now and I would really appreciate some help. I am getting TLE on test case 13 (Code takes over 30 sec). However, I can't tell what is wrong with my complexity. I'm really stuck ): http://mirror.codeforces.com/contest/877/submission/33872973
I solved it similarly — this 279988202 might help :)
Can someone explain how to solve F using flows?
Can anybody please tell me what is wrong with my DP solution for div2 B? I am getting WA on case 15. Here is the code. 39735958
Why isn't the answer for C, n+1, i.e, if you drop a bomb from the nth cell then on the n-1,n-2, — — — ,2,1,2. Won't that destroy all the tanks? I can't see why I am wrong. Any help appreciated.
Tank from cell n - 1 can move into cell n, so it won't be destroyed
.
In problem D, instead of using sets to find the nearest unvisited neighbor in each direction, we can also use DSU (Disjoint Set Union) for each row/column in which every cell would point to the next unvisited cell, you can follow this link for more details about how DSU can be used for this purpose.
Submission for reference: 101039018
Thanks bro
problem F: can someone explain me how to solve this problem in O(n.q.log(n))? i don't understand the solve above
Use map for F will result TLE lol, you should compress the prefix and pre calculate the next and previous of a(i). That's way better.
About Problem D:
My submission 234897503 is Accepted but I was wrong in this test:
The correct answer is 2 but my output is 3. Can you add this test to this problem