Code Jam 2010 is off to a huge start! Despite the tougher-than-usual problems and a few technical glitches, more contestants than ever advanced to Round 1 this year (about 8523). We also set records in participants who downloaded at least one input (12092), participating countries (125), and programming languages (53).
The problems were a mix of simulation, number theory and big integer arithmetic. Big integers made their first appearance in a Code Jam round as part of a problem with the foreboding name of "Fair Warning".
Cast
Problem A. Snapper Chain Written and prepared by Igor Naverniouk.
Problem B. Fair Warning Written by Bartholomew Furrow. Prepared by Xiaomin Chen and Bartholomew Furrow.
Problem C. Theme Park Written by Bartholomew Furrow and Igor Naverniouk. Prepared by Ante Derek and Bartholomew Furrow.
Contest analysis presented by Bartholomew Furrow, Igor Naverniouk, and Cosmin Negruseri.
Solutions and other problem preparation provided by David Arthur, John Dethridge, Petr Mitrichev, and Cosmin Negruseri.
The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.
When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states.
In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.
Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.
I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it's receiving power from the Snapper it's plugged into.
The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 10,000.
1 ≤ N ≤ 10;
0 ≤ K ≤ 100;
1 ≤ N ≤ 30;
0 ≤ K ≤ 108;
4 1 0 1 1 4 0 4 47
Case #1: OFF Case #2: ON Case #3: OFF Case #4: ON
On our planet, Jamcode IX, three Great Events occurred. They happened 26000, 11000 and 6000 slarboseconds ago. In 4000 slarboseconds, the amount of time since all of those events will be multiples of 5000 slarboseconds, the largest possible amount... and the apocalypse will come.
Luckily for you, you live on Jamcode X! The apocalypse came on Jamcode IX less than a year ago. But Jamcode X has a worrying prophecy: "After the moment of reckoning, on the first optimum anniversary of the N Great Events, the apocalypse will come. 64 bits will not save you. You have been warned."
The people of Jamcode X are very concerned by this prophecy. All of the Great Events have already happened, and their times have been measured to the nearest slarbosecond; but nobody knows when their optimum anniversary will occur. After studying the diary of a scientist from Jamcode IX, scientists working on the problem have come up with a theory:
The moment of reckoning is now, the moment you solve this problem. At some time y ≥ 0 slarboseconds from now, the number of slarboseconds since each of the Great Events will be divisible by some maximum number T. If you can find the smallest value of y that gives this largest possible T, that will give you the optimum anniversary when the apocalypse will come.
On Jamcode IX, for example, there were 3 Great Events and they happened 26000, 11000 and 6000 slarboseconds before the moment of reckoning. 4000 slarboseconds later, the amount of time since each event was a multiple of T=5000 slarboseconds, and the apocalypse came.
Your job is to compute the amount of time until the apocalypse comes. But remember the prophecy: even though the people of Jamcode X have been solving problems for two years, and 64-bit integers have always been enough, they might not always be enough now or in the future.
The first line of the input gives the number of test cases, C. C lines follow. Each starts with a single integer N, which is followed by a space and then N space-separated integers ti, the number of slarboseconds since Great Event i occurred.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of slarboseconds until ti + y is a multiple of the largest possible integer factor T for all i.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ C ≤ 100.
ti ≠ tj for some i, j.
2 ≤ N ≤ 3.
1 ≤ ti ≤ 108.
2 ≤ N ≤ 1000.
1 ≤ ti ≤ 1050.
3 3 26000000 11000000 6000000 3 1 10 11 2 800000000000000000001 900000000000000000001
Case #1: 4000000 Case #2: 0 Case #3: 99999999999999999999
Fortunately for the peoples of the Jamcode system, "the apocalypse" turned out to be a mistranslation of "the giant party." Nobody from Jamcode IX bothered to pass this along, because they were having so much fun.
Roller coasters are so much fun! It seems like everybody who visits the theme park wants to ride the roller coaster. Some people go alone; other people go in groups, and don't want to board the roller coaster unless they can all go together. And everyone who rides the roller coaster wants to ride again. A ride costs 1 Euro per person; your job is to figure out how much money the roller coaster will make today.
The roller coaster can hold k people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run R times in a day.
For example, suppose R=4, k=6, and there are four groups of people with sizes: 1, 4, 2, 1. The first time the roller coaster goes, the first two groups [1, 4] will ride, leaving an empty seat (the group of 2 won't fit, and the group of 1 can't go ahead of them). Then they'll go to the back of the queue, which now looks like 2, 1, 1, 4. The second time, the coaster will hold 4 people: [2, 1, 1]. Now the queue looks like 4, 2, 1, 1. The third time, it will hold 6 people: [4, 2]. Now the queue looks like [1, 1, 4, 2]. Finally, it will hold 6 people: [1, 1, 4]. The roller coaster has made a total of 21 Euros!
The first line of the input gives the number of test cases, T. T test cases follow, with each test case consisting of two lines. The first line contains three space-separated integers: R, k and N. The second line contains N space-separated integers gi, each of which is the size of a group that wants to ride. g0 is the size of the first group, g1 is the size of the second group, etc.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of Euros made by the roller coaster.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 50.
gi ≤ k.
1 ≤ R ≤ 1000.
1 ≤ k ≤ 100.
1 ≤ N ≤ 10.
1 ≤ gi ≤ 10.
1 ≤ R ≤ 108.
1 ≤ k ≤ 109.
1 ≤ N ≤ 1000.
1 ≤ gi ≤ 107.
3 4 6 4 1 4 2 1 100 10 1 1 5 5 10 2 4 2 3 4 2 1 2 1 3
Case #1: 21 Case #2: 100 Case #3: 20
The difficult part was understanding how a single Snapper works. Each Snapper can be in one of two states -- On or Off. Also, each snapper can either be powered or unpowered. The first Snapper is always powered because it is plugged into the power socket in the wall. The i'th Snapper is powered if and only if the (i-1)'th Snapper is powered and On. Snapping your fingers changes the state of each powered snapper (from On to Off, or from Off to On).
With these rules in mind, let's represent the On/Off state of the Snappers by a sequence of bits, 1 meaning On. If we list the bits right-to-left, we get a binary integer. Initially, the integer has value 0. Similarly, we can write down the binary integer for the powered/unpowered state of each Snapper. Initially, this integer is 1 because only the rightmost Snapper is powered.
Snapping your fingers is equivalent to doing an XOR of the On/Off integer and the powered/unpowered integer and putting the result into the On/Off integer. After that, we update the powered/unpowered bits according to the rule above,
For example, let's say that the On/Off number is now 10100011111. This means that the powered/unpowered number is 00000111111. When we XOR these two numbers, we get the new value of the On/Off number: 10100100000.
The interesting thing is that these two updates are equivalent to a simple increment of the On/Off integer! Snapping your fingers adds 1 to the On/Off integer, and we do not even need to care about the powered/unpowered integer.
The solution to the problem is then very simple. The answer is "ON" if and only if the rightmost N bits of K are 1.
This turned out to be the hardest problem in the qualification round. One of the reasons may have been that the solution involves big arithmetic precision. Using big numbers in timed programming contests is sometimes not considered fair because some languages like python or java have internal libraries that deal with this while for other languages you may have needed to write your own or search for a external one like the GNU Multi-Precision Library. Considering that the qualification round was 24 hours long we took this chance to give you a warning and one which is fair ... that big numbers are fair game for now on, so have a library on hand!
This problem talks about divisors and multiples so it hints at using the greatest common divisor concept in some way. To solve the problem we need to find T and afterwards we can easily find y.
Let's simplify the problem and just look at two numbers a and b. In this case we need to find the largest T so that some positive y exists where a + y and b + y are multiples of T. So (a + y) modulo T = (b + y) modulo T which means that (a - b) modulo T = 0. Thus T must be a divisor of |a - b|.
Coming back to the problem with N numbers, we have proved that T must divide every |ti - tj|. This means that the solution is the greatest common divisor of all |ti - tj| numbers. A simple observation can improve our algorithm from O(N2) to O(N) iterations of the Euclidean algorithm. Let's say a ≤ b ≤ c, then gcd(b - a, c - a) = gcd(b - a, c - a, c - b). To prove this we look at the first iteration of the Euclidean algorithm. Since a ≤ b ≤ c it means that b - a ≤ c - a so in the first step we subtract b - a from c - a: gcd(b - a, c - a) = gcd(c - b, b - a), this proves our observation. Now we can just compute the greatest common divisor of all |ti - t1| to find T.
Here's some python code from Xiaomin Chen that solves one test case:
def Gcd(a, b):
if b == 0:
return a
return Gcd(b, a % b)
def Solve(L):
y = L[0]
L1 = [abs(x - y) for x in L]
g = reduce(Gcd, L1)
if y % g == 0:
return 0
else:
return g - (y % g)
Useful concepts: Greatest common divisor, Euclidean algorithm, Arbitrary precision arithmetic.
At first glance, this problem appears to be a straightforward simulation: keep adding groups until you run out space on the roller coaster (or run out of groups), then re-form the queue and start again. Repeat this R times and you're done.
For the Small, that was enough; and we got more than a few questions during the contest from contestants thinking that they were unable to solve the Large because their computers were so slow. The fact is that, with limits so large -- up to 103 groups queuing for 109 rides -- you need to come up with a smarter algorithm to solve the problem, since that one is O(NR).
When you're sending the roller coaster out for 109 rides, you've got to expect that a few of them are going to be the same. If you store the queue of groups as an unchanging array, with a pointer to the front, then every time you send out a ride s, you could make a note of where it ended, given where it started. Then the next time you see a ride starting with the same group in the queue, you can do a quick lookup rather than iterating through all the groups.
That speeds up the algorithm by a factor of 103 in the worst case, leaving us with O(R) operations. There are some other ways of speeding up the calculation for any given roller coaster run: for example, you could make an array that makes it O(1) to calculate how many people are in the range [group_a, group_b] and then binary search to figure out how many groups get to go in O(log(N)) time. That gives a total of O(R log N) operations.
As we observed in Optimization One, you're going to see a lot of repetition between rides. You're also going to see a lot of repetition between groups of rides. In the example in the problem statement, the queue was made up of groups of size [1, 4, 2, 1]. 6 people get to go at once. Let's look at how the queue changes between rides:
1, 4, 2, 1 [5] 2, 1, 1, 4 [4] 4, 2, 1, 1 [6] 1, 1, 4, 2 [6] 2, 1, 1, 4 [4] 4, 2, 1, 1 [6] 1, 1, 4, 2 [6]As you may have noticed, there's a cycle of length three: starting from the second run, every third queue looks the same. We make 16 Euros when that happens, which means we'll be making 16 Euros every 3 runs until the roller coaster stops rolling.
So if the roller coaster is set to go 109 times: the first time it makes 5 Euros; then there are 999999999 runs left; and every three of those makes 16 Euros. 3 divides 999999999 evenly -- if it didn't, we'd have to do some extra work at the end -- so we make 5 + (999999999 / 3 * 16) = 5333333333 Euros in total.
It turns out that a cycle must show up within the first N+1 rides, because there are only N different states the queue can be in (after N, you have to start repeating). So you only have to simulate N rides, each of which takes O(N) time in the worst case, before finding the cycle: that's an O(N2) solution.
Either of the optimizations above should be enough. But if you're a real speed demon, you can squeeze out a little more efficiency by combining the binary search that we mentioned briefly in Optimization One with the cycle detection from Optimization Two, bringing our running time down to O(N log N). An alternate optimization can bring us down to O(N); we'll leave that as an exercise for the reader. Visit our Google Group to discuss it with the other contestants!