@taran_1407, I followed your approach while also using the break after swapping the two positions and it got Accepted.
How can taran help you here? 
1 Like
Well @vijju123, i know this would apper suprising to u, but incidently i can :D.
@akshaycs, firstly i would like to congratulate u for getting 100 points without writing actual solution.
After that, the reason your solution worked was weaker test cases for this problem.
Lastly, i would recommend u to solve this question using sqrt decomposition for your practice.
Alright??
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?
When I read the ans, my interpretation was “Brute force got AC, do something about it!” (and hence my confusion :p)
That TC had all small cases. A TLE in it means your code is going either into undefined behavior, or an infinite loop. Look for common errors which cause runtime error to debug easily, array index out of bound etc. are my first bet.
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
Whenver Ai == Bi, i try to replace it witn any suitable position j, such that Ai != Bj and Aj != Bi, this way, when i swapBi and Bj, Ai != Bi and Aj != Bj, thus reducing hamming distance.
After that, only those positions have Ai ==Bi, for which it is not possible to reduce hamming distance by swap with any other element.
Aftet that, i calculate hamming distance of final array and print answer.
Thanks @taran_1407 for replying. I will try to implement it and let you know if it fails. Apart from that do you have a better approach?
Thanks for the help, as I am just beginning with competitive coding!
Simply u could create a frequency map of elements of array A. Put it in a double ended queue(which stores the element and its frequency).Now traverse the array A,compare A[i] with first element of deque,if (they are not equal then decrease its frequency and print it,if frequency becomes 0 pop it),else if(they are equal do the same procedure for last element of deque)
Well @kushan02, If you wanna have a look at better approach, See my solution for its simplicity, (Everyone tends to like their own solution) or refer many solutions from above comments.
Following is my most favorite solution:
Randomized solution: https://www.codechef.com/viewsolution/16511540
Great explanation! Thanks
Glad to hear that…