loc june17 challenge

how to solve KCHAR question??

see my solution https://www.codechef.com/viewsolution/14397133

the character present at K th position (if it is not a power of 2) depends on the character present at
buffer-K%buffer here buffer is power of 2 which is close to K and lesser than it (in case when K is 13 buffer will be 8,when K is 5 then buffer is 4) so use the analogy to reduce to problem
remember if K is power of 2 then it is definitely ‘a’ i.e when K=1,2,4,8,16,32,64…
see my solution CodeChef: Practical coding for everyone

The string formed has a unique nature. The length of string S(n) is 2^(n)-1, and always the character at position 2^n is ‘a’.

Convert the value to its binary equivalent and traverse the binary value from right to left till you get your first one.

If the left of the first one (if exists) is one the answer will be ‘c’ else ‘a’
This will give you the answer in O(Log N).

My solution

1 Like

the length is always 2^n-1 . the best way will be .
whille(m %2==0)
m=m/2;
if(m%4==1)
print(a)
else
print©

carefully create the pattern , its the power of something, so its better to divide by 2 to eventually convert it into the first of the strings. :slight_smile:

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)

This can be done in O(1) by checking the bit to left of least significant one.If it is 1 then answer is ‘c’ else ‘a’.
Here it link to the solution

If you look at the sequence carefully, you’ll notice that the i’th character is the complement of the character at the nearest power of 2 minus the difference between i and the nearest power of 2 to the left. Similarly it goes on till the first character. Keep a count of the flips you are doing.
For eg: if k=5: aacaa, the fifth character is ‘a’ which is the flip of third character ‘c’. Similarly the third character ‘c’ is a flip of the first character ‘a’. In each iteration look on the left side of the nearest power of 2 and subtract the difference and flip.

from math import log
def fn(n,flip):

	loop=int(log(n,2))
	l1=(1<<loop+1)-n
	if l1==n:
		return flip
	if l1==1:
		return not flip

	return fn(l1,not flip)
	
a=['a','c']
for x in xrange(int(raw_input())):
	print a[fn(int(raw_input()),False)]

something different , innovative .

I was also going in the same direction but get stuck with a thought that if we go on finding recursively buffer-K%buffer (in case k is not a power of 2), will it exceed the time limit. That was silly not to continue with that method.Recursion was getting solved at exponential speed hence there was no chance of TLE. We were subtracting from buffer numbers of exponential order .Should have done it.:frowning:

Btw Thanks :slight_smile: