Ahmed_Morsy's blog

japanese olympaids informatics
By Ahmed_Morsy, 10 years ago, In English

i took part in this contest and i wanted to see if anyone can give me a hand in this problem .

the link ->http://cms.ioi-jp.org/contest/tasks/fortune_telling2/description

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

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

I also participated in the competition and managed to solve the problem. Here is my idea in O(NlogN).

Let's assume that A<B in each card (if it isn't true we swap the values and remember that we swapped them). Now, notice that after a query T, in which T>=A, T<B then after that query, you are sure that the card is facing up with its B side. Simply, if it was on its A side, then it would get flipped as T>=A and if it was on its B side it wouldn't change since T<B. Knowing that, we need to find for each card the last query that was in the interval [A,B). This can be done in O(NlogN) by keeping a dynamic segment tree and for the i-th query with value T we update val[T]=i in the segment tree. The simply the last query in some interval can be found by a RMQ query in the tree.

Having that, now we need to find for each card, how many queries in the interval [B,inf) were done AFTER the time of the last query that was in its [A,B) interval. This can be achieved by O(NlogN) again, by sorting the cards by the last query that affected their [A,B) interval, and simply iterating them and adding the corresponding queries in another dynamic sum segment tree. Then the answer is yet again, the sum of interval [B,inf).

Knowing those values we can very easily find how is each card flipped in the end. For example, if at first the card had A<B, and there was some query in its [A,B) interval, and afterwards there were K queries in the interval [B,inf), then obviously, if K is even, the card is flipped with B side up, and otherwise (K is odd) the A side is up. It's easy to cover all cases once you've computed those values.

Sorry if I didn't explain it very well, feel free to ask questions. Some of my friends solved it in O(Nlog^2N) and it still passed the time limit. Good luck!

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

    thanks alot for your kindness :D i am afraid i didnot get it well can you please explain to me on an example ? thanks in advance

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

      Ok so let's have the following cards (A and B respectively)

      4 6

      8 8

      1 9

      And queries 2 8 9. Now the idea is to find for each card the last query that was in the interval formed A and B (including A, excluding B).

      For card 1, there is no such query.as there is no query of value 4 or 5.

      For card 2, there is no such query too, since there is no interval when A=B

      For card 3 the last query is the second, since the first and second are in the inteval (1 to 8) and the third isn't.

      Finding those values is done with dynamic rmq over all 10^9 possible values of T. So in this case the values we need to update are v[2]=1, v[8]=2, v[9]=3. For example for the third card, the answer is the biggest number in interval A~B-1 (i.e. 1 to 8).

      Now knowing those we sort by the value we just found, having the largest numbers before the smallest. We get the sequence of card 3,1,2. Now we keep another segment tree over 10^9 leaves. Each time we process a card, we add all queries that weren't prevously added and are larger than the value we found for this card. Then we calculate other values.for the cards. Let's see it as an example.

      First we process card 3. The last query that fits in its interval is the second. Since the third is not added, we add it. That means val[9]++ in our segment tree. Then the answer we are looking for, call it flips[] is simply a query from B to infinity (or max value, i.e. 10^9). So flips[3]=Sum(9,inf), and since only val[9] is 1, answer is 1. We get flips[3]=1.

      When processing card 1 we will add queries 1 and 2 since no queries fitted in its interval, therefore the last query to fit is said to be 0, i.e. val[8]++ and val[2]++. Then we get flips[1]=Sum(6,inf) = 2.

      Lastly processig card 2, we've already added all queries, so flips[2]=Sum(8,inf)=2

      Now let's see all the information we have. For the first card, it started at the smaller face and there were no queries in its interval. Therefore all flips of that card are equal to flips[1]=2. Therefore this card faced A at the end, i.e. 4.

      The second card also didn't have a query in its interval. It also had flips[2]=2, so it faced side A at the end, and that is 8.

      The third card again started while.facing the smaller number, but however did have queries in its interval, last of them — the second query. After the second query was done, we can be sure that this card was facing the bigger face, i.e. B. Now the flips that were done AFTER that query are saved in flips[3]=1. So after being at B e flip once and face A. Then the third card again show face A, i.e. 1.

      The total sum is 4+8+1=13.

      The answer is 13.

      Feel free to tell me if you still don't understand.

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

        After the last query,the card is always B.Am I right?

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

          Well yea, after the last query which has a value larger or equal to one face of the card and smaller than the other, the card will show its largeer value after the query. In my solution I swap A and B if A>B (and remember that, since the result may change), so yes, after SUCH query the card is always B :)

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

            What's your solution of the first problem?Also use the Heavy Light Decomposition?

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

              Sadly I couldn't solve it, however my teammate Hristo Venev had some really cool solution, though I'm unable to explain it since I don't fully understand it.

              → Reply