# COOK82C Help

Hi, I was solving up the Commonlounge ladder, and I am getting TLE in this problem : https://www.codechef.com/problems/COOK82C

My submission: https://www.codechef.com/viewsolution/27985840

I think this solution should pass according to the time constraints as the time complexity of my solution is O(63N + 63Nlog(63*N)) if I’m not wrong.

I think N log(N) with N = 64 * 10^6 is too large. You need to find a solution with better complexity.
The sort is killing your runtime. Maybe a kind of counting sort can be done?

2 Likes

Do let me know if your algo works

Here’s my approach.

Edit:

Here’s a generator that generates unpleasant testcases for this Problem:

``````// Simon St James (ssjgz) - 2019-11-28
//
// Unpleasant testcase generator for https://www.codechef.com/problems/COOK82C
//
#include <iostream>
#include <cassert>

#include <sys/time.h>

using namespace std;

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);

struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

const int N = 1'000'000;
const int M = N;
const int minPowerOf2 = 42;
const int maxPowerOf2 = 63;
uint64_t maxValue = 1;
for (int i = 0; i < maxPowerOf2; i++)
{
maxValue *= 2;
}
maxValue--;

cout << N << " " << M << endl;
for (int i = 0; i < N; i++)
{
const int powerOf2 = minPowerOf2 + rand() % (maxPowerOf2 - minPowerOf2);
assert(powerOf2 < maxPowerOf2);
uint64_t twoToThePower = 1;
for (int j = 0; j < powerOf2; j++)
{
twoToThePower *= 2;
}
assert(twoToThePower <= maxValue);
uint64_t multiplier = (maxValue / twoToThePower == 0) ? 1 : 1 + rand() % (maxValue / twoToThePower);
const uint64_t value = multiplier * twoToThePower;

assert(0 < value);
assert(value <= maxValue);

cout << (value) << " ";
}
cout << endl;
for (int i = 0; i < M; i++)
{
cout << (i + 1) << endl;
}

return 0;
}
``````
1 Like