COOK82C Help

1

Hi, I was solving up the Commonlounge ladder, and I am getting TLE in this problem : COOK82C Problem - CodeChef

My submission: CodeChef: Practical coding for everyone

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.

Can anyone please help? Thanks in advance.

2

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
3

Do let me know if your algo works :slight_smile:

4

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