### Livace's blog

By Livace, history, 5 years ago, translation,

Massive thank you to all who partisipated. It's really important for me. If you still have questions after reading editorial, feel free to write me using codeforces/vk/gmail.

877A - Alex and broken contest

tutorial

877B - Nikita and string

tutorial

877C - Slava and tanks

tutorial

877D - Olya and Energy Drinks

tutorial

877E - Danil and a Part-time Job

tutorial

877F - Ann and Books

tutorial

• +75

 » 5 years ago, # | ← Rev. 2 →   +4 What is test 49 in D(it is long hence not visible)? NOTE: Ignore got it.
•  » » 5 years ago, # ^ |   0 if you have figured it out can you tell me the case?
•  » » » 5 years ago, # ^ |   +8 1000 1000 1000 ......(....).....# ......(....)...... ......(....)...... ......(....)...... ......(....)...... 1 1 1000 1000 Not sure, but after finding the way to pass this test i got AC.
•  » » » » 5 years ago, # ^ |   0 Thank you so much!!!
 » 5 years ago, # | ← Rev. 2 →   +17 How is BFS too slow for D? 31650245 is BFS, but it doesn't time out.
•  » » 5 years ago, # ^ |   +6 Nice, the essential part in this submission is to stop when !(dist[i][y]>=dist[x][y]+1)
•  » » » 5 years ago, # ^ |   0 Wow, I got mine to pass when I added that, but I don't understand why that works. Could you give a little explanation?
•  » » » » 5 years ago, # ^ |   +2 When dist[i][y] < dist[x][y] + 1 all 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.
•  » » 5 years ago, # ^ |   0 Can you please tell me what's wrong in my code here? http://codeforces.com/contest/877/submission/31680763
 » 5 years ago, # | ← Rev. 3 →   +15 My solution for D (O(n*m)):http://codeforces.com/contest/877/submission/31659168
•  » » 5 years ago, # ^ |   0 can you please explain a little !it will be helpful for beginners:)
•  » » 5 years ago, # ^ |   0 Any specific reason for deque? I guess the logic works fine without that as well ?
•  » » » 5 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   0 My solution for D (O(n*m*k) ) =).http://codeforces.com/contest/877/submission/38798575
 » 5 years ago, # |   0 If someone would be kind enough to tell me what went wrong with my E submission (http://codeforces.com/contest/877/submission/31648193). Thanks
•  » » 5 years ago, # ^ |   0 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
 » 5 years ago, # |   +7 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   -35 Man, you should have known that java is bit slower than c++. I think usage of inappropriate language is only your problem.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Arrays.sort() can work up to O(n2)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 4 years ago, # ^ |   0 NO
•  » » 5 years ago, # ^ |   +14 When I run this solution on all tests, it gets a lot of REs with the following error: java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866) at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483) at java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:406) at java.util.ComparableTimSort.sort(ComparableTimSort.java:213) at java.util.Arrays.sort(Arrays.java:1246) at F.main(F.java:48) 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.
•  » » » 5 years ago, # ^ |   +1 I got the problem. There was a bug in the implementation of the comparable function. Thanks!
•  » » » 5 years ago, # ^ |   +35 Well, your sorting is just incorrect for Mo's algorithm. It should sort by block, but it sorts by l.
•  » » » » 5 years ago, # ^ |   +1 Yes, exactly
 » 5 years ago, # |   +16 Problem D
