AvadaKedavara's blog

O(N log N) solution not working for this problem.
By AvadaKedavara, history, 12 months ago, In English

In the problem Swaps [problem:https://mirror.codeforces.com/problemset/problem/1573/B], my solution which is of O(n log n) time complexity is not working and giving a tle on test 2, when clearly the problem allows O(n log n) to pass. My solution: [submission:https://mirror.codeforces.com/contest/1573/submission/240104987]. Can somebody explain why this is happening. I know that there is a better solution in the editorial but why should this not pass?

Update: Fixed the problem :>

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

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Each test case you create an array pos of size 1e6, so your solution works in ~ 1e6 * T, which is quite a lot.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There's also the fact that your solution seems to be wrong?

4
1 5 7 3
4 8 2 6
  • Correct answer: 0
  • Your answer: 1
→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AvadaKedavara (previous revision, new revision, compare).

→ Reply