alv-r-'s blog

By alv-r-, 10 years ago, In English

Hello, I'm trying to solve E — New Year Domino from last contest, following the tutorial #1.

The tutorial mentions that you can calculate R[i] "using a segment tree or using a stack". My first approach was to try using a stack to see how it could be done, but I'm getting TLE on test 12: Here's my code/submission: http://mirror.codeforces.com/contest/500/submission/9349751 Is there something wrong with the way I'm using the stack to do it?

I also tried to do it with a segment tree then, but I'm getting "WA on test 7" with this approach. Code: http://mirror.codeforces.com/contest/500/submission/9352369 (the segment tree code is from the book Competitive Programming — 3rd edition). It's essentialy the same approach as before, but using the segtree instead of a stack. Printing the contents of U and R for the small test cases is giving me the correct values, so I was unable to find the error. Can someone please help?

PS: in the code:

  • pos[i] and len[i] are the x-position and length of the i-th domino

  • R[i] is the maximum x position covered when you drop the i-th domino

  • U[i][j] has the 2^jth "uncovered" piece index when you drop domino i (the 2^jth piece to 'break the interval'), as described in the tutorial

  • S[i][j] has the value needed to cover from i to U[i][j].

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I just reviewed your code which uses a stack.
There's no problem with your stack implementation, it is with your build part for 2^j interval breakdown. See this Updated Code ,I just exchanged the position of for loop for (i,j)

P.S -> I prefer doing query with something like this Updated Query

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

    Wow, thanks a lot!

    I don't get why changing the loop make such a difference though (from TLE of 2s on test 12 to AC with 436ms :O).

    I mean, I can see why it's better, you break from a N loop instead of a log N loop. But it's still O(N logN) with N=2x10^5 (and TL = 2s). That should be ok, shouldn't it? Is there something I'm missing?

    The updated query is indeed neater!

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      Actually if the ith loop is written first and then the jth(logN one) then, Suppose if you are computing the value for i = 0, j = 2 and U[i][1] = 2 then for computing the value for U[0][2] you need the value for U[2][1] which is not computed until now.
      while exchanging both the loops it won't be a problem as all the values of U[i][1] is already computed for i in range(0,n-1).

      The updated query is picked up directly from the LCA tutorial of topcoder :)

»
10 years ago, # |
  Vote: I like it -10 Vote: I do not like it

give me — please