Round 1B opened with Manhattan Crepe Cart, which became a lot easier if you realized that the multiple dimensions in the problem could be handled independently. In Draupnir, just as in this year's other interactive problems so far, you were able to ask for only a very small amount of data, from which you had to extract a lot of information. (Code Jam authors don't always attend the opera, but when they do, they end up writing contest problems in their heads instead of paying attention!) Finally, Fair Fight presented a dueling challenge that was tough even for a third Round 1 problem.
Benq earned our first perfect score, only 29 minutes and 41 seconds into the contest (plus 4 minutes for one penalty attempt). Just as in 1A, our second perfect score came from a previous Distributed Code Jam champion, and in this case a two-time one: bmerry. That was at 42:35, and the third perfect score was from alex20030190 at 52:17. By the end of the contest, there were almost 200 perfect scores — our contestants never cease to impress us!
This time, the (tentative) cutoff for advancement is 51 points plus a small enough penalty time. That corresponds to solving all of the first problem and the Visible test sets of the other two. Once again, our interactive problem turned out to be a bit tougher than anticipated!
As usual, we will need some time to review the submissions before finalizing the results, but if you make the cut, you can expect confirmation within the next few days. Otherwise, next weekend's Round 1C will be the last chance to advance to Round 2. Good luck!
Cast
Manhattan Crepe Cart: Written by Shane Carr. Prepared by Anubhav Srivastava.
Draupnir: Written by Ian Tullis. Prepared by Pablo Heiber.
Fair Fight: Written by Kevin Tran. Prepared by Darcy Best and Kevin Tran.
Solutions and other problem preparation and review by Patrick Au, Liang Bai, Darcy Best, Shane Carr, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Andy Huang, Ray Robinson, and Kevin Tran.
Analysis authors:
There are a lot of great streetside food vendors in Manhattan, but without a doubt, the one with the tastiest food is the Code Jam Crepe Cart!
You want to find the cart, but you do not know where it is, except that it is at some street intersection. You believe that people from across Manhattan are currently walking toward that intersection, so you will try to identify the intersection toward which the most people are traveling.
For the purposes of this problem, Manhattan is a regular grid with its axes aligned to compass lines and bounded between 0 and Q, inclusive, on each axis. There are west-east streets corresponding to gridlines y = 0, y = 1, y = 2, …, y = Q and south-north streets corresponding to gridlines x = 0, x = 1, x = 2, …, x = Q, and people move only along these streets. The points where the lines meet — e.g., (0, 0) and (1, 2) — are intersections. The shortest distance between two intersections is measured via the Manhattan distance — that is, by the sum of the absolute horizontal difference and the absolute vertical difference between the two sets of coordinates.
You know the locations of P people, all of whom are standing at intersections, and the compass direction each person is headed: north (increasing y direction), south (decreasing y direction), east (increasing x direction), or west (decreasing x direction). A person is moving toward a street intersection if their current movement is on a shortest path to that street intersection within the Manhattan grid. For example, if a person located at (x0, y0) is moving north, then they are moving toward all street intersections that have coordinates (x, y) with y > y0.
You think the crepe cart is at the intersection toward which the most people
are traveling. Moreover, you believe that more southern and western parts of
the island are most likely to have a crepe cart, so if there are multiple
such intersections, you will choose the one with the smallest non-negative
x coordinate, and if there are multiple such intersections with
that same x coordinate, the one among those with the smallest
non-negative y coordinate. Which intersection will you choose?
The first line of the input gives the number of test cases, T.
T test cases follow. Each test case starts with one line containing
two integers P and Q: the number of people, and the maximum
possible value of an x or y coordinate in Manhattan, as described above.
Then, there are P more lines. The i-th of those lines contains two
integers Xi and Yi, the current location
(street corner) of a person, and a character Di, the
direction that person is headed. Di is one of the uppercase
letters N, S, E, or W,
which stand for north, south, east, and west, respectively.
For each test case, output one line containing Case #t: x y,
where t is the test case number (starting from 1) and
x and y are the horizontal and vertical coordinates
of the intersection where you believe the crepe cart is located.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ P ≤ 500.
0 ≤ Xi ≤ Q, for all i.
0 ≤ Yi ≤ Q, for all i.
For all i, if Xi = 0,
Di ≠ W.
For all i, if Yi = 0,
Di ≠ S.
For all i, if Xi = Q,
Di ≠ E.
For all i, if Yi = Q,
Di ≠ N.
Q = 10.
Q = 105.
3 1 10 5 5 N 4 10 2 4 N 2 6 S 1 5 E 3 5 W 8 10 0 2 S 0 3 N 0 3 N 0 4 N 0 5 S 0 5 S 0 8 S 1 5 W
Case #1: 0 6 Case #2: 2 5 Case #3: 0 4
In Sample Case #1, there is only one person, and they are moving north from (5, 5). This means that all street corners with y ≥ 6 are possible locations for the crepe cart. Of those possibilities, we choose the one with lowest x ≥ 0 and then lowest y ≥ 6.
In Sample Case #2, there are four people, all moving toward location (2, 5). There is no other location that has as many people moving toward it.
In Sample Case #3, six of the eight people are moving toward location (0, 4). There is no other location that has as many people moving toward it.
Odin has some magical rings which produce copies of themselves. Each "X-day ring" produces one more X-day ring every X days after the day it came into existence. These rings come in six possible varieties: 1-day, 2-day, ..., all the way up to 6-day.
For example, a 3-day ring that came into existence on day 0 would do nothing until day 3, when it would produce another 3-day ring. Then, on day 6, each of those two rings would produce another 3-day ring, and so on.
You know that Odin had no rings before day 0. On day 0, some rings came into existence. At the end of day 0, Odin had Ri i-day rings, for each 1 ≤ i ≤ 6. You know that 0 ≤ Ri ≤ 100, for all i, and at least one of the Ri values is positive.
Fortunately, you also have access to the secret well of knowledge. Each time you use it, you can find out the total number of rings that Odin had at the end of a particular day between day 1 and day 500, inclusive. The well will give you the answer modulo 263, because even it can only hold so much information! Moreover, you can only use the well up to W times.
Your goal is to determine how many rings of each type Odin had at the end of day 0 — that is, you must find each of the Ri values.
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, your program should read a single line containing two integers T, the number of test cases, and W, the number of times you are allowed to use the well of knowledge per test case. Then, you need to process T test cases.
In each test case, your program processes up to W + 1 exchanges with our judge. You may make up to W exchanges of the following form:
-1.
After between 0 and W exchanges as explained above, you must perform one more exchange of the following form:
1 if
your answer is correct, and -1 if it is not (or you have
provided a malformed line).
After the judge sends -1 to your input stream (because of either
invalid data or an incorrect answer), it will not send any other output.
If your program continues to wait for the judge after receiving
-1, your program will time out, resulting in a Time Limit
Exceeded error. Notice that it is your responsibility to have your program
exit in time to receive a Wrong Answer judgment instead of a Time Limit
Exceeded error. As usual, if the memory limit is exceeded, or your program
gets a runtime error, you will receive the appropriate judgment.
1 ≤ T ≤ 50.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
W = 6.
W = 2.
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
This interaction corresponds to Test set 1. Suppose that, unbeknownst to us, the judge has decided that Odin had one ring of each of the six types at the end of day 0.
t, w = readline_int_list() // Reads 50 into t and 6 into w
printline 3 to stdout // Asks about day 3.
flush stdout
n = readline_int() // Reads 15 into n.
printline 1 to stdout // Asks about day 1.
flush stdout
n = readline_int() // Reads 7 into n.
printline 1 1 1 3 0 0 to stdout
flush stdout // We make a guess even though we could have
// queried the well up to four more times.
verdict = readline_int() // Reads -1 into verdict (judge has decided our
// solution is incorrect)
exit // Exits to avoid an ambiguous TLE error
Notice that even though the guess was consistent with the information we received from the judge, we were still wrong because we did not find the correct values.
En garde! Charles and Delila are about to face off against each other in the final fight of the Swordmaster fencing tournament.
Along one wall of the fencing arena, there is a rack with N different types of swords; the swords are numbered by type, from 1 to N. As the head judge, you will pick a pair of integers (L, R) (with 1 ≤ L ≤ R ≤ N), and only the L-th through R-th types of swords (inclusive) will be available for the fight.
Different types of sword are used in different ways, and being good with one type of sword does not necessarily mean you are good with another! Charles and Delila have skill levels of Ci and Di, respectively, with the i-th type of sword. Each of them will look at the types of sword you have made available for this fight, and then each will choose a type with which they are most skilled. If there are multiple available types with which a fighter is equally skilled, and that skill level exceeds the fighter's skill level in all other available types, then the fighter will make one of those equally good choices at random. Notice that it is possible for Charles and Delila to choose the same type of sword, which is fine — there are multiple copies of each type of sword available.
The fight is fair if the absolute difference between Charles's skill level with his chosen sword type and Delila's skill level with her chosen sword type is at most K. To keep the fight exciting, you'd like to know how many different pairs (L, R) you can choose that will result in a fair fight.
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing the two integers N and K, as described above. Then, two more lines follow. The first of these lines contains N integers Ci, giving Charles' skill levels for each type of sword, as described above. Similarly, the second line contains N integers Di, giving Delila's skill levels.
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 number of choices you can make that result in a fair fight, as
described above.
1 ≤ T ≤ 100.
0 ≤ K ≤ 105.
0 ≤ Ci ≤ 105, for all i.
0 ≤ Di ≤ 105, for all i.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ N ≤ 100.
N = 105, for exactly 8 test cases.
1 ≤ N ≤ 1000, for all but 8 test cases.
6 4 0 1 1 1 8 8 8 8 8 3 0 0 1 1 1 1 0 1 0 3 3 5 0 0 8 0 8 0 4 0 4 0 4 3 0 1 0 0 0 1 2 5 2 1 2 3 4 5 5 5 5 5 10
Case #1: 4 Case #2: 4 Case #3: 1 Case #4: 0 Case #5: 1 Case #6: 7
In Sample Case #1, the fight is fair if and only if Charles can use the last type of sword, so the answer is 4.
In Sample Case #2, there are 4 fair fights: (1, 2), (1, 3), (2, 2), and (2, 3). Notice that for pairs like (1, 3), Charles and Delila both have multiple swords they could choose that they are most skilled with; however, each pair only counts as one fair fight.
In Sample Case #3, there is 1 fair fight: (1, 1).
In Sample Case #4, there are no fair fights, so the answer is 0.
In Sample Case #5, remember that the duelists are not trying to make the fights fair; they choose the type of sword that they are most skilled with. For example, (1, 3) is not a fair fight, because Charles will choose the first type of sword, and Delila will choose the third type of sword. Delila will not go easy on Charles by choosing a weaker sword!
In Sample Case #6, there are 7 fair fights: (1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4), and (4, 4).
Test sets 1 and 2 differ only in how large the available grid area is. In the first test set, people can only be standing in cells with coordinates between 0 and 10, inclusive, in either dimension. Moreover, we can notice that the cart can only be in a cell within this area. The cart's horizontal and vertical coordinates must both be nonnegative per the rules of a problem. Moreover, it cannot have a coordinate larger than 10 (in either dimension). Suppose, for example, that the cart had a horizontal coordinate greater than 10; then that would imply that there must be at least one person standing at horizontal coordinate 10 and facing east. Otherwise, placing the cart at horizontal coordinate 10 would be even better, per the tiebreaker rules. But the rules of the problem do not allow people at (horizontal/vertical) coordinate 10 to face (east/north).
Therefore, to solve test set 1, we can create an array to represent all of the blocks in the allowed area, and initialize each cell's value to 0. Then, for each person, we increment all of the cells of the array that they are walking toward. Finally, we find the cell of the array with the maximum value, using the tiebreaker rules as needed. This solution takes O(P × Q2) time.
In problems that involve multiple dimensions, it is often worth checking whether those dimensions are independent. In this case, they are! A person heading west, for example, gives us a "vote" for the crepe cart being to the west of them, but tells us nothing at all about the north-south location of the cart. So we can solve the two dimensions as separate one-dimensional problems; the horizontal problem includes only the people heading west or east (and their horizontal positions), and the vertical problem includes only the people heading south or north (and their vertical positions). Let us consider the horizontal dimension for now; our arguments also apply to the vertical dimension.
Even if our people are widely spread out along the horizontal axis, the crepe cart can only possibly be in a limited number of horizontal positions. In fact, it must be either at position 0, or at a cell that is one cell to the east of some person. To see why, suppose that the cart is in some other cell 1 ≤ C ≤ Q. Let W denote the cell one unit to the west of C. We know by assumption that W does not contain a person. But then if we move the cart from C to W, we will not be losing any votes (i.e. any person voting for C is also voting for W), and we many even gain votes (if there were people in C who were heading west). (Notice that a person does not vote for the cell they are in.) Even if we do not gain votes, our tiebreaker gets better. So we should always make this move, and, therefore, we should always move the cart west until it is at 0 or immediately to the east of someone. Observe that this might find only a locally optimal solution, but if we check all such cells, we will surely find the globally optimal solution.
These observations reduce the number of cells we need to check to O(P) rather than O(Q). To check a cell, we can make a linear pass over all of the people, and count whether each one is voting for that cell. One such check takes O(P) time. Then we choose the cell that got the most votes, breaking a tie if needed by choosing the westernmost of the tied cells. The overall time complexity is O(P2) for the one-dimensional problem, and solving it twice (for two dimensions) is still O(P2).
Although the above solution is fast enough to solve test set 2, we can do even better by avoiding making a linear pass over the data for each person.
We can first process our data into a set of tuples like the following: (coordinate, number of people at that coordinate facing west, number of people at that coordinate facing east). Let us denote these as (Ci, Wi, Ei). (Remember that for the purposes of the horizontal subproblem, we are ignoring people facing north or south.) Using a hash-based dictionary, this processing takes time linear in P. As we do this, we should also determine the total numbers W and E of people facing west and east.
Then, we sort these tuples in ascending order of their first values. It is probably most convenient to use a common sorting algorithm (or one built into your language), making this step nonlinear. (We will leave a spirited discussion of which sorting algorithms are truly linear for another day.)
Once we have sorted the tuples, we start by considering cell 0 as a candidate location, and we determine the votes for that cell. We know that quantity is equal to W minus the number of people in cell 0, if any. We make a note of this number of votes and set 0 as our best candidate so far. Then, we look at the first tuple in our sorted list, which represents the people at some cell C (which might be cell 0). The number of votes for cell C + 1 (the cell one unit to the east of C) should be the same as the number of votes we found for cell 0, plus the number of people in cell C facing east (which is all of them in this case), minus the number of people in cell C facing west. If cell C is a better candidate, we store it and its number of votes.
We can do this for every tuple in our list to get our final answer. If we have one or more people on the eastern border, we do not need to check the cell one unit to the east of them, since (as explained at the start of the analysis) the cart can never have a coordinate larger than Q. Since the check for each entry of the tuple takes constant time, the full pass takes O(P) time.
In this problem, we need to determine the number of each type of X-day ring by querying the total number of rings in existence at the end of a certain day.
Let R1 be the number of 1-day rings, R2 be the number of 2-day rings, ... etc. at the end of day 0. The number of X-day rings doubles at the end of every day that is a multiple of X. Thus, the total number of rings on day i is
R1*2i + R2*2floor(i/2) + R3*2floor(i/3) + R4*2floor(i/4) + R5*2floor(i/5) + R6*2floor(i/6).
In the first test set, we are allowed six queries to determine the six unknown variables. Note that if we query any day number larger than 63, then the number of 1-day rings on that day will be a multiple of 263 (equivalently, it is 0 modulo 263). Similarly, if we query any day number larger than X*63, then the number of X-day rings will be 0 modulo 263 on that day.
Thus, on day 315 (=5*63), the total number of rings, modulo 263, is R6*252 (since the number of 1-day, 2-day, ..., 5-day rings are all 0 modulo 263). Since R6 ≤ 100, we know that R6*252 does not exceed 263, so we can directly determine R6. Then, on day 252 (=4*63), the total number of rings, modulo 263, is R6*242 + R5*250. Since we already know R6 and we know this sum cannot be more than 263, we can solve for R5. We may continue this process by querying days 189 (=3*63), 126 (=2*63), 63 (=1*63) and 1 to determine R4, R3, R2 and R1, respectively.
Note that since we are querying six days and attempting to solve for six variables, we may choose to query (for example) days 1,2, ... , 6. This gives us a system of equations with six equations and six variables. Since these equations are linearly independent, we can solve this system, via Gaussian elimination for example, to get the solution.
The second test set requires another insight. We are only given two queries, so we must be able to solve for multiple Ri at once.
Let's think about what information we get by querying day 189 (=3*63). This gives R6*231 + R5*237 + R4*247, modulo 263. However, it is possible that there is some overlap between R6*231 and R5*237. For example, all other things being equal, we would not be able to differentiate between the case where R6=64 and R5=0 and the case where R6=0 and R5=1. Both of these would have 237 total rings.
We must use the fact that Ri ≤ 100. In order for the number of i-day rings to not interfere with the number of (i-1)-day rings on day d, we need 2floor(d/(i-1)) > 100 * 2floor(d/i) (note that this is equivalent to floor(d/(i-1)) ≥ floor(d/i)+7 since 27 > 100). If we ignore the modulo 263 restriction, then we could solve the question in a single query of (for example) 1000. This would give us
R1*21000 + R2*2500 + R3*2333 + R4*2250 + R5*2200 + R6*2166.
Since Ri ≤ 100, we coud determine R6 by
taking this value modulo 2200 to get
R6*2166, then by dividing by 2166.
We then could iteratively determine R5, R4, ...,
R1. However, this idea does not work since the problem is
modulo 263. There is no single query that can
give us all of the information we need, modulo 263.
We will use one query to determine the values of R4, R5, and R6, followed by a second query to determine the values of R1, R2, and R3. We saw above that a query of 189 (=3*63) will not work. However, a query of (for example) 200 will work:
R4*250 + R5*240 + R6*233,
and then solve for each in the same way as for the 1000 case. We can
then make a second query of (for example) 56:
R1*256 + R2*228 + R3*218 + R4*214 + R5*211 + R6*29.
We know the value of R4, R5, and R6
from the first step, so we may substitute those in and then solve
for R1, R2, and R3 one-by-one.
Note that the choice of 200 and 56 above were not the only possible options. In this problem, we could either guess-and-check for these values offline or (preferably) write a loop in the program to find two values that satisfy the criteria. We also need to ensure that the term with the largest exponent is not too large. For example, we cannot use a query of 250 in the first step since this gives R4*262 + R5*250 + R6*241, because the first term (R4*262) may be at least 263.
Let us call a pair (L, R) fair if choosing it produces a fair fight. Notice that since there are only 100 entries, there are at most 100*101/2 = 5050 possible intervals. For each interval, we may simply search for the maximum value is in each array via a linear search and check if those maximum values are close enough.
Notice the random choice of sword in case of ties does not change whether (L, R) is fair or not, so we can further assume that, if there are ties, they are broken by choosing the sword with smallest index. To simplify the write-up below, we assume that each Ci is distinct.
Let us consider a sub-problem: for each sword i that Charles can choose, how many fair intervals (L,R) are there which Charles chooses sword i? Let us call this value Fi. The answer to the original problem is simply the sum of the Fis. For each interval (L,R), there are three properties we are concerned with:
So we have Fi = (# of intervals that satisfy P1 and P2) - (# of intervals that satisfy P1 and P3). These two quantities are computed very similarly since they just have a different bound on the right-hand side of the inequality in P2 and P3. We explain below just how to compute (# of intervals that satisfy P1 and P2) and leave computing (# of intervals that satisfy P1 and P3) to the reader.
Note that if an interval (L,R) satisfies P2, then any subinterval of (L,R) also satisfies P2. Similarly, if (L,R) satisfies P1, then any subinterval of (L,R) that still contains i also satisfies P1. Thus, we are really only interested in how far left L can go with R=i (and how far right R can go with L=i). One option is to do a linear search for how far left L can go, but this is too slow. Instead, we binary search for how far away the left-endpoint is. A left-endpoint is too far left if P1 or P2 are no longer true. Otherwise, the left endpoint can be pushed further left. Once we know the furthest left L can go (let this index be Li) and the furthest right R can go (let this index be Ri), then (# of intervals that satisfy P1 and P2) = (i - Li + 1) × (Ri - i + 1). Calculating the maximum element in a range can be computed efficiently using a range minimum (maximum) query-type data structure in O(1) time per query, meaning O(log N) total time for the binary search.
In terms of time complexity, for each i, we need to perform 4 binary searches, which take O(log N) time each, for an overall O(N log N) total time. Setting up the range maximum query data structure takes an additional O(N log N) time, yielding an overall O(N log N) time for the full algorithm. There are solutions that can compute all of the required Li and Ri values (defined above) in O(N) total time by doing a couple of clever sweeps of the data to count the number of unfair intervals, but this was not needed for this problem.