You should definitely check out — https://vjudge.net

https://img.atcoder.jp/jsc2019-qual/editorial.pdf

editorials are already up, check out there

since number of intervals that we will invert it is $$$N$$$ and all intervals must be different

so we know every cell will be starting cell of interval or ending cell of interval let's make the value of all cells that have white color $$$0$$$ and black color $$$1$$$. so for every cell number of intervals that cell is inside it $$$mod 2$$$ must equal to its value so it will be white.

first we will solve it when order doesn't matter : we will loop on every cell and have variable that denotes the number of intervals that started and didn't end and denote it as $$$cnt$$$ so if ($$$cnt$$$ + $$$arr[i]$$$) $$$mod$$$ $$$2$$$ $$$!=$$$ $$$0$$$ then we need to start new interval to make this cell white else we will close interval, to find number of ways to make all cells white in every time that we will close interval we will make $$$ways * (opened intervals)$$$ and $$$ways$$$ will represent number of ways if order doesn't matter.

since order matters then ans will be equal to $$$ways * N!$$$. and in cases like if the first cell is white or number of opened intervals $$$ \lt 0$$$ or number of opened intervals $$$ \gt n$$$ or after ending of loop number of opened intervals $$$ \gt 0$$$ then their answer will be $$$0$$$.

my submission

But there wasn't much typing required. Way more thinking than typing, at least.

After the contest I spent at least an hour wondering why my brutetester wasn't finding any bugs before realizing the same thing :/

changing the order of operations does not affect the result because what matters is the number of times we flip the color of a square(in fact just the parity of number of flips). Assume the i index is flipped even number of times then the color remains preserved. Example: S="BWWB". We flip in order (1,3) and then (2,4) the index 2 is flipped twice. Even if we change the order of operation i.e (2,4) and then (1,3) we flip index 2 twice. When we flip a color even number of times, we get the same color back irrespective of the order of operations. Similar argument for odd flips. The color is inverted irrespective of order of operations.

Sorry but I don't understand how this works, can you elaborate? (I got solution similar to editorial I think).

lol. atcoder does same most of time. but this time they went back too much.. 1983 haha..

btw how do u find the hidden treasure

For each element, we have two types of inversions,

1) Inversions among it's own sequence

2) Inversions among other sequences that are concatenated.

For type 1), we just calculate in given sequence, in $$$O(n^2)$$$.

For type 2), in given sequence of $$$N$$$ elements, you need to find for each element how many elements are smaller (or larger) than it ( strictly ).

So if there are $$$x$$$ numbers smaller than some element, then in first copy of the sequence the other $$$(k-1)$$$ copies on the right will each have those x numbers. So we add $$$(k-1)*x$$$ inversions, then for the second copy of the sequence, we have $$$(k-2)$$$ copies on the right. So, this way, you will add $$$x$$$, $$$(k-1) + (k-2) + (k-3) + ... + (1) + (0)$$$ times.

[ $$$0$$$ is for the last copy that you concatenate ].

And $$$\sum_{i=1}^{k-1}i$$$ = $$$\frac{k*(k-1)}{2}$$$

We need the length of any cycle to be even, not the number of times each edge is used. I had to read the note at the end to understand this part:

"For example, if we leave Room 2 , traverse the path 2 → 3 → 2 → 3 → 2 → 1 → 2 while only passing passages of level 1 and get back to Room 2 , we pass through a passage six times."

Finding the LSAB of XOR directly translates to finding the maximum number of bits from the right which are the same. Basically, an edge in level i connects two nodes with labels such that the least significant i-1 bits are the same but the least significant ith bit is different.

Now think about travelling edges only in level i. This means everytime you travel an edge in level i, the ith bit will keep on changing. This will never contain any odd cycles as if there were odd cycles, the first and the last element of the cycle will not be the same, which is a contradiction. Edges of level i form a bipartite graph, which is what is required.