•  » » 5 years ago, # ^ |   +3 5 5 3 ..#.. ..... ..... ..... ..... 3 3 1 2 invalid function 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 :)
•  » » » 2 years ago, # ^ |   0 thx
•  » » 5 years ago, # ^ | ← Rev. 2 →   +9 7 14 14 XXXXXXXX..XXXX XXXXXXX...XXXX XXXXXX..X.XXXX XXXXX.....XXXX XXXX..X...XXXX XXXXXXXXX.XXXX XXXXXXXXX.XXXX 1 9 7 10 the visit order may be the cause. So you need to memorize the direction too, seen[f][c][d] and that should fix it.
•  » » » 4 years ago, # ^ |   0 Can you please explain why do we need to save direction, too?
•  » » » » 4 years ago, # ^ |   0 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?
•  » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » 4 years ago, # ^ |   +1 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?
•  » » » » » » » 4 years ago, # ^ |   0 here's my submission: 36150483
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » » » » » » » 4 years ago, # ^ |   +3 Wow, thank you so much, I struggled with this problem for a long time!
•  » » 5 years ago, # ^ |   0 Thanks Temirulan and -osdajigu-. Got AC
•  » » 5 years ago, # ^ |   0 I failed the same one;(
•  » » 5 years ago, # ^ |   0 Any implementation as mentioned in Editorial..... Thanks.
•  » » 5 years ago, # ^ |   0 if your solution fails this test case you should not break the loop when a neighbouring cell is already visited just ignore it and move to the next one. just remove the test on vis[x][y] and you should get a TLE without using set .
 » 5 years ago, # |   0 Does anyone have any idea why this- http://codeforces.com/contest/877/submission/31647784 gave WA on test 49?
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 Why didn't it give TLE?? My implementation is almost same but i get TLE on test 48.http://codeforces.com/contest/877/submission/31654408 If you can point out the mistake that would be really helpful
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 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
 » 5 years ago, # | ← Rev. 4 →   +5 LOL, For 5 seconds I was waiting to load the tutorial of problem C. :P
 » 5 years ago, # |   +6 Proof of optimality for Problem C ?
•  » » 5 years ago, # ^ |   +24 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.
•  » » » 5 years ago, # ^ |   0 Can you please explain, how did you reduced the given problem to equivalent string problem?
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » 21 month(s) ago, # ^ |   0 Can you explain directly how filling by an even-odd-even method is optimal?
•  » » 5 years ago, # ^ |   +3 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).
 » 5 years ago, # | ← Rev. 3 →   0 Can someone provide the recurrence formula for B with DP?Never mind, figured it out!
