**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]

## No comments:

## Post a Comment