The bruteforce solution is O(n^4).

Does anyone know if this problem can be solved using invariants / permutation parity, with a better complexity?

Active In

International Olympiad in Informatics

Indian Computing Olympiad (ICO)

Competitive Programming

Artificial Intelligence

Featured Contributions

reply in this discussion

The bruteforce solution is O(n^4).

Does anyone know if this problem can be solved using invariants / permutation parity, with a better complexity?

Read more… (23 words)

reply in this discussion

Read more… (89 words)

reply in this discussion

Yeah, your solution seems a lot more intuitive, thanks for sharing. :)

Read more… (12 words)

reply in this discussion

I submitted Malvika's solution with the following changes and documented the results, they are as follows:

1.Unchanged:

C++: 0.00 sec, C: 0.024 sec

2. Changed all variables to Signed Integers:

C++: 0.00 sec, C: 0.024 sec

3. Changed all variables to Signed Long Long:

C++ 0.00 sec, C: 0.036 sec

4. Changed scanf/printf to cin/cout and variables of type signed int:

C++ 0.036 sec, C: compilation error

NOTE: All the tests were on the IARCS online judge, so the maximum N = 2*10^8

Read more… (83 words)

reply in this discussion

Check out this video, it explains multidimensional arrays, and arrays in general pretty well.

https://www.coursera.org/learn/data-structures/lecture/OsBSF/arrays

Read more… (15 words)

reply in this discussion

Keshav Sir, can you explain Malvika's solution, I get that it is using the Inclusion-Exclusion Principle, but it seems a lot more efficient than anything other solution I have seen.

Read more… (30 words)

reply in this discussion

reply in this discussion

Tanavya wow, dude I did not know you were in tenth grade. Pretty sweet......

Well I wasted about 1.5 hours on Fence trying to use a Union-Find data structure (I know totally stupid of me).

Then in the next 1.5 hours, I got Fence accepted and I got the first 2 subtasks for Training (with specific bruteforce for each of the subtasks). The third subtask would have been easy if I had a little more time :(

So overall 150 / 200 (which I'm pretty sure won't be sufficient this year to get to IOITC).

Curious to know how others performed.

Read more… (101 words)