atlasworld's blog

problem 12 D

By atlasworld, history, 6 years ago, In English

anyone who solved this problem http://codeforces.net/problemset/problem/12/D , can please share his ideas.

i have read this blog http://codeforces.net/blog/entry/44775#comment-437643 , the explanation which is written by

@satyaki3794 , how will it fit in time limit ?

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

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Before I explain his approach, are you familiar with segment trees ?

And the problem of how to count number of inversions with a segment tree ?

If you are familiar with that, then I will build on it to explain.

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

    @ghoshsai5000 i think , i have to learn about Binary index tree ...

    i dont know about it .. most accepted submissions are based on BIT ..

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

      Segment trees and Fenwick trees are equivalent. Fenwick trees are faster because they need less memory and less code to implement. But, segment trees are conceptually easier.

      In this particular problem, you can use either, I think . I'll just try with segment trees and get back to you with an explanation.

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

        Thanks...

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

          Here's the main idea —

          Sort the ladies by their beauty.

          Rank all the intellects. Let the rank of each intellect i, be R[i].

          Now, we will go through the ladies in descending order of beauties.

          Find the 'ranks' of all the intellects of each lady.

          Maintain an array where the index is the intellect rank, and the value is the richness. Insert the richness into this array, one by one, and maintain a maximum segment tree over this array.

          1. Check if, the maximum richness in all intellects with ranks, [R[i] + 1, N], is greater than richness of current lady. If yes, then it means, there is some lady with greater beauty, (Because she's already processed), greater intellect (Because we are only querying intellects from R[i] + 1 to N) and greater richness (By comparison with this lady's richness.)

          2. After this, insert richness of current lady, at position R[i] in the segment tree.

          I shall convert this to code shortly. Please wait.

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

I don't think it's a good idea to ask questions from a contest while the contest is going on, even if it's on some other site. Ignore my comment if your post has nothing to do with atcoder beginning contest 100.

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

    there was no official tutorial for CF round 12 .

    so i was left with only this way to ask my doubt..

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

I have written an editorial for this problem here.

I learnt quite a lot in solving this problem. I hope you find my post helpful :)

→ Reply