Блог пользователя OmaeWaMouShenDeiru

Автор OmaeWaMouShenDeiru, история, 9 лет назад, По-английски

Hey,

For problem: Lauren And Inversions

My code pass all but two huge cases.

What is wrong with my approach ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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