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.
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…
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
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.