dario-dsa's blog

Spoj Meteors
By dario-dsa, 10 years ago, In English

Hi, can anyone help with this task http://www.spoj.com/problems/METEORS/ . First i thought about binary search and segment tree with lazy propagation but that wouldn't work. Can anyone give me hole perspective to this problem? Thanks.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Solution for yet another Div2 A.

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

    If you want a number to become X

    Ok, but you want the sum of a group of numbers to become X.

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

      Wow! I thought I've seen this problem before, but it has been an easier one. I'm sorry :p

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

Is O(N * sqrt(N)) solution ok for you?

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

    Yes, but how did you get sqrt(N)?

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

      Of course there should be M somewhere, but since N ~ M I wrote it in that way.

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

        Ok, but how did you get sqrt?

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

          Let's divide our queries into O(sqrt(N)) groups. We can process all the queries from a single group in O(N) time. When we do it, we can check whether a particular group is filled now. If it does, then let's run all these updates from the last group and get the precise time when it got filled. We can do it point-by point, since every point will be affected by O(sqrt(N)) segments.

          This got accepted with two times margin on main, but got TLE on SPOJ :(

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

            Thanks very much. :-D

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

            Something got TLE on SPOJ? That is unbelievable :P! (I got TLEs for optimal complexities algorithms in 3 out of 5 problems I submitted on SPOJ :P)

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

              Their new cluster is ok, but those problems that are checked on the old one are sometimes hard to make them pass.

              Btw, it's pretty strange that there is 35 sec TL on some tests on main, while maximum TL on SPOJ is 15 sec.

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

                Got accepted on SPOJ O(N * sqrt(N))

                Code

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

Think about doing binary searches parallel.

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

That is a really great problem. In Poland parallel binary searching is abbreviated as "Meteors" since that task appeared on finals :P. I was really proud that I have solved it on a contest, but even though I got 70 pts — beware of long long overflow :D.

By the way, if you don't like SPOJ, here is that task on a much better site :P http://main.edu.pl/en/archive/oi/18/met

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

    Can you recommend some good editorial for parallel binary searching? It also would be great if you explain this technique on "Meteors" problem. Thanks in advance.

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

      In binary searching you need to be able to answer questions of form "Is answer greater than x?", so that in log n questions we can find answer. In that problem we need to find values a_1, ..., a_n and trick is that we can answer all of the questions of form "Is a_i greater than x_i?", where x_i are chosen by us, simulating all of the rains just once (pretty easy how to do this). So it suffices to do log n of simulations in order to find all answers.

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

Sorry to bring up this old thread, but has anyone got an AC using segment tree? here is my implementation of parallel binary search : http://ideone.com/7l4nSx which gets TLE on SPOJ

Edit : NVM, got AC with BIT.

→ Reply