OmaeWaMouShenDeiru's blog

WolrdCup HackerRank semi Finals round, problem: Lauren And Inversions

By OmaeWaMouShenDeiru, history, 9 years ago, In English

Hey,

For problem: Lauren And Inversions

My code pass all but two huge cases.

What is wrong with my approach ?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's interesting that your code passes all but two cases, since it's actually very wrong. We can feed it the following testcase:

7
3 2 1 7 4 5 6

The answer will be 4 5 (ideone), i.e. your suggestion is to swap the 4 and the 7, which will reduce the number of inversions by one. However, note that swapping the 1 and the 3 will actually reduce the number of inversions by three.

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

    I didn't thougt it would pass either, is there a correct solution thats uses binary indexed tree ?

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

And this is why partial scoring like HackerRank does it is BS. How did this incorrect greedy get so many points?

4 1 2 3 7 6 5

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

    What's the idea of incorrect greedy solution?

    → Reply