https://www.codingame.com/training/medium/inversion-count
Send your feedback or ask for help here!
Created by @Djoums,validated by @TBali,@Kobz and @Velcoro.
If you have any issues, feel free to ping them.
1 Like
Maybe my code is just bad and there’s a much better way to do this, but I had to toggle optimizations with a pragma to solve this with C++ and the level 8 still took 200ms. I feel sorry for anyone solving this in a language that doesn’t provide C++ levels of performance, because they’ll definitely have to use a better algorithm than I did. 
The harder tests were removed during validation to give every language a chance 
As long as your algorithm can do better than O(N²) it should be ok.
You sure they were removed?? I’m at O(n log n) with no luck on 8 still. Using java…
My C# solution is also in O(N logN) and passes test 8 in ~150ms, that should leave some breathing room.
Also @TBali solved the puzzle in PHP, which is slower than Java by a fair amount (especially given their crappy array system ).
I noticed that Validator 1 is the only place where the values in input are repeated.
I do not know if repeated values was intended, but this limits the number of ways one can solve the puzzle.
My suggestion is to change Validator 1 and add a uniqueness constraint in the statement.
1 Like
It wasn’t intentional, I probably messed up the LCG parameters.
I corrected it and added the uniqueness to the description, thanks for reporting it.
2 Likes