Let's go over the varied set of problems for Round 1C. An Overexcited Fan had to get to an elusive celebrity cat to take a photo before their tour was over. Lovers of unusual problems were over the moon with Overrandomized, which was all about focusing on the right patterns in the data. Finally, Oversized Pancake Choppers was among the more difficult pancake problems we've ever posed; its name is an overt reference to problems in two previous rounds. With 1C done, the set of Round 1s is over. Hopefully they weren't overly difficult to the point of being overwhelming.
Our first problem had a more straightforward solution than usual, involving simulation. The other two problems were hard enough that only two people solved the full set in under an hour: Rafbill with a penalty time of 35:06, and maroon only four seconds behind that at 35:10. After that, there was a gap until spencercompton, Lutyj, and fedoseev.timofey came in just past the 1 hour mark, with penalty times of 1:00:45, 1:03:37, and 1:04:39, respectively. This time, there were just over 50 perfect scores out of over 10000 contestants who submitted. Almost 90% of contestants fully solved the first problem and got their picture with Peppurr!
As usual, we will take some time to review the results, but tentatively, a score of 58, achieved fast enough, is good enough to advance. With so many test sets in this round (9, which was a record for a Round 1), there were many paths to a successful result.
If you are not among the 1500 advancing from Round 1C, or the 3000 who already advanced from Rounds 1A and 1B, your journey is unfortunately over for this year... but we hope that you enjoyed the problems and will continue to practice for next year's contest. You can also give Kick Start a try for the rest of this year. For those of you who did advance, we will see you in Round 2 in two weeks for the usual shot at a T-shirt and further Code Jam glory!
Cast
Overexcited Fan: Written by the 🐱 Peppurr Fan Squad 🐱: Darcy Best, Timothy Buzzelli, and Max Ward. Prepared by Darcy Best.
Overrandomized: Written by Ian Tullis. Prepared by Pablo Heiber.
Oversized Pancake Choppers: Written by Pablo Heiber. Prepared by Artem Iglikov.
Solutions and other problem preparation and review by Mohamed Yosri Ahmed, Liang Bai, Darcy Best, Timothy Buzzelli, John Dethridge, Md Mahbubul Hasan, Artem Iglikov, Joyce Lee, Archie Pusaka, Pi-Hsun Shih, Sudarsan Srinivasan, and Marten Wiman.
Analysis authors:
Today will be the day—today will be the day that you finally get a picture with Peppurr the cat!
It has just been announced that Peppurr will be touring your city. The city has infinitely many infinitely-long streets running north-south and infinitely many infinitely-long streets running east-west. An intersection is any point at which a north-south street and an east-west street meet. From any given intersection, the closest intersection in each of the four directions (north, east, south and west) is exactly one block away.
You know the exact path that Peppurr's tour will take along those streets. Your goal is to be at one of the intersections on Peppurr's tour at the same time that Peppurr is there, and you want to do so as fast as possible. This is how you will get your picture with Peppurr!
Peppurr's tour starts at an intersection that is X blocks east and Y blocks north of the intersection where you are currently located. Both you and Peppurr take exactly one minute to walk one full block, and must finish each minute at an intersection; neither of you can walk partial blocks.
Peppurr moves along a predefined path. Every minute, you can choose to stand still for the minute, or use it to walk a single block in any of the 4 directions (north, east, south or west). Both you and Peppurr only walk along the streets.
If you and Peppurr are at the same intersection at the same time, you can take a picture, even at the last intersection of the tour. However, Peppurr is unavailable for pictures after the tour ends, so arriving at the tour's final intersection even a single minute after the tour finishes means you will not get a picture.
Is it possible to get a picture with Peppurr? If so, how soon can you do it?
The first line of the input gives the number of test cases, T.
T test cases follow. Each case consists of one line containing two
integers, X and Y, and a string of characters M.
This represents that Peppurr's tour starts exactly X blocks east
and Y blocks north of you. The string M is the sequence
of moves that Peppurr will make.
The i-th character in M is one of N,
E, S or W, and corresponds to the
direction (north, east, south, or west, respectively) in which Peppurr will
walk one block during the tour's i-th minute.
For each test case, output one line with Case #x: y, where
x is the test case number (starting from 1). If there is no way
to get a picture with Peppurr, y is IMPOSSIBLE. Otherwise,
y is the smallest number of minutes from the start of the tour needed
to get a picture with Peppurr.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
(X, Y) ≠ (0, 0). (The tour does not start in the same intersection as you.)
0 ≤ X ≤ 10.
0 ≤ Y ≤ 10.
1 ≤ length of M ≤ 8.
Each character in M is an uppercase letter —
either N or S.
0 ≤ X ≤ 1000.
0 ≤ Y ≤ 1000.
1 ≤ length of M ≤ 1000.
Each character in M is an uppercase letter —
either N or S.
0 ≤ X ≤ 1000.
0 ≤ Y ≤ 1000.
1 ≤ length of M ≤ 1000.
Each character in M is an uppercase letter —
either N, E, S or W.
5 4 4 SSSS 3 0 SNSS 2 10 NSNNSN 0 1 S 2 7 SSSSSSSS
Case #1: 4 Case #2: IMPOSSIBLE Case #3: IMPOSSIBLE Case #4: 1 Case #5: 5
In Sample Case #1, you can walk east four blocks and you will be able to take a picture with Peppurr on the tour's last intersection.
In Sample Case #2, the tour starts off exactly three blocks to the east of you. No matter how you move, you cannot get a picture with Peppurr.
In Sample Case #3, the tour is too far north for you to get the picture before the tour ends.
In Sample Case #4, the tour will come to you after one minute, so you don't even have to move! Enjoy the picture with Peppurr! Remember that you can only take pictures in intersections, so if you moved north while the tour moved south, which would cause you to cross paths with Peppurr outside of an intersection, you could not get your picture in 0.5 minutes.
In Sample Case #5, you can move north twice, then east twice. Then, you can stay still and you will be able to take a picture with Peppurr in the next minute. There are other paths you can take which can get you a picture with Peppurr in 5 minutes, but none which can do it sooner than that.
The following two cases could not appear in Test Set 1 or Test Set 2, but could appear in Test Set 3:
2 3 2 SSSW 4 0 NESW
The correct output for these two cases would be:
Case #1: 4 Case #2: 4
Note that in Case #1, you can take a picture with Peppurr one block to the south and two blocks to the east of your original starting point.
In Case #2, Peppurr travels in a small square. You can take a picture when Peppurr returns to the starting point of that square.
Note: Every time this statement says something is randomly chosen, it means "chosen uniformly at random across all valid possibilities, and independently from all other choices".
The company Banana Rocks Inc. just wrote a premium cloud-based random number generation service that is destined to be the new gold standard of randomness.
The original design was that a group of servers would receive a request in the form of a single positive integer M of up to U decimal digits and then respond with an integer from the range 1 through M, inclusive, chosen at random. However, instead of simply having the output written with digits 0 through 9 as usual, the servers were "overrandomized". Each server has a random subset of 10 distinct uppercase English letters to use as digits, and a random mapping from those letters to unique values between 0 and 9.
The formal description of the current situation is as follows: each server has a
digit string D composed of exactly 10 different uppercase English letters.
The digit string defines the mapping between letters and the base 10 digits:
D's j-th character from the left (counting from 0) is the base 10 digit of value j.
For example, if D were CODEJAMFUN then C would represent
digit 0, O would represent digit 1 and N would represent
digit 9. The number 379009 would be encoded as EFNCCN when using that
digit string.
When receiving the i-th query with an integer parameter Mi, the server:
We collected some data that we believe we can use to recover the secret digit string D from each server. We sent 104 queries to each server. For each query, we chose a value Mi at random from the range 1 through 10U - 1, inclusive, and received the response Ri, a string of up to U uppercase English letters. We recorded the pairs (Mi, Ri). As we were moving these records to a new data storage device, the values of all the integers Mi within the records of some servers became corrupted and unreadable.
Can you help us find each server's digit string D?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains the records for one server and starts with a line containing a single integer U, representing that 10U - 1 is the inclusive upper bound for the range in which we chose the integers Mi to query that server. Then, exactly 104 lines follow. Each of these lines contains an integer Qi (in base 10 using digits 0 through 9, as usual) and a string Ri, representing the i-th query and response, respectively. If Qi = -1, then the integer Mi used for the i-th query is unknown. Otherwise, Qi = Mi.
For each test case, output one line containing
Case #x: y, where x
is the test case number (starting from 1) and y is the digit string D
for the server examined in test case x.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 10.
D is a string of exactly 10 different uppercase English letters, chosen independently and
uniformly at random from the set of all such strings.
Mi is chosen independently and uniformly at random from the range 1 through
10U - 1, inclusive, for all i.
Ni is chosen independently and uniformly at random from the range 1 through
Mi, inclusive, for all i.
Ri is the base 10 representation of Ni, using the j-th digit from
the left of D (counting starting from 0) as the digit of value j, for all i.
Qi = Mi, for all i.
U = 2.
Qi = Mi, for all i.
U = 16.
Qi = -1, for all i.
U = 16.
The sample input is too big to display inline, so we are providing downloadable files instead for the input and output.
You just showed up to your job as the head chef of the Infinite House of Pancakes, and as usual, you found a disaster in progress! The other chefs accidentally created some enormous circular pancakes, all of the same size. These pancakes are too large to serve whole, so they have already started to chop them up into slices (which, in this problem, are circular sectors). You currently have N slices, the i-th of which is a sector with an internal (central) angle of Ai nanodegrees (a nanodegree is 10-9 degrees).
You have D diners waiting for their food. Each diner wants a single slice that is the same size as every other diner's slice, although they do not care what that size is. But it may not be possible to do this using the current slices, so you may need to make one or more radial cuts.
A cut changes an existing slice with internal angle X into two new slices with internal angles Y and X - Y. You can do this for any 0 < Y < X, and these values do not need to be integers. You may apply further cuts to either or both of these new slices, and so on.
It is OK to have one or more leftover slices (of any size) that are not given to the diners; you can eat those later, since this disaster is making you miss your own breakfast!
Determine the smallest total number of cuts you need to make to satisfy the diners.
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing two integers N and D: the number of slices you currently have and the number of diners. Then, there is one more line containing N integers A1, A2, ..., AN; the i-th of these represents the internal angle (in nanodegrees) of the i-th slice.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is the smallest number of cuts you need, as described above.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ai < 360 × 109, for all i.
Time limit: 20 seconds.
1 ≤ N ≤ 300.
2 ≤ D ≤ 3.
Time limit: 20 seconds.
1 ≤ N ≤ 300.
2 ≤ D ≤ 50.
Time limit: 60 seconds.
For exactly 21 cases, 9000 ≤ N ≤ 10000.
For exactly T-21 cases, 1 ≤ N ≤ 1000.
2 ≤ D ≤ 50.
4 1 3 1 5 2 10 5 359999999999 123456789 10 2 3 8 4 3 2 1 2 3
Case #1: 2 Case #2: 0 Case #3: 1 Case #4: 1
In Sample Case #1, you only have one tiny slice to start with. The optimal solution is to use one cut to change it into two slices with angles of 1/3 nanodegree and 2/3 nanodegrees, and then further cut the latter slice into two more slices with angles of 1/3 nanodegree.
In Sample Case #2, you already have two slices of the same size, so you can give those to the two diners, and you do not need to make any cuts.
In Sample Case #3, the optimal solution is to cut the slice with internal angle 8 nanodegrees in half. After that operation, you have exactly 3 slices of internal angle 4 nanodegrees, with no leftovers.
In Sample Case #4, remember that every diner must receive a single slice. You cannot give one diner the "3" slice and the other diner the "1" and "2" slices, even though the total areas are the same. You must make at least one cut in this case to satisfy the requirements.
In Test Set 1, we can try every possible path we can take. During any given minute we have 5
options: walk a block in one of the 4 directions, or stay still. Since Peppurr's tour is at
most 8 minutes long, we can only walk for at most 8 minutes.
That is at most 58 possibilities, which is a pretty small
number for a computer. For each combination, we simulate our own path and Peppurr's path,
recording any encounters. After trying all possibilities, the solution is
IMPOSSIBLE if we did not record any encounters, or the earliest time of those
if we did.
In Test Set 2, just as in Test Set 1, Peppurr's tour will remain within a single north-south street. Notice that if we want to meet Peppurr at an intersection (a, b), the order in which we walk the blocks doesn't matter as long as we walk east a times more than west and north b times more than south. So we may assume that we can finish all of our eastward walking, for example, before walking in any other direction. This means an optimal strategy can begin with X blocks of walking east. After that, we are in the same north-south street as Peppurr, so we can walk towards the tour until we meet or we are just 1 block away, in which case we need to stand still for 1 minute to avoid crossing paths with the tour in the middle of a block.
For Test Set 3, we can simulate Peppurr's tour. If after R minutes it is XR blocks to the east of us and YR blocks to the north (XR and YR can be negative to represent being west or south), we only need to check whether we can reach that intersection in R minutes. Fortunately, this is easy to check: the intersection is reachable in R minutes or less if and only if |XR| + |YR| ≤ R. That is, the intersection must be within an L1 distance (also known as Manhattan Distance) of R.
Therefore, we can solve the problem by simulating Peppurr's path, and for the i-th intersection
visited, check if it's reachable in i minutes. If it is, then i is the answer; otherwise, we
need to keep looking. If none of the intersections is reachable within the required time, we
answer IMPOSSIBLE.
In Test Set 1, the range for possible M values is so small compared to the number of records that each combination (Mi, Ni) has a somewhat large probability 1 / (99 × Mi) of appearing as a particular record, and an even larger probability of being present as at least one record.
Suppose there exists at least one record with Mi = Ni = x for each x in the range 1 through 9. From the record with Mi = Ni = 1 we know that the only letter in Ri represents 1. Then, from all the records with Mi = 2, we can discard the ones where Ri represents 1. The leftovers must be the ones with Mi = Ni = 2, and in those, the only letter in Ri represents 2. In general, after we have decoded the letters for 1 through x, we can take the records with Mi = x + 1 and discard the ones with letters in Ri that are already assigned, and the Ri values of the remaining records will contain the letter that should be assigned to x + 1. Finally, the only remaining unassigned letter should be assigned to 0.
This process works as long as records with Mi = Ni = x exist for each x in the range 1 through 9. The probability of that happening is hard to calculate, but the least likely of those combinations is Mi = Ni = 9, with a probability of only 1 / (99 × 9) per record. The probability of that appearing at least once in 10000 records is greater than 99.999%. The smaller values of x have even higher probability. Of course, the probability of all 9 coexisting is smaller than that, and the probability of that happening in all 10 cases is even smaller, but still decent enough. In addition, there is a really small probability that the letter representing 0 doesn't appear at all in the input, but if that were the case, no algorithm could find it. Given that this is a Visible Verdict test set, we can give the solution a try, and confirm that it passes.
There are additional heuristics we could add to the algorithm. For example, if we can't find the value for 9 in this way and we need to distinguish the two remaining letters to assign to 9 and 0, just having a record whose Ri starts with one of the letters is enough to know that that one should be a 9, since 0 cannot be a leading digit. This further increases the probability of the method working. We can add more and more heuristics to cover the remaining cases, but at some point it's easier to just try something more general.
In Test Set 2, the probability of Mi being a single digit is small, and we cannot rely on that happening, let alone several times and with extra conditions. However, we can treat records that have Mi and Ri of the same length similarly, by simply using their first letters and then using those (digit, letter) pairs as we did in the solution for Test Set 1.
At this point, it seems like we may have to throw all of the above insights away, because they are all predicated on knowing Mi. However, the "use the leading digit/letter" insight we used to solve Test Set 2 is actually the first step toward solving Test Set 3 as well.
In Test Set 3, each record's information comes from a single integer, not two, so we cannot use the association between the two parts as before. We can start by checking the distribution used to generate the only piece of information we have. The probability of any particular Ni being equal to x is the sum of 10-16 / y for y in [x, 1016 - 1], which can be approximated by 10-16 (ln 1016 - ln x). In other words, the probability is decreasing in x. Because of this, leading digits are more likely to be smaller than larger. Moreover, even though the decrease in probability between the actual result being x and x + 1 is small, the decrease in probability between the leading digit being d and d + 1 is large, because it aggregates the differences between the probability of dS being more than the probability of (d+1)S for each possible suffix S. This is a version of Benford's law.
Therefore, a possible solution is to calculate the frequency with which each letter appears as a leading digit, and assign the highest frequency to 1, the second highest to 2, etc. The only letter that never appears as a leading digit, and therefore has the minimum frequency, should be assigned to the digit 0.
In the first test set, we are only asked to produce 2 or 3 equal slices. Let us consider these cases separately.
For D=2, if we already have two equal slices, then we don't need any cuts. If no two slices are equal, then we can cut any slice into two equal halves with one cut.
Similarly, for D=3, if we already have three equal slices, then we don't need any cuts. We can also cut any slice into three equal slices with two cuts. The extra case to consider is whether we can do it with a single cut.
If we do only 1 cut we end up with N+1 slices: N-1 original slices and two new slices. Three of them need to be of the same size, so this size has to be equal to the size of at least one uncut slice. We can try all possibilities (up to N) for the target size and all possibilities (up to N) for which slice we cut. If the slice p to be cut is not larger than the target size s, we disregard the case. Otherwise, we cut p into a part of size s and another part of size Ap-s. Then, if there are 3 slices of size s in the set of N+1 slices, it is possible to do it with one cut. If that doesn't happen for any of the considered possibilities, then we definitely need two.
Let's define a fully-usable slice as a slice which we can use fully to produce the slices we need, either by cutting it into 2 to D equal sized slices, or just using it in its entirety as it is. That is, a fully-usable slice is a slice that will leave no further leftovers.
Here is a key observation: for every slice we will produce, we will need to use one cut, except possibly for one slice cut from each fully-usable slice we use. That is, we will need D-K cuts to produce D equal slices, where K is the number of slices used fully.
For example:
Also notice that we never have to consider K=0, since K=1 is always possible by cutting one original slice into equal pieces, and we want the maximum possible K.
By the observation above, the final size of our produced slices (hereafter the target size) is going to be one of the original sizes (from one of the slices we fully use) divided by an integer between 1 and D. Therefore, we have to check at most N×D possible target sizes. With any other size, we would have 0 fully-usable slices.
For each such target slice size, we should do the following:
The part above can be done in O(N) time if we sort the Ais once (in non-decreasing order) at the beginning, resulting in an O(D×N2) time complexity for the overall algorithm.
First of all, notice that we can precompute the largest possible target slice size in O(log(max(Ai))×N) time with a binary search on the target size. Then, we can save some time by not considering any target slice sizes that are greater than the calculated limit.
Now, as in the solution for Test Set 2, we iterate through the Ais (in non-decreasing order) and all numbers of cuts c (1 to D). Instead of doing an additional pass through N original slices as in the solution for Test Set 2, we can just mark this original slice as a fully-usable slice for target size Ai/c. To do that efficiently, we use a dictionary (ideally implemented as a hash table) where the keys are valid target sizes, and the values are tuples containing the number of fully-usable slices found so far for that target size, and the number of target slices produced from them. Notice that the keys are fractions; to ensure that we do not represent the same fraction in multiple ways, we can use an algorithm to find greatest common divisors and ensure that all fractions are reduced.
For each target size Ai/c we add 1 and c to the corresponding dictionary values for key Ai/c (assuming the default value for an unset key is zero). If after this operation the number of produced target slices of size Ai/c would exceed D, we should just not consider that slice as fully-usable for this case.
Then we can choose the maximum possible number M of fully-used slices across all valid target slices, and the result is D-M. This improves the time complexity of the algorithm to O(D×N).