What’s wrong in my code…can anybody help me out, plz…
Here is my
[1]
[1]: https://www.codechef.com/viewsolution/16560604
Thanks...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.
For CHEFHAM, I tried a different approach, I broke the array in subarrays of length two, now there can be two cases:
- Both the elements in a subarray are different, then just swap the elements
- If both the elements in a subarray are same, swap the position of this subarray with the nearby subarray.
Take care of the last element left for odd n.
Here is the link to my solution :
[1]
[1]: https://www.codechef.com/viewsolution/16516552
1 Like
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.
@taran_1407 thanks for the editorial. For the problem CHEFHAM, shouldn’t there a break after swapping the two positions in your code?
@taran_1407 I got a solution of CHEFEXQ got AC in brute force approach using numpy python library, how can it possible solution, plss help me!
I tried to do CHEFEXQ with BIT(fenwick tree) got 50 points can anyone suggest how can the query part be optimized to suit the problem.
here is the code.
This is my solution for CPLAY. https://www.codechef.com/viewsolution/16567845 Can someone check and tell me why its giving Wrong Answer?
I made a observation for the chefham problem that if the array length is greater than 3 than there always and always should exist a array with hamming distance equal to the length of the array. I could not implement a solution for the same, I have now a thought about directly outputting a sorted array using check that the position does not match with the original array, if it does then it goes to a different array and this continues till there is no element left to output.
Any suggestions and is my observation regarding the hamming distance correct? Thanks
Yeah, u are right about the part that if N>3, max possible hamming distance = N.
Ur approach, though sounds easier, can be met with a tricky case i guess (cant say surely, as i have not seen ur solution).
I too used a similar idea initially.
My approach
First, create total 3 copies of given array. One original, one sorted in ascending order and one ordered in descending order.
Compare original array with both sorted arrays, and compare hamming distance in both cases. Run above program on array with greater hamming distance.
Friend, i would be able to help u if u explain the idea of ur solution. I havent worked woth fenwick trees…
No, there should not be any break in CHEFHAM solutio.