July Cook-Off 2019 - Discussion

help
1

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

3 Likes
2

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

8 Likes
3

Ya, that’s what I have done

4

i got TLE with brute force

5

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

2 Likes
6

I’m just a piece of junk.

3 Likes
7

I wish I was a piece of junk like you.

6 Likes
8

https://www.codechef.com/viewsolution/25385403
My AC solution with brute force

1 Like
9

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:- CodeChef: Practical coding for everyone

1 Like
10

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

2 Likes
11

k*k+k ? Can you explain?

12

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

1 Like
13

can someone explain the solution for two variable

14

vector v;
for(int i=1; i<=100000;i++){
if(isInt(sqrt(4i+1)) && int(sqrt(4i+1))%2==1 ) v.push_back(i);
}
The possible lengths !

1 Like
15

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

3 Likes
16

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

2 Likes
17

#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!!

1 Like
18

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

19

can you tell something about time complexity of this solution ??
@l_returns :pleading_face::pleading_face:

1 Like
20

it is possible in python with some optimizations ~ look at my code →
https://www.codechef.com/viewsolution/25387447