PS: @aryanc403 loves russia and their editorials XD
Just give him a problem and he will find a russian editorial for it 
1 Like
arent there O(n^2) substrings for a given string
basically in that ques. given u have to maximise the no. of moves
and in that u have to choose some values of ‘p’ to reach some value Xf so for maximum moves u can
easily choose p values from 1 and maintain variable sum which always stores the square of all the values. now lets assume u r on i th move but i^2 is less than sum so u cannot take this value(as mentioned in ques. condition ) for ex… u have taken 1,2,3,4 so yur sum is 30(1^2+2^2+3^2+4^2) but now u cannot take 5 as 5^2 is less than sum. so move further and now choose again next number so choose until u cannnot get sum>(Xf)^2 …
and for the above approach u can maintain array… in which consecutive sum is there except those values whose i^2<sum & and when any Xf query comes so u have to answer lower_bound of Xf^2
for more explanation u can refer to my code …
https://www.codechef.com/viewsolution/25394039
3 Likes
check your code for xf = 10^9;
It’s giving 44723 instead of 59;
You’re Welcome.
basically in that ques. given u have to maximise the no. of moves
and in that u have to choose some values of ‘p’ to reach some value Xf so for maximum moves u can
easily choose p values from 1 and maintain variable sum which always stores the square of all the values. now lets assume u r on i th move but i^2 i is less than sum so u cannot take this value(as mentioned in ques. condition ) for ex… u have taken 1,2,3,4 so yur sum is 30(1^2+2^2+3^2+4^2) but now u cannot take 5 as 5^2 is less than sum. so move further and now choose again next number so choose until u cannnot get sum>(Xf)^2 …
and for the above approach u can maintain array… in which consecutive sum is there except those values whose i^2<sum & and when any Xf query comes so u have to answer lower_bound of Xf^2
for more explanation u can refer to my code …
https://www.codechef.com/viewsolution/25394039
2 Likes
thanks for the solution …i totally understand by your solution and all my concepts are clear by your solution
1 Like
Hi thanks, i could not solve this problem.hey could u provide some small solution outline for MNMXAR. Also do u know when are editorials are to be released.
hey can you tell me how u got the number 900000000?
Reason you are getting run time error: x = stoll(s1, &sz, 2)[You are are converting a substring into long long] Length of substring n is big that can’t be stored in long long.
Alright, didn’t think about really long strings of very high orders. Thanks a lot!
i have taken just random number but greater than 5e8 because Xf max. value possible is 1e9 so when we sqaure it and find the numbers so it should be greater than 5e8…
Its 315 not 351 i think and i also used 2 arr containing no.of zeros and no.of ones till an idx.
Thanks … got your points …
This is because only those string will count which have length k * k + k, where k is an integer.
Reason : For a string to be special, it needs to have i * i zeroes, if it has i ones, thus the length of any special string would be number of ones (i), plus number of zeroes(i*i).
Yup my bad, its 315. And the second point is kinda trivial isnt it? I mean everyone must have done it!
Can someone help in WARTLND problem?
Doesn’t matter if we keep 315 or 351.
https://www.codechef.com/viewsolution/25401329
This is my solution by brute force, but it got TLE. Logic is that first string will be of length 2 (cn1=1+cn0=1), second will be of 6 (cn1=2+cn0=4) and so on, and check all the substrings with that length and if all conditions satisfies increase the ans by 1, can you please help?
I have also applied brute force and got AC. Try keeping an array such that the traversing time of each subarray of that specific length is reduced to O(1) time. (as you are taking O(n - x) time for traversing it). It will give you AC.
1 Like
can u explain more why this solution works ?