What is the solution of KCHAR from LOCJUN17 ?

I have been looking at various solutions for this problem but couldn’t understand any of them.

So could anybody explain their approach to solving this problem?

There was a question which demanded the same. link to question. if you are not able to figure it out after reading the answers feel free to ask.(always please check if there is any relevant question before posting yours)

it is a very good question which requires just a little bit of observation…
you can see that each char at position 2^i is a so if you have to give query which is in the form of power of two simply print a.
lets define max as power of two just equal or less than desired position.
Now what happen if the number is not of type of power of two then there are two possibilities:-

  1. number is left to max or,
  2. number is right to max.
    if number is left to max ,just reduce the max to half and see in remaining half .
    but if the number is in the right then there u need to observe…
    observations:-
  3. the right half of pattern is reverse of left half .
  4. the right half is opposite of left half(i.e c = b,and c = a)
    use of observation:-
  5. if char is x distance from the mid than it will be same char as mid-x distance in left part (here do not consider flipping of character) means if it mid+xth char in right part than it will be xth char from begining in left part thus instead of searching for mid+xth ,search for xth char in left part
  6. since right part is just flipped version of left thus if we are currently getting a at that pos ,we will get c at new position in left part so reverse the char u find in left part.

i have written a simple two line fuction ,u can refer here
MY_ Solution

@deepcpp
My code-

 int getans(ll k, ll pow) {

 if(k==1)return 1;

 if (k == (1 << (pow - 1))) return 1;

 if (k < (1 << (pow - 1))) return getans(k, pow - 1);

 else return -getans((1 << pow) - k, pow - 1);

 }

This function will return 1 if the answer is a ans, will return −1 if the answer is c. I am just back doing the problem statement. You should call getans(k,63). complexity O(logN)

Explanation-

My function $getans(K,pow)$represents K^{th} character in S_{pow}.
there may arise some cases when we call getans(K,pow):-

if K==1 the answer is 1,(i.e. 1st position will always have charcter ‘a’)

also S_{pow} will have length 2^{pow}-1.

S_{pow} will have same characters as S_{pow-1} for first 2^{pow-1}-1 characters.(as S_{pow} = S_{pow-1} +a+ rev1(rev2(S_{pow-1})) )

so if(K<2^{pow-1})(i.e. K is before middle position) i call getans(K,pow-1);

also S_{pow} will have “a” at $2^{pow-1}$th character.(as 2^{pow-1} is the middle position)

that’s why i return 1, when K==2^{pow-1}

also when i call getans(K,pow) and K>2^{pow-1}(i.e. K is after middle position) then we can relate some how K with S_{pow-1}.

we have to find out which position of S_{pow-1} will relate with K, if we reverse S_{pow-1} and add with itself with letter ‘a’ in between. clearly K will be related to 2^{pow}-K (i.e. distance from last =distance from first) (i.e. total length+1 - current Position)

(for ex "123404321" in this 1234 is reverse and added with itself with a 0 in between, so 2nd 3's position can be related to 1st 3's position as 1st 3's position = total length+1- 2nd 3's position.
here in our example 1st 3's position is 3, 2nd 3's position is 7, total length is 10)

so when k>2^{pow-1} i call -getans(2^{pow}-K,pow-1)
(-ve sign is added as all ‘a’ are reversed to ‘c’ and vice-versa)

done…

Could you please give a proof to your solution? I am unable to prove that your method gives the correct solution. Thanks! :slight_smile:

added bro…