July Cook-Off 2019 - Discussion

l_returns · July 21, 2019, 7:17pm

as we know fib(2n-1) = fib(n)^2 + fib(n-1)^2
Now as fib is exponentially increasing. The complexity will be less than O(\log_2{N}) (inverse of exponentially increasing function)
Though not sure. We’ll see in editorial !

atiaditya369 · July 21, 2019, 7:18pm

See, we have to count the no of pairs i,j such that c0 = c1c1. Lets consider the length of substring be n and no of 1’s in that string be k, so no of zeroes would be (n-k). Now your equation will be like this : (n-k) = kk. So k*k + k is the length of the substring required. The maximum value of k can be around sqrt(n). So the overall complexity would be only O(Tnsqrt(n)) which is enough to get AC.

loopfree · July 21, 2019, 7:19pm

Thank you. That’s true. I’m ashamed of my stupidity.

harshraj22 · July 21, 2019, 7:19pm

but how do you relate the solution to fibonachi numbers ??
did you even click on the link ??

l_returns · July 21, 2019, 7:21pm

XD. maybe \hspace{0mm}
One possible sequence of values of X is 0→1→2→3→5→8.
This is fibonacci. I didn’t tried solving the que but saw this explanation.

harshraj22 · July 21, 2019, 7:21pm

then how are the two related ??

aryan12 · July 21, 2019, 7:22pm

So basically,

There are 2^n substrings of a binary string. Making some observations, we come to know that we need only substrings of some particular length.
(i.e (for each cnt1 = 0; to a number(x)) where (cnt0 + (x * x) <= length) and incrementing the value of cnt1 by 1 will break this rule in the problem, we need cnt0 + cnt1 length of substrings)

Now, for each value of cnt1, count the no of substrings where the given condition is satisfied.

The only thing left to do is traversing the substrings in O(1) time, else it will give you a TLE. For this, you keep an array counting the no of zeroes in the string from starting to that position.

Thus,
No of zeroes in substring = arr[right] - arr[left], and ones is the size of the substring minus the no of zeroes. Here right and left are the upper and lower limits of the array respectively. You can do your work with no of zeroes and ones.

I hope you could understand.

For help:
My solution: CodeChef: Practical coding for everyone

l_returns · July 21, 2019, 7:23pm

edited my answer \hspace{0mm}

harshraj22 · July 21, 2019, 7:24pm

but the solution, it shouldn’t pass the time limit. seems like T*log(n)*sqrt(n). ?? Is this correct ?

sharath1999 · July 21, 2019, 7:24pm

I’m new to CC this being my second contest i’m getting shit on by TLEs , I got the logic behind twoVar and bday but both were TLE.
Can someone give me some tips to go around this

ayush4 · July 21, 2019, 7:26pm

I too tried this logic just couldn’t code it, had no proofs either. Another pattern for 8
0 -> 1 -> 3 -> 4 -> 6 -> -> 8

kamesh_11 · July 21, 2019, 7:26pm

Thank you so much!!!

l_returns · July 21, 2019, 7:27pm

It won’t be greater than O(T*\sqrt{N}). as y+=p*p hence it takes at most sqrt(n) steps.
PS: its O(40) for n=10^6

loopfree · July 21, 2019, 7:28pm

I don’t think he’s going to let us build arrays like that, because the only thing that really works for us is the 2^i.

harshraj22 · July 21, 2019, 7:30pm

what about sqrt function ? isn’t it O(sqrt(n)) . also, won’t the while loop be running log(n) times as it is becoming sqrt(2) times on every iteration ??

l_returns · July 21, 2019, 7:31pm

you can consider sqrt function as O(1). It’s not a loop.
Or O(log(N)) as @aryanc403 said which is a very small number.

bufftowel · July 21, 2019, 7:32pm

Well I don’t really understand why we only need k : k= 2^i , guess I’ll wait for the editorial.

loopfree · July 21, 2019, 7:39pm

Can it solved by brute forces ? , even though I have TLE.

l_returns · July 21, 2019, 7:40pm

Thanks maybe. \hspace{0mm}

loopfree · July 21, 2019, 7:44pm

I guess it’s probably O (nlogn*C), which may have some constant time complexity.