Livace's blog

Codeforces Round #442 (Div. 2). Editorial.
By Livace, history, 7 years ago, translation, In English

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
  • Vote: I like it
  • +75
  • Vote: I do not like it

Comments Comments (135)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

What is test 49 in D(it is long hence not visible)? NOTE: Ignore got it.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you have figured it out can you tell me the case?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it 
      1000 1000 1000
......(....).....#
......(....)......
......(....)......
......(....)......
......(....)......
1 1 1000 1000

      Not sure, but after finding the way to pass this test i got AC.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

How is BFS too slow for D? 31650245 is BFS, but it doesn't time out.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Nice, the essential part in this submission is to stop when !(dist[i][y]>=dist[x][y]+1)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, I got mine to pass when I added that, but I don't understand why that works. Could you give a little explanation?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

My solution for D (O(n*m)):

http://codeforces.net/contest/877/submission/31659168

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain a little !

    it will be helpful for beginners:)

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any specific reason for deque? I guess the logic works fine without that as well ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution for D (O(n*m*k) ) =).

    http://codeforces.net/contest/877/submission/38798575

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If someone would be kind enough to tell me what went wrong with my E submission (http://codeforces.net/contest/877/submission/31648193). Thanks

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it -35 Vote: I do not like it

    Man, you should have known that java is bit slower than c++. I think usage of inappropriate language is only your problem.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Arrays.sort() can work up to O(n2)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      NO

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I got the problem. There was a bug in the implementation of the comparable function. Thanks!

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      Well, your sorting is just incorrect for Mo's algorithm. It should sort by block, but it sorts by l.

      → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Problem D

Test case 31?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    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 :)

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it 
    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain why do we need to save direction, too?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              here's my submission: 36150483

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                ← Rev. 3   Vote: I like it +1 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  Wow, thank you so much, I struggled with this problem for a long time!

                  → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks Temirulan and -osdajigu-. Got AC

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any implementation as mentioned in Editorial..... Thanks.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have any idea why this- http://codeforces.net/contest/877/submission/31647784 gave WA on test 49?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Why didn't it give TLE?? My implementation is almost same but i get TLE on test 48.

    http://codeforces.net/contest/877/submission/31654408 If you can point out the mistake that would be really helpful

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

LOL, For 5 seconds I was waiting to load the tutorial of problem C. :P

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Proof of optimality for Problem C ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain, how did you reduced the given problem to equivalent string problem?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone provide the recurrence formula for B with DP?

Never mind, figured it out!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you provide the formula? Brute force soln in tutorial is n^2 and gets Timed out.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Still, even without the multiplier, the python code should be roughly 5x slower. And it should easily pass O(n^2) for n=5000

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Actually no. python is roughly 100 times slower.

            → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      DP Solution O(N): I hope this is quite clear! 31663633 Simple Bruteforce O(N^2): 31642282

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if the tank is in the cell 2 and moves to cell 3?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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

        → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have the same doubt, for 4 cells shouldn't the optimal placement of bombs be, 2 4 3 1 2 ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When you hit cell 3, the tank inside it might move to cell 4 and not get hit after that.

      → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can someone please provide the code for D

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I wrote fenwick accidentally, I haven't a solution with fenwick for this problem. Sorry again.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it
My idea for D

UPDATE: My mistake. Seems like I didn't read the problem statement carefully enough.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you make sure you won't move more than k steps in one direction?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5 ≠ n

    tank can move from 5 to 6

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why? it's said in the problem statement that tanks on position n can be moved only to position n — 1.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nmax = 5000, so some languages could be not fast enough for solving this problem.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's a pretty famous problem. click

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, this lazy propagation is kinda straightforward :)

    Check mine: 31644977

    Coded it in 18 mins.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

BFS is enough for D number. http://codeforces.net/contest/877/submission/31656756

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give some explanation why it works?

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BFS nice, but can someone prove that it's enough?

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why i keep getting memory limit exceeded on problem D? is it because too many queue?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any implementation of problem D as mentioned in Editorial. Thanks...!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my code giving RE for test 5 in [problem:D].

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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 .

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered_map has a big overhead. Quite often it will even be slower than map, even though the complexity is better.

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why did my solution get TLE http://codeforces.net/contest/877/submission/31697709 for F? \n used unordered_map

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E,Can someone guide me on how to form segment tree from given tree ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use the dfs order where a subtree will be in a continuous range.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate your idea a bit more pls?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It could be because of duplicate elements in your std::queue.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can solve F by using Mo's algorithm if we discretize the numbers first..

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/877/submission/31757764

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my thought on the problem div2E (div1C): http://robezhang.blogspot.com/2017/10/segment-tree-with-lazy-propagation.html

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

s.#  
..d

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

For those interested

there are more details.
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how u solved F ? roll_no_1

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understood it from the editorial and coded it. It requires the knowledge of MO's algorithm which you can read about here.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.net/contest/877/submission/33872973

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve F using flows?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tank from cell n - 1 can move into cell n, so it won't be destroyed

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

About Problem D:

My submission 234897503 is Accepted but I was wrong in this test:

3 5 1000
....#
.##.#
.....
1 1 3 5

The correct answer is 2 but my output is 3. Can you add this test to this problem

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

  1. 0-edge weight // If I moved in the same direction from {x1,y1,di} to {ni,nj,j} (iska matlb -> {x1,y1} jis direction se reach hua tha I have moved in same dirn so 0-edge case (ofc, dist<k))

  2. 1-edge weight case (I have moved in the different direction in which previous node was visited)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the code for editorial of B http://codeforces.net/contest/877/submission/285117793

→ Reply