Can someone share their approach for problem EXPTPROD? I was literally scratching my head for 1.5 hours while staring at the pc, couldn’t think of any feasible approach.
1 Like
You’ll get stronger in the next contest. My question is how matrix multiplication can get through that problem. I think its O(n^3logk), so i give up.
1 Like
can someone elaborate what is the way to solve the problem BDGFT ?
Please anyone Explain the logic behind TWO VARIABLE problem 
its solvable in O(N*N*log(K)) afaik. Don’t know details.
2 Likes
What is logic behind Two Variables?? Please Describe Logic
1 Like
Lets say dp[k][n] denote number of ways to obtain modulo of n after k steps…
One can easily calculate dp[2*k][n] from dp[k][n]…
So just calculate dp[2^i][n]
3 Likes
is it necessary to use dp ?
Can someone explain BDGFT clearly please?
Yeah sure!
Let Len be the length of a random substring of the main string .
Hence the equation C0 = C1C1 becomes Len - C1= C1C1.
Now find the roots of this Quadratic Eqaution.
Hence C1 = (sqrt(4Len+1) -1)/2;
So Len Can take only such values for which 4Len +1 is a Perfect square.
Finding such values of len is easy, and takes O(1) Time (only 351 such numbers ) .
I stored it in Vector V.
Then Afterwards its pretty much BRute Force.
Compute on all Substrings of length Len. !
Hope u get it!
5 Likes
Can anyone see what’s wrong with my solution. [CodeChef: Practical coding for everyone] for Two Variables of divison-2.
Even providing some testcases would be helpful
I guess we can do it using binary exponentiation.we just have to calculate frequency of each element from 0 to n-1.we can do that in n^2 so the total complexity is n^2log(k).
for(i,0,n)for(j,0,n)
temp[(i*j)%n]+=(freq[i]*freq[j])%MOD
fr(i,0,n)freq[i]=temp[i]
1 Like
Can u please elaborate on the equation Len - C1 = C1C1,
Dude but isn’t k like 10^9 ? Can you elaborate a bit more on your approach.
C1 = Number of 1’s in the substring
C0 = Number of 0’s in the Substring
Len = Length of that substring
Hence Len = C0 + C1;
THerefore Len - C1 = C1 x C1
Thought of the same pattern! But, had no time to submit at the last 
I don’t understand why your solution gave WA.
Can someone please look into this?
1 Like
For the problem Two Variables, we first make an observation that if a certain number X is reachable in K steps, any number greater than X is reachable in K steps. (One way would be to perform K-1 steps similary and add the larger number in the last step).
So we initially precalc the highest values reachable in each step (start at 1, add X^2 to Y and then , take X to be ceil(sqrt(Y)), the lowest value which can be added subject to the constraints), while X <= 10^9 and store these in a vector.
Now for each of the test cases, let the Jth element be the largest element of this vector less than or equal to Xi , then obviously the maximum number of steps is J.
We can either search for this value using a function like upper_bound in c++ or just iterate over the entire vector since it has <100 elements for X<=1e9 which will run within the time limit.
2 Likes
Yeah That is why Precompute it na!
Oh, I got it, I was taken to the ditch by myself. 
2 Likes
I am sorry but i’m sort of lost here, can you explain how ?