Unofficial editorials December Long challengr Part 2

@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

Hello, my approach was to divide the array into two sub parts where the first part contained elements with frequency 2 and the second part contained elements with frequency 1. Then checked if the 1st element of the new array is same as the jth element of the given array, if yes then increment j by 1, if no then pop that element, print and continue.

But I got TLE for the 1st test of the Subtask 3 only while 2nd one executes perfectly. Can anyone please help me why my solution’s getting TLE?

Code: https://www.codechef.com/viewsolution/16487066

Your solution to Problem CHEFHAM is great.
However, could you give me some hints why the solution guarantee to find the maximal Hamming distance?
Thanks

Great explanation! Thanks

And that too using Scanner for reading input? I can’t believe this. :frowning:

Nice way, Although i like getting an AC with an O(N^2) algorithm. :smiley:

Unbelievable, I too ran first solution brute force, which gave only 50 points.

Well, i guess this one is the simplest one. Because Segment tree, popular choice for such range query problems, didn’t work, atleast for me. If you solve it in a different way, feel free to share. :slight_smile:

Your calculation for e is wrong.As its not necessaray that N will be a perfect square.So just check if e<=n.
Also if u get AC , share your code.Since i was getting tle with this approach in c++.

Or more simple write e=min(e,n)

Isn’t it taking too much time? My O(N^2) solution ran in 0.47 seconds (in java). Anyways, the solution which works is fine. :smiley:

I wrote same brute force in c++ all i could get is 50 pts why this one passed all -_-

Thanks @trashmaster.

There are many O(N), O(NlogN) solutions and Only one O(N^2) solution (mine :D) for solving CHEFHAM.

I too was entirely suprised to see 50 points for my first brute force solution. Some people even got 100 points using brute force.

Well, I too tired Segment trees, but i couldn’t get it right, getting TLE. I used prefix xor of input array as base for building segment tree and then for every update, U need to update (i, N-1) with x^A[i].

For query, just return frequency of K from 0 to i.

But This didn’t work, because of update part.

1 Like

I went into shock for some seconds on seeing the solution at first :stuck_out_tongue:

I don’t think seg tree solution is possible for this problem.