# Unofficial editorials December Long challengr Part 2

Hello Guys, I’m back once again with editorials, hoping you would like them.

This is the part 2 of three posts of Unofficial editorials for December Long Challenge.

For editorials of problems GIT01, CPLAY, and VK18, click here.

For editorials of problem REDBLUE, click here.

This post has editorials for problems CHEFHAM and CHEFEXQ.

### Problem Difficulty : Easy-medium

#### Problem Explanation

Given an array, rearrange it in order to maximize the hamming distance between original array and the rearranged array. Hamming distance is defined as the number of indices i for which A[i] != B[i].

Important thing to note: Maximum frequency of a value is 2.

#### Solution

Well, I’m gonna share the most basic solution that comes in your mind naturally, with O(n^2) time Complexity.

Loop for every position and run a nested loop swapping elements if elements at both positions can be swapped or not.

Two elements at positions i and j can be swapped if A[i] != B[j] && A[j] != B[i]. (B array is another array with same elements in same order). (Swaps should be made only in B array)

After that, calculate hamming distance using a single loop and print the Hamming distance and the B array.

Simple, right. Well, this is my solution, except one observation.

Observation: Above solution will easily fit the time limit. (My solution ran within 0.47 seconds out of 6 second time limit.)

We run the internal loop only at that position i for which A[i] == B[j].

As we know that the maximum frequency of any element is 2, there can be at most 3 iterations (one for each position i and j, and last one is successful one) in the inner loop, making the solution complexity O(3*N), that is same as O(N).

That’s all.

Here’s a link to my

``````
[4].

### Problem [CHEFEXQ][5]
#
### Problem difficulty: Medium
#

### Prerequisites: Square Root Decomposition

#
#### Problem Explanation

Given an array with N elements, you have two perform two type of queries:

1. Update ith value to x
2. Count Number of magical sub-arrays ending before i whose prefix xor is k.

Magical sub-array is defined as sub-array starting with index 0 of original array. (0 based indexing in my solution).

#### Solution

**Naive Solution**:

For every update query, update A[i] to x and for every query of second type, run a loop from 0 to i, taking prefix xor. whenever prefix xor == k, increment count by 1 and then print count.

Time complexity of update is O(1) and count operation is O(N), making overall complexity O(N*Q), which will give TLE.

Surprisingly, this solution gave 50 points instead of 20 points as above solution would give TLE for N and Q upto 1e4, probably weak test cases for those test files.

Anyways, we now are aiming for 100 points and that's where square root decomposition comes into action.

**Square root decomposition, or the buckets method**, means to divide the given range into blocks of any size (usually of sqrt(N) size), pre-compute answers for every block as a whole, and combine results of different blocks to answer count queries of given range. In case of query having partial start and end block, we will compute answer using naive method till start of next block and also from end of last complete block in range to r. Time complexity per count => Q(sqrt(N)) (Assuming we have sqrt(N) blocks).

For update operation, We just need to update one block, which can be done in O(sqrt(N)) time, assuming block size is sqrt(N).

Well, this was general overview of square root decomposition technique. Now, we need to decide what to store in each block such that we can answer queries for whole block in O(1).

I creates an array xor, which holds the xor of all values present in each block, and a map
(unordered in c++/HashMap in java) for every block, holding the the key value pairs where key is the prefix xor of block up-to any position and value is the frequency of key being the prefix xor of block.

Take example of one block of an array 1 3 5 4 1

prefix xor would be 1 2 7 3 2

Now, map for this block will contain following four key => value pairs:

1. 1 => 1
2. 2 => 2
3. 3 => 1
4. 7 => 1

Coming to update operation, for each update, we will rebuild whole map again the same way we initially built above, and also update xor[b] with new block xor, where b is block index.

Query operation is simple.

prev = 0 and count = 0

if i is the given index and k is given value, then for every block ending before i,

if map[b] contains key prev^k, count += map[b].get(prev^k)

prev = prev^xor[b].

For remaining portion of count operation, use the simple solution mentioned above.

The variable prev is holding the prefix xor for first b-1 blocks. Querying for prev^k works for following reason.

**Reason:** we need to find number of positions for which **prefix xor of whole array** == k. But every block stores prefix xor of their own block only. We know that if xor(i, j) denote prefix xor of range i to j, then xor(i, j) = xor(i, k) ^ xor(k+1, j) holds true.

xor(i, j) = xor(i, k) ^ xor(k+1, j)

If k = index of last element of last completed block i-1, Then prev = xor(0,k) for ith block.

We need the prefix xor to be k and we have prefix xor up-to last position is prev, So entry in map of ith block, whose key is prev^k, will have prefix xor of whole array as (prev^k) ^ prev = k, which is what we want.

``````

6.

Just like editorial part 1, I again hope you enjoy my editorials as much as you all do like coffee in winters (though i don’t).

Enjoy coding.

11 Likes

Hi taran,

I have solved CHEFHAM using sorting. Make one copy of given array and sort it. Iterate the sorted and array put the element x at index having value ceiling(x) in original array. if ceiling(x) is null put it at the at the index having vacant space as well as lowest value.

my solution

I think my solution is the same as what chef_keshav is saying (in C++ though). I believe I had nlogn complexity and my solution ran in 0.33 seconds.

here

https://www.codechef.com/viewsolution/16551760

How even in the world can this solution pass all the test cases? Or am in not seeing something?

CHEFEXQ problem had weak test cases, a lot of O(NQ) solutions managed to pass all test cases and get AC which is really disappointing.

Is there no other method of solving CHEFEXQ problem? If there is can somebody please explain it to me. Thank You

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

@taran_1407 I attempted the problem CHEFEXQ as you explained above

My Code:- Link to my code

Where am I getting it wrong? Please have a look at my code.

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

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.

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.

CHEFHAM can be solved in so many ways . The test cases were weak enough for hit and trial for obtaining the solutuion .
CHEFEXQ scoring was bit weird too . The most basic brute force solution of CHEFEXQ was able to fetch 50 points. THere was no need for three different scoring brackets .

Anyways thanks for the editorials . Keep up the good work Taran

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.

Thanks for the editorial.
Can we do CHEFEXQ with segment trees in any way?

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

Hey @taran_1407, used same method for CHEFEXQ but getting TLE. Doing Square_Root_Decomposition, storing frequencies in unordered_map, used lazy technique for update task, still getting TLE.

Here is MY CODE .