What is your solution to Two Variables and Birthday Gift Again ?

Birthday again is brute force.

Just check all subarrays with size = k*k+k

Complexity = O(T*N*\sqrt{N}) because there are less than \sqrt{N} sizes possible and checking all subarrays with **size=constant** takes O(n).

PS: use prefix sum for checking each subarray.

https://www.codechef.com/viewsolution/25384163

Ya, that’s what I have done

i got TLE with brute force

how does this run in time? shouldn’t it be 10^8.5 operations

I’m just a piece of junk.

I wish I was a piece of junk like you.

But it depends on the programming langugage you are using. I tried it with python but it showed TLE but the same solution with pypy3 got accepted with 0.98s.

My solution:- https://www.codechef.com/viewsolution/25387628

I solved Bday Gift one quite quickly with a sort of brute force but not exactly BF. Hold on i’ll post my Logic in a while .

PS- i loved it <3

k*k+k ? Can you explain?

@ l_returns Can you please explain your brute force a little especially k*k+k part …??

can someone explain the solution for two variable

vector v;

for(int i=1; i<=100000;i++){

if(isInt(sqrt(4*i+1)) && int(sqrt(4*i+1))%2==1 ) v.push_back(i);

}

The possible lengths !

Que says cnt_0=cnt_1*cnt_1

Lets assume cnt_1=k

now hence size of subarray = cnt_0 + cnt_1 = cnt_1*cnt_1 + cnt_1 = k*k+k.

@hetp111 @rk_221b

How to solve EXPTPROD? I think only of matrix multiplication.

#include <bits/stdc++.h>

using namespace std;

int main() {

// your code goes here

int t;

cin >> t;

while(t–)

{

string s;

cin >> s;

int n = s.length();

long long c = 0;

long long c0, c1, x;

string s1;

for(int i = 0; i < n; i++)

{

for(int j = 2; j <= n - i; j++)

{

s1 = s.substr(i, j);

string::size_type sz = 0;

x = stoll(s1, &sz, 2);

c1 = __builtin_popcount(x);

c0 = s1.length() - c1;

if(c0 == c1 * c1)

c++;

}

}

printf("%d\n", c);

}

return 0;

}

This is my code using Brute force for sub-array computation. My sample test case passed, but i get a run-time error(SIGABRT) during submission. Any help wrt why that is happening? Even some test cases which can break the code would do.

Thanks!!

Right I missed that que. Started contest one hour late otherwise my rank would have been ~50

it is possible in python with some optimizations ~ look at my code ->

https://www.codechef.com/viewsolution/25387447