Unofficial editorials December Long challengr Part 2

The 20 marks i.e. subtask 1 was meant to pass if we take xor of every subarray starting from 1, i.e. (1-1, 1-2, 1-3, 1-4) by linear traversing, instead of using previous xor value.

Thats quite different… @eugalt

Mate, there’s no limit to efficieny. I have just checked and found that fastest c++ has runtime of 0.03 seconds…

Keep trying till u get the best runtime…

Wow… Something random it is…

Use 2d array instead of map.
Did the same mistake

tried but it also failed !

Well, sorry it ran in 0.16 seconds - I hadn’t used fast I/O methods. I’m a newbie around here, so I didn’t know about it at that point

Interesting, is there a way to break it? Actually for small N’s your program kind of goes over all permutations, for large N’s, it is very hard to construct a counterexample that can break it.

For maximum frequency = 2, i can guarantee that we can’t fault this solution, because of very high number of acceptable permutations of given array.

In case we are given maximum frequency X instead of 2, worst case for this solution would be

N = 2*x followed by N elements. N elements shall consist of i values being a, and remaining i being b.

Even in this case, probability of favourable permutations is (i!)^2/(2*i)!.

But this was the probability of getting correct answer in one iteration.

So we need to make N upto a limit, for which (MAX_ITER*(i!)^2)/(2*i)! Will be reasonably less, say below 0.5.

After finding a suitable N, Set T, then following test case T times.

N (as found above)

(a a a … i times) (b b b…i times)

I believe this test file will fail not only this, but any randomized algorithm.

ONLY IF WE MAXIMUM FREQUENCY WAS GIVEN X UPTO N/2.

Coreect me if i am wrong, as this is my first time developing a test case to hack a randomized solution.

thanks taran…

@vivek_1998299
https://www.codechef.com/viewsolution/16561389
TLE and WA !

Exactly what i did ^

Exact brute force aolution of this problem.

I am not getting the use os many variables in ur code, which makes the code complicates to find the bug.

So, i would suggest, make a buildBlock(blockno) function, which rebuild block. Whenever there’s an update, just change A[i] and call updateBlock(i/BlockSize). Dont complicate things.

For query, if i belong to first block, calculate answer using brute force, else set prwv = 0, run loop from j = 0 to j< i/blocksize, add map[j].get(prev^k) to count and set prev = prev^xor[j].

Run another loop from j = (i/blocksize)*blocksize to j<= i, prev = prev^A[j], if prev==k, count++. Print count.

Well, you must be tired to hear this again and agin, but practice ia the obly way :). You have to spend quality time with algorithms :slight_smile:

First thing, no need to maintain update array, we can calculate the prev value on the run. Calculating update also increase our work, with ni benefit.

Second thing, U too are complicating your solution, so i would recommend implementing it the way i mentioned in a comment above. Keep things simple, so that debugging is simple.

Friend, i haven’t solved this problem using segtree. I don’t even think there’s are solution using segment trees. The only other solution i know MIGHT be using trie, but i haven’t seen any such solution. Square root decomposition is the most easy one.

If you have any different solution, i would like to see.

No problem…

Friend, though your approach is correct and can work, There are much simpler approaches available.

In the second loop where (i+1) < n && a[i]!=b[i+1]

add one more condition a[i+1] != b[i]

Same for i-1.

Also, You can use the above O(N^2) solution i explained for N <= 4 and Your solution for N>4.

Keep coding.