•  » » 5 years ago, # ^ |   0 Could you provide the formula? Brute force soln in tutorial is n^2 and gets Timed out.
•  » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   0 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 :(
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Still, even without the multiplier, the python code should be roughly 5x slower. And it should easily pass O(n^2) for n=5000
•  » » » » » » 5 years ago, # ^ |   0 There are few successful solutions in Python like: http://codeforces.com/contest/877/submission/31636672 They have used different approach
•  » » » » » » 5 years ago, # ^ |   0 Actually no. python is roughly 100 times slower.
•  » » » 5 years ago, # ^ |   +1 DP Solution O(N): I hope this is quite clear! 31663633 Simple Bruteforce O(N^2): 31642282
•  » » » » 4 years ago, # ^ |   0 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 make dp[2][i + 1] = max(dp[1][i] + s[i]=='b', dp[2][i]) + (s[i] == 'a')
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   0 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 with b, it's unnecessary! Thanks for bringing that interesting problem again to my mind :)
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   0 What if the tank is in the cell 2 and moves to cell 3?
•  » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   +6 A tank in cell n can move to n - 1A tank in cell 1 can move to 2A tank in cell 2 ≤ i ≤ n - 1 can move to either i - 1 or i + 1
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I have the same doubt, for 4 cells shouldn't the optimal placement of bombs be, 2 4 3 1 2 ?
•  » » » 5 years ago, # ^ |   0 When you hit cell 3, the tank inside it might move to cell 4 and not get hit after that.
•  » » » » 5 years ago, # ^ |   0 for 4 the ans can be 1 2 3 4 3 so the ans will be n+1
 » 5 years ago, # |   +1 can someone please provide the code for D
 » 5 years ago, # | ← Rev. 5 →   +1 I am totally missing the point of how the sets are used. Now it's easy to find all not visited cell which is reachable from vertex I don't get it. Isn't the following also easy? (PSEUDOCODE) int r_cur = queue.top().row; int c_cur = queue.top().column; queue.pop(); int dr[4] = {1, -1, 0, 0}; int dc[4] = {0, 0, 1, -1}; for (int dir = 0; dir < 4; dir++) { for (int len = 1; ; len++) { int r = r_cur + len * dr[dir]; int c = c_cur + len * dc[dir]; if (!empty[r][c] || !valid(r, c)) break; if (dist[r][c] > cur_dist + len) { dist[r][c] = cur_dist + len; queue.push({r, c}); } } } 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?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 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).
 » 5 years ago, # |   +43 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.
•  » » 5 years ago, # ^ |   +3 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)
•  » » » 5 years ago, # ^ |   0 Sorry, I wrote fenwick accidentally, I haven't a solution with fenwick for this problem. Sorry again.
•  » » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   +5 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.
•  » » » 5 years ago, # ^ |   +12 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.
 » 5 years ago, # | ← Rev. 2 →   +9 My idea for DI 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.
•  » » 5 years ago, # ^ |   0 How do you make sure you won't move more than k steps in one direction?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   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
•  » » » 5 years ago, # ^ |   +3 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.
 » 5 years ago, # |   0 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 years ago, # ^ |   0 5 ≠ ntank can move from 5 to 6
•  » » » 5 years ago, # ^ |   0 why? it's said in the problem statement that tanks on position n can be moved only to position n — 1.
•  » » » 5 years ago, # ^ |   0 (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)
•  » » » » 5 years ago, # ^ |   0 in the cell n, not in the cell i
•  » » » » » 5 years ago, # ^ |   0 get it. thanks:).
 » 5 years ago, # |   0 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)
•  » » 5 years ago, # ^ |   0 nmax = 5000, so some languages could be not fast enough for solving this problem.
•  » » » 5 years ago, # ^ |   0 Most people implemented a O(n) solution, but I did not understand their logic :(
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 It's a pretty famous problem. click
•  » » 5 years ago, # ^ |   0 Well, this lazy propagation is kinda straightforward :)Check mine: 31644977Coded it in 18 mins.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 years ago, # ^ |   +4 Can you list some of them , maybe on SPOJ or somewhere
 » 5 years ago, # |   0 BFS is enough for D number. http://codeforces.com/contest/877/submission/31656756
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 Can you give some explanation why it works?
•  » » 5 years ago, # ^ |   0 BFS nice, but can someone prove that it's enough?
 » 5 years ago, # |   0 why i keep getting memory limit exceeded on problem D? is it because too many queue?
 » 5 years ago, # |   0 31659292 877B - Nikita and string 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.
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 Any implementation of problem D as mentioned in Editorial. Thanks...!
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 thanks got it!!
 » 5 years ago, # |   0 Why is my code giving RE for test 5 in [problem:D].
•  » » 5 years ago, # ^ |   0 You can compare with my code http://codeforces.com/contest/877/submission/31849869
 » 5 years ago, # | ← Rev. 2 →   0 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.
 » 5 years ago, # |   +3 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?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 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 .
•  » » 5 years ago, # ^ |   0 unordered_map has a big overhead. Quite often it will even be slower than map, even though the complexity is better.
 » 5 years ago, # |   +1 why did my solution get TLE http://codeforces.com/contest/877/submission/31697709 for F? \n used unordered_map
 » 5 years ago, # |   0 In problem E,Can someone guide me on how to form segment tree from given tree ?
•  » » 5 years ago, # ^ |   0 Use the dfs order where a subtree will be in a continuous range.
•  » » » 5 years ago, # ^ |   0 Can you elaborate your idea a bit more pls?
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   0 Can you provide me some useful link (english)?
•  » » » » » » 5 years ago, # ^ |   0 maybe this one can help you.
•  » » » » » » » 5 years ago, # ^ |   0 thank you
•  » » » » » » » » 5 years ago, # ^ |   0 No problem.
 » 5 years ago, # | ← Rev. 3 →   0 BFS why i have Memory limit exceeded on test 5 ? 31660164and why i have AC if i use std::set > > ? 31660401
•  » » 5 years ago, # ^ |   0 It could be because of duplicate elements in your std::queue.
•  » » » 5 years ago, # ^ |   0 hm.... thank
 » 5 years ago, # |   0 We can solve F by using Mo's algorithm if we discretize the numbers first..
 » 5 years ago, # |   0 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://codeforces.com/contest/877/submission/31757764
 » 5 years ago, # |   0 Here is my thought on the problem div2E (div1C): http://robezhang.blogspot.com/2017/10/segment-tree-with-lazy-propagation.html
 » 4 years ago, # | ← Rev. 2 →   0 Regarding Problem D solutionswhich 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: s.# ..dwhere s and d are 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. The eight versions of the test.I think it would be better if all of these were present in tests (the right answer is obviously 2 for K > 1, badly optimized solutions will return 3 on one or more of these tests): s.# #.s d.. ..d ..d d.. #.s s.# s. .s d# #d .. .. .. .. #d d# .s s.For those interested there are more details.32651366 is my example of a wrong optimization. Changing break to continue on the following line will pass the #31 test: if (cost != INFTIME) break;(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.)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ |   0 how u solved F ? roll_no_1
•  » » » » 3 years ago, # ^ |   0 I understood it from the editorial and coded it. It requires the knowledge of MO's algorithm which you can read about here.
 » 4 years ago, # |   0 Since problem B was tagged with DP, does anyone have a DP solution for it? Please share your approach if you do. Thanks in advance.
 » 4 years ago, # | ← Rev. 2 →   0 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://codeforces.com/contest/877/submission/33872973
 » 4 years ago, # |   0 Can someone explain how to solve F using flows?
 » 4 years ago, # |   0 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
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   0 Tank from cell n - 1 can move into cell n, so it won't be destroyed
•  » » » 4 years ago, # ^ |   0 Did not read the question correctly(dumb me). Thanks for the reply.
 » 3 years ago, # |   0 I tried solving Problem B with DP. However, I keep getting TC 18 wrong.Their Output: 3014My Output: 3015Could someone please explain where my code went wrong? My implementation is attached here.Thanks for the help in advance.
 » 2 years ago, # |   0 877C-Slava and tanks should have a difficulty rating of less than 1600.Also,thanks for such a cute problem.
•  » » 21 month(s) ago, # ^ |   0 Can you explain how you did it?
 » 20 months ago, # | ← Rev. 2 →   0 in problem C why the answer won't be n+1.. for example n = 3. If I first bomb the nth cell then the tank will move into the (n-1)th cell then I will bomb the 1st cell then this tank also will move into the 2nd cell. so in the 2nd cell we have 2 damaged tank and 1 undamaged tank. now if i bomb the 2nd cell then 2 damaged tank should be destroyed and 1 tank is damaged which will move into the 3rd cell. now i have to bomb the 3rd cell to destroy the last tank. so for n = 3. output should be: 4, 3 1 2 3but in this case it gives wrong answer and says in 2nd cell all tanks are not destroyed
 » 20 months ago, # | ← Rev. 2 →   0 .
 » 17 months ago, # | ← Rev. 2 →   0 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
 » 3 months ago, # |   0 Why my code get WRONG_ANSWER in test point 31? #include using namespace std; char room[1005][1005]; int vis[1005][1005]; queue q; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int main() { memset(vis, -1, sizeof(vis)); int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) while (((room[i][j] = getchar()) == '\n') || (room[i][j] == ' ')); int sx, sy, tx, ty; scanf("%d%d%d%d", &sx, &sy, &tx, &ty); q.push(sx); q.push(sy); vis[sx][sy] = 0; while (!q.empty()) { int x = q.front(); q.pop(); int y = q.front(); q.pop(); if (x == tx && y == ty) { printf("%d", vis[x][y]); return 0; } for (int i = 0; i < 4; i++) { for (int j = 1; j <= k; j++) { int nx = x + dx[i] * j, ny = y + dy[i] * j; if (1 > nx || nx > n || 1 > ny || ny > m) break; if (room[nx][ny] == '#') break; if (vis[nx][ny] != -1) break; q.push(nx); q.push(ny); vis[nx][ny] = vis[x][y] + 1; } } } printf("-1"); return 0; }