[Community Puzzle] 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. :stuck_out_tongue:

The harder tests were removed during validation to give every language a chance :slightly_smiling_face:
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 :stuck_out_tongue:).

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.