MMAX - Editorial

Thanks:grinning::grinning:

if we take k in form of string then its length will be equal to 10^100000 only .plz explain

It is given that k is upto 10^100000. So if we take k as a string then the length of that string is upto 10^5 which we can easily traverse within time limit.

I’m not understanding the logic of starting with 0 or 1 by looking to cnt1 cnt0…

Why space complexity is not O(1)?

Don’t mind about the sequence starting with 0 or 1.
It can be understood as the number of distinct pairs possible when there is a sequence of numbers arranged alternatively. Let the number of n’s in the sequence be x and the number of n+1’s be y.
If x==y : Number of pairs = (2 * x) - 1 = (2 * y) - 1
else : Number of pairs = 2 * min(x,y)

Why is time complexity of this algorithm log10(k) ?

@im_skp
log10(k) will be basically number of digits in K .
So if you take input of K as string Time and Space complexity will be order of length of K.

@mayank1601
for _ in range(int(input())):
n = int(input())
k = int(input())

cnt1 = k%n
cnt0 = n-cnt1

if(cnt1 < cnt0):
    print(2*cnt1)

elif(cnt0 < cnt1):
    print(2*cnt0)

else:
    print((2*cnt1)-1)

This is my solution which i coded up after seeing the editorial.
I mean this code is doing mod calculation,subtraction and comparison in constant amount of time.The only loop that is being used in my code is the loop for the no. of test cases.So,its time complexity should be O(T) where T represents the no. of test cases.And about space complexity,we aren’t making any new data structure.Therefore its space complexity should be O(1).

@im_skp
You are using python
In python you can take large values as input but that doesn’t mean that the space or time complexity will reduce .
Since k is large the space complexity to store k is still length of k
also mod operation for large k will take time and will not be a O(1) operation.

actually when we take any value at a particular index of a string(here k[i]),then it doesn’t gives us a integer value coz string a formed by a combination of character,so for converting it to integer we substract ascii code from it…

why im getting WA in first task
https://www.codechef.com/viewsolution/33408482