July Cook-Off 2019 - Discussion

help
70

check your code for xf = 10^9;
It’s giving 44723 instead of 59;
You’re Welcome.

71

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
72

thanks for the solution …i totally understand by your solution and all my concepts are clear by your solution

1 Like
73

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.

74

hey can you tell me how u got the number 900000000?

75

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.

76

Alright, didn’t think about really long strings of very high orders. Thanks a lot!

77

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…

78

Its 315 not 351 i think and i also used 2 arr containing no.of zeros and no.of ones till an idx.

79

Thanks … got your points …

80

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).

81

Yup my bad, its 315. And the second point is kinda trivial isnt it? I mean everyone must have done it!

82

Can someone help in WARTLND problem?

83

Doesn’t matter if we keep 315 or 351.

85

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?

86

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
87

can u explain more why this solution works ?

88

Actually for this problem, it is not difficult to prove that the brute force solution is sub - cuberoot(X), because Y starts increasing faster than that pretty quickly, and increases even further (this is sort of a hand-waving argument, a formal proof can be constructed from this). It is in fact exponential (someone also mentioned a bound of 100). But I didn’t see this relation with fibonacci.

89

Thank you so much, got AC!

90

I actually worked for linear case:
lets say you have freq array for n=4 : [{0,1},{1,3},{2,0},{3,0}] remainder and its freq so for k=2 we do is multiplying value to all previous considered value modulo n.it will give new freq array. for k=4,so what i am doing is replacing (((x1 % n * x2 ) %n * x3 )%n x4 )%n with (x1x2)%n * (x3*x4)%n which is binary exponentiation.

1 Like