codejam 2010 qualifications

qualifications problems


A Snapper Chain

The snappers are same as incrementing binary bits. The overflow is discarded. ANDing K with 111...N bits gives the state of the snappers after K snaps. The count of 1 bits of that number if same as N means the state is ON else OFF.

string snapperChain(int n, int k)
    int nbit = (int) Math.Pow(2, n) - 1;
    int result = nbit & k;
    int count1 = count1bits(result);
    
    if (count1 == n)
        return "ON";
    else
        return "OFF";

int count1bits(int num)
    int n = num;
    int count = 0;
    while (n != 0)
        n = n & (n - 1);
        count++;
    return count;

B Fair Warning

I used this IntX code for 64+ bits data structure. The trick is to subtract the min of the array and find their gcd - which gives Tmax. ymin is calculated then. One way is to sort the array and find the gcd from index 1...N. Another way is to find the min and put checks for 0 in gcd function.

string fairWarning(IntX[] input)
    IntX Tmax = -1;
    IntX ymin = -1;

    //Array.Sort(input);
    IntX min = minf(input);
    
    for (int i = 0; i < input.Length; i++)
        input[i] = input[i] - min;
    Tmax = gcdf(input);

    if (Tmax == 0 || (min % Tmax) == 0)
        ymin = 0;
    else
        ymin = Tmax - (min % Tmax);
    
    return ymin.ToString()

//min of array
IntX minf(IntX[] input)
    IntX min = input[0];
    for (int i = 0; i < input.Length; i++)
        if (input[i] < min)
            min = input[i];
    return min;

//gcd of array
IntX gcdf(IntX[] input)
    IntX a = input[0];
    for (int i = 1; i < input.Length; i++)
        IntX b = input[i];
        if (i < input.Length-1 && a == 0)
            i++;
            a = input[i];
        if (i < input.Length-1 && b == 0)
            i++;
            b = input[i];
        a = gcdf(a, b);
    return a;

//gcd of a, b
IntX gcdf(IntX a, IntX b)
    if (a == 0 && b == 0)
        throw new ArgumentException();
    while (b != 0)
        IntX t = a % b;
        a = b;
        b = t;
    return a; count;

C Theme Park

Limits
1 <= T <= 50
gi <= k

Small dataset
1 <= R <= 1000
1 <= k <= 100
1 <= N <= 10
1 <= gi <= 10

Large dataset
1 <= R <= 10^8
1 <= k <= 10^9
1 <= N <= 1000
1 <= gi <= 10^7

My first solution was of O(R*N) time i.e. 10^8 * 10^3 which does not work for large dataset. The trick is to first calculate and cache the sums and save the next group position which takes O(N*N) time i.e. 10^6 and then add the sums in O(R) time i.e. 10^8 - the sum is calculated for each position i of N in cache[] and the next group index in nextCacheIndex[].

Int64 themePark(Int64 R, Int64 k, Int64[] q)
    Int64 totalMoney = 0;
    Int64 groups = q.Length;

    Int64[] cache = new Int64[q.Length];
    Int64[] nextCacheIndex = new Int64[q.Length];

    for (Int64 i = 0; i < groups; i++)
        Int64 sum = 0;
        Int64 nextIndex = i;

        Int64 groupCount = 0;
        //while sum <= k and not at the end of the *current* queue 
        while ((sum + q[nextIndex] <= k) && (groupCount < groups))
            sum += q[nextIndex];
            nextIndex = (nextIndex + 1) % groups;
            groupCount++;
        cache[i] = sum;
        nextCacheIndex[i] = nextIndex;

    Int64 index = 0;
    for (Int64 r = 0; r < R; r++)
        totalMoney += cache[index];
        index = nextCacheIndex[index];

    return totalMoney;

[codejam]