This year, Round 1B jumped right into the Expogo problem, which had a pleasing deterministic solution. Blindfolded Bullseye was interactive and involved geometry; arriving at a correct algorithm probably required drawing some pictures and experimenting bravely! The card-shuffling Join the Ranks had a constructive solution, but one that wasn't easy to find, and a brute-force approach was too slow even for Test Set 1 without an insight.
This was a more time-consuming set of problems than Round 1A's set, and we didn't see our first perfect score until about an hour into the round. jiry_2 was in the lead for much of the first hour, and was the first to solve every problem, but mnbmvar swooped in with a penalty time of 1:04:30, and jiry_2's penalty time ended up being slightly larger, at 1:07:08. isaf27 came in third with 1:08:38, and then Marcin.Smulewicz and duality were not far behind in fourth and fifth. By the end of the contest, there were almost 90 perfect scores.
Once again, we had a five-digit number of contestants on the scoreboard. Tentatively, the advancement cutoff is 34 points plus a small enough penalty time. It wasn't quite enough to solve just Expogo! We saw quite a few pickups of the first Blindfolded Bullseye set; the first Join the Ranks set, on the other hand, was tougher to snag.
Round 1C is two weeks from now, so you will have some extra time to practice if that round will be your last chance to advance. Good luck, and next time you play darts, remember to flush your buffer between throws!
Cast
Expogo: Written by Ian Tullis. Prepared by John Dethridge.
Blindfolded Bullseye: Written and prepared by Pablo Heiber.
Join the Ranks: Written by Shik Chen and Pi-Hsun Shih. Prepared by Kevin Gu and Jonathan Irvin Gunawan.
Solutions and other problem preparation and review by Liang Bai, Darcy Best, Timothy Buzzelli, John Dethridge, Kevin Gu, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Andy Huang, Nafis Sadique, Pi-Hsun Shih, Kevin Tran, and Max Ward.
Analysis authors:
You have just received the best gift ever: an Expogo stick. You can stand on it and use it to make increasingly large jumps.
You are currently standing on point (0, 0) in your infinite two-dimensional backyard, and you are trying to reach a goal point (X, Y), with integer coordinates, in as few jumps as possible. You must land exactly on the goal point; it is not sufficient to pass over it on a jump.
Each time you use your Expogo stick to jump, you pick a cardinal direction: north, south, east, or west. The i-th jump with your Expogo stick moves you 2(i-1) units in the chosen direction, so your first jump takes you 1 unit, your second jump takes you 2 units, your third jump takes you 4 units, and so on.
Given a goal point (X, Y), determine whether it is possible to get there, and if so, demonstrate how to do it using as few jumps as possible.
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of a single line with two integers X and Y: the coordinates of the goal point.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is IMPOSSIBLE if the goal point cannot be reached. Otherwise,
y must be a string of one or more characters, each of which is
either N (north), S (south), E (east),
or W (west), representing the directions of the jumps that you
will make, in order. This sequence of jumps must reach the goal point at the
end of the final jump, and it must be as short as possible.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
(X, Y) ≠ (0, 0).
1 ≤ T ≤ 80.
-4 ≤ X ≤ 4.
-4 ≤ Y ≤ 4.
1 ≤ T ≤ 100.
-100 ≤ X ≤ 100.
-100 ≤ Y ≤ 100.
1 ≤ T ≤ 100.
-109 ≤ X ≤ 109.
-109 ≤ Y ≤ 109.
4 2 3 -2 -3 3 0 -1 1
Case #1: SEN Case #2: NWS Case #3: EE Case #4: IMPOSSIBLE
In Sample Case #1, you can jump south from (0, 0) to (0, -1), then jump east to (2, -1), then jump north to (2, 3).
We can be sure there is not a more efficient solution (two moves or fewer) because at least 2 + 3 = 5 units of distance are needed to reach the goal point, but the first two jumps combined only give us 3 units of distance.
Notice that Sample Case #2 is like Sample Case #1 but reflected across both axes, and so the answer comes from reflecting all directions in Sample Case #1's answer.
In Sample Case #3, notice that EWE would not be a valid answer,
even though it reaches the target, because there is a way to get there using
fewer jumps.
We leave it to you to determine why it is impossible to reach the target in Sample Case #4.
Gary has a large square wall that is exactly 2 × 109 nanometers tall and 2 × 109 nanometers wide. Gary has a dartboard placed on the wall. The dartboard is circular and its radius is between A and B nanometers, inclusive. The dartboard is fully contained within the wall, but it may touch its edges. The center of the dartboard is an integer number of nanometers from each edge of the wall.
Gary invited his friend Mika over to play an interesting game. Gary blindfolds Mika and challenges her to throw a dart at the center of the dartboard. To help her, whenever Mika throws a dart at the wall, Gary will tell her whether the dart hit the dartboard.
Mika does not know where on the wall the dartboard is, but since Mika is very skilled at darts, she can throw darts with nanometer precision. That is, she can aim and hit exactly any point that is an integer number of nanometers away from each edge of the wall. Immediately after throwing each dart, Gary tells her whether she hit the center of the dartboard, some other part of it, or missed it completely and hit the bare wall.
Can you help Mika hit the center of the dartboard, without throwing more than 300 darts?
Initially, your program should read a single line containing three integers T, A and B, indicating the number of test cases and the inclusive minimum and maximum values for the dartboard's radius, in nanometers, respectively. (Notice that A and B are the same for every test case within a test set.) Then, you need to process T test cases.
We represent the points that darts can be aimed at as pairs (x, y), where x and y are integers between -109 and 109, inclusive. The pair (x, y) is the point that is x + 109 nanometers away from the left edge of the wall and y + 109 nanometers away from the bottom edge of the wall. Point (0, 0) is therefore at the exact center of the wall.
For each test case, there is a secretly chosen radius R for the dartboard, and a secretly chosen center of the dartboard (X, Y). R, X, and Y are integers chosen for each test case by the judges in a designed (not random) way, within the limits. For each test case you need to process up to 300 exchanges with the judge. Your program represents Mika and the judge program represents Gary. Each exchange consists of Mika (your program) choosing where to throw a dart and Gary (the judging program) giving information about that position.
The i-th exchange consists of your program first outputting a single line containing two integers Xi and Yi, both between -109 and 109, inclusive, and the judge responding with a single line containing either:
CENTER if Xi = X and Yi = YHIT if 0 <
(X - Xi)2 + (Y - Yi)2 ≤ R2MISS in all other cases.
After sending CENTER, the judge will start waiting for the first
exchange of the next test case, if there is any.
If you output a line that is incorrectly formatted or with an out of bounds value,
the judge will respond with a single line containing WRONG.
If 300 exchanges occur (including 300 responses from the judge) without you receiving
CENTER, or if you ever receive WRONG, the judge will finish all
communication, wait for your own program to also finish, and give a Wrong Answer verdict.
After sending the T-th CENTER, on the other hand, the judge will finish all
communication, wait for your own program to finish, and give a Correct verdict.
If, while waiting for your program to finish, time or memory limits are exceeded,
the corresponding verdict will be assigned instead. (Note that verdicts are not messages
sent to your program.)
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 20.
A ≤ R ≤ B.
-109 + R ≤ X ≤ 109 - R.
-109 + R ≤ Y ≤ 109 - R.
A = B = 109 - 5.
A = B = 109 - 50.
A = 109 / 2.
B = 109.
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.
The interactive runner was changed after the 2020 Qualification Round. Be sure to download the latest version.
The following sample interaction uses the limits of Test Set 1.
// The following reads 20 into t and 999999995 into a and b. t, a, b = readline_int_list() // The judge secretly picks R = 999999995 (it had no choice) and X = -1, // Y = 3 (it did have a choice here). (Note: the actual Test Set 1 will // not necessarily use the values in this example.) // We try to throw at the upper left corner of the wall, and the dartboard // does not overlap with that point. printline -1000000000 1000000000 to stdout flush stdout r = readline_string() // reads MISS. // We try to throw at the center of the wall. That does hit the dartboard, // but not the center. printline 0 0 to stdout flush stdout r = readline_string() // reads HIT. // We make a super lucky choice and throw at the center of the dartboard. printline -1 3 to stdout flush stdout r = readline_string() // reads CENTER. // The judge begins the next test case. It secretly picks R = 999999995 // and X = 5, Y = 5. // We accidentally throw a dart out of the allowed range. printline -1234567890 1234567890 to stdout flush stdout r = readline_string() // reads WRONG. exit // exits to avoid an ambiguous TLE error.
You recently acquired a new deck of cards. Each card displays a rank, which is an integer between 1 and R, and a suit, which is an integer between 1 and S. For each combination of a rank and a suit, there is exactly one card that displays it, meaning that the deck has R × S cards in total. We will denote a card with rank r and suit s as (r, s).
Being brand new, the deck is sorted from top to bottom by suit in increasing order, with ties being broken by ranks in increasing order. That is, (1, 1) comes first, then (2, 1), ..., (R, 1), then (1, 2), (2, 2), ..., (R, 2), and so on up to (R, S). For example, with R = 4 ranks and S = 2 suits, the initial ordering would be: (1, 1), (2, 1), (3, 1), (4, 1), (1, 2), (2, 2), (3, 2), (4, 2).
You want to reorder the deck to be sorted by rank. That is, you want to put all the cards of the same rank together, and have the ranks be in increasing order. You do not care, however, about the order of the suits within each rank. For example, with R = 4 and S = 2, one of the various possible valid new orderings would be: (1, 2), (1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (4, 2), (4, 1).
You have been learning how to cook, so you want to reorder the deck without putting your spatulas down. You decided to sort the deck using only the following multi-part operation:
Notice that the operation exchanges the pile A part of the deck and the pile B part of the deck, without affecting any other cards deeper in the deck (if there are any).
Continuing with our R = 4, S = 2 example, if your first move is
to choose 3 cards from the top for pile A and 2 cards for pile B, then these
are the cards you get:
A: (1, 1), (2, 1), (3, 1),
B: (4, 1), (1, 2), and
Remainder of deck: (2, 2), (3, 2), (4, 2).
After putting A on the deck and then B on top of that, the new deck is
ordered like this:
(4, 1), (1, 2), (1, 1), (2, 1), (3, 1), (2, 2), (3, 2), (4, 2).
Given R and S, find a sequence of operations that reorders the deck to be sorted by rank, as described above, and uses the minimum possible number of operations to do so.
The first line of the input gives the number of test cases, T. T lines follow. Each of these lines describes a single test case with two integers R and S, the number of ranks and suits in the deck, respectively.
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 minimum number of operations needed to reorder the deck
as explained above. Then, print y more lines containing
ai bi, meaning that in the i-th operation
in a sequence of moves that reorders the deck, you take
ai cards first to form pile A and then
bi cards after that to form pile B.
Memory limit: 1GB.
Time limit: 30 seconds.
T = 12.
2 ≤ R ≤ 5.
2 ≤ S ≤ 7.
R × S ≤ 14.
Time limit: 60 seconds.
1 ≤ T ≤ 100.
2 ≤ R ≤ 40.
2 ≤ S ≤ 40.
3 2 2 3 2 2 3
Case #1: 1 2 1 Case #2: 2 3 2 2 1 Case #3: 2 2 3 2 2
In Sample Case #1, the initial order is
In Sample Case #2, the initial order is
In Sample Case #3, another valid solution is a1 = 4,
b1 = 1 first, and then a2 = 3
and b2 = 1.
Test Set 1 is small enough to solve by hand. We can speed this up with a couple of observations:
EEN is a solution for (3, 4), then we also
know that WWS is a solution for (-3, -4), and EES
is a solution for (3, -4), and so on. Because of all the horizontal,
vertical, and diagonal symmetry, there are really only six fundamentally
different cases!Based on the observations above, we may think to try a breadth-first search of all possible jumping paths, and continue until every "odd" (X, Y) position (with -100 ≤ X ≤ 100 and -100 ≤ Y ≤ 100) has been reached. It turns out that each such position is reachable in no more than 8 moves. We know that these solutions are optimally short because of the breadth-first nature of the search.
Suppose that (X, Y) = (7, 10). In what direction should we make our initial 1-unit jump? As we saw above, we need our final X coordinate to be odd, but it is currently even, and we have only one chance to go from even to odd. Moving north or south will make our Y coordinate odd, but then we will never have another chance to make that even and the X coordinate odd. So we should either move west or east. For now, let's guess that we will go west; we will revisit the other possibility later.
That jump will take us to (-1, 0), and we will next need to make a 2-unit jump. Notice that we can make this look identical to the original problem setup, if we make two changes:
With this in mind, let's revisit our original decision to jump to the west. If we had jumped east instead, we would have ended up at (1, 0), and if we had changed the problem in the same way we did above, our new goal would have been (3, 5). But that would be an "even" position (after rescaling), which cannot be reached! So we had no choice after all; we had to move west to be able to eventually reach the goal. It's a good thing we were so lucky!
So now the problem has "reset", and we are at (0, 0) and trying to get to
(4, 5). In what direction should we make our "first" jump? Now we know we
must move vertically, since 5 is odd and we will only have "one chance" to
go from even to odd. If we jump north, the next rescaling will have a target
of (2, 2), but if we jump south, the target will be (2, 3), which is the
"odd" position that we want. From there, we should jump south to change the
target to (1, 2), then east to change the target to (0, 1). At that point,
we have a choice between jumping north and reaching the goal, and jumping
south (which could still allow us to reach the goal after some further moves,
e.g. one more to the south and then one more to the north). But the problem
requires that we choose the shortest solution, so we should jump right to
the goal! Therefore, the answer in this case is WSSEN.
Notice that this method is deterministic: we always have only one choice out of the four possible directions. We can rule out two of them because they will not make the correct coordinate odd. Of the other two, the new goal states they would leave us with must differ only in one of the coordinates and only by exactly 1 unit, and therefore one must be an "odd" position and the other must be an "even" position. It is possible that that "even" position is the goal, in which case we should jump there, but otherwise, we must choose the "odd" position.
The above analysis also shows that the only time we have a choice is when one of those options is to jump directly to the goal, in which case we obviously should. So we can be confident that our method produces the shortest possible solution. (We also know that that solution is unique, since if we were to choose to not jump directly to the goal when we had that option, we would only end up with a longer solution.)
Our method has a running time which is logarithmic in the magnitudes of the coordinates, so it will solve this test set blazingly fast!
This problem is a riff on the Pogo problem from Round 1C in 2013. If you were familiar with that problem, the analysis might have helped a bit with this one... but, like a well-designed pogo stick, Expogo is not too difficult to get a handle on anyway.
In Test Set 1 the radius is both really large and known in advance. The fact that it is large gives
us a major restriction: plugging in the value for R in the limits for X and Y shows that the hidden
center is restricted to a square with side length 10 nanometers, centered on the origin. That means
that there are only 112 = 121 possible positions for the center! We can simply try
throwing a dart at each of them, stopping as soon as we are told that we have hit the
CENTER.
In Test Set 2 the radius is also large and known, but small enough that the square of candidate center points has side 101 nanometers. This means that there are 10201 possible centers, which is a lot more than the number of darts we get. We need to restrict that further.
We can use the fact that we know the exact radius to reduce this number. Every dart we throw can give us a clue. If a dart thrown at point p hits, that means the the distance between p and the center c is no more than R. If a dart thrown at point q misses, that means that the distance between q and c is more than R. If we find two points p and q that are close to each other, the points that are no more than R away from p but more than R away from q form a narrow crescent-shaped region of width equal to the distance between p and q. Intersecting that with the original square of possibilities from the first paragraph can give us a small enough range for c that we can just throw a dart at each possibility without running out of darts.
We can find points p and q that are close to each other by finding the edge of the dartboard. Since the dartboard is so large, the edge has to be close to the edge of the wall. If we inspect points (x, 0) for the possible values of x, most points are guaranteed to be inside the dartboard: any point (x, 0) with -109 + 101 ≤ x ≤ 109 - 101 is no more than R away from all possible centers, and is thus guaranteed to be inside the circle. Therefore, we can try all possible x on any one side of that guaranteed interval to find a hit point and a miss point that are 1 nanometer away from each other. Since there are only 101 points on each side that are not guaranteed to be in the circle — for example [-109, -109 + 100] — this requires at most 101 darts.
After finding those points, we know that the center has to be inside a narrow crescent-shaped band of width 1. Intersecting that with the 101-by-101 square of candidates leaves at most 202 candidates, since there can't be more than 2 candidates that share an x value. Moreover, for most x values, the rounding ensures that there are less than 2, so the 199 darts we have left are enough to cover all candidates.
Notice that no complicated geometry is involved to find the candidates; the square is small enough to iterate over all points within it and check the distances to our hit and miss points to see if they are candidates or not.
For Test Set 3, we can take a more typical geometric approach. To find the center of a circle, we can find 3 points on the edge of the circle, and then calculate a center from those. This has an issue: we only have nanometer precision, which means we would typically find points near the edge of the circle, but not exactly in it. The error that this introduces in our calculations could be significant. We can overcome this by bounding the error and then checking not only our calculated center, but also other nearby points too. The math to calculate the center, and most importantly, to bound the error of it, can be hard and time consuming, but it is doable. In addition, you can wing it by not bounding the error and instead starting to throw at your calculated center and then spiral around it on nearby points until you find the actual center. This requires a leap of faith that you won't run out of tries, but it's a reasonable assumption. Fortunately, there is a simpler related approach that is more clearly correct, that we describe below. Of course, we still need to solve the problem of finding "almost-edge" points of the circle, which we also need for our simpler approach.
To find a point in the edge, we can't use the approach in Test Set 1, because if the dartboard's radius is not very large, those points could be really far away from the wall's edge. A different way of doing it is via a binary search. Say we know that point (x0, y0) is within the dartboard. Then, we know that for all x in the range [-109, x0] the points (x, y0) are grouped such that there is a (possibly empty) interval having all misses, and then an interval having all hits. The same holds (in reverse) for [x0, 109]. Analogously, points (x0, y) for y in [-109, y0] or [y0, 109] are grouped by hits/misses. Then, for each of those ranges, we can do a binary search to find the switching point — that is, a point in the edge of the circle. This is exactly what we did in Test Set 2, except we fixed x0 = 0, because the radius is so large that some points like (0, 0) are guaranteed to be inside the dartboard, and the range is small enough that we can scan it entirely instead of using binary search.
The searches above get us leftmost and rightmost points inside the dartboard for a given y-coordinate y0, and topmost and bottommost points for a given x-coordinate x0. Notice that the dartboard is symmetric with respect to the horizontal and vertical lines that go through its center. Therefore, the leftmost and rightmost points inside the dartboard in any fixed y-coordinate mirror each other, and the x-coordinate of the center is the midpoint between their x-coordinates. Similarly, we can find the y-coordinate of the center as the midpoint between the y-coordinates of the topmost and bottommost points inside the dartboard at any fixed x-coordinate.
The remaining task is to find a single point inside the dartboard. Since the area of the dartboard makes up a significant percentage of the wall area (at least π / 16), we could do this by throwing darts at random until we hit one point (the probability of hitting could be slightly less than π / 16 because we consider only points with integer nanometer coordinates, but the difference is negligible). This has an overwhelmingly high chance of hitting in 100 throws or fewer for all cases. However, there is a deterministic way that also works, which is to divide the wall into squares of side A. If the center of the dartboard is inside a square, it is guaranteed that at least one of the corners of that square is inside the dartboard. Therefore, we can simply try all those corners (there are only 25, and it is even possible to restrict it further), and we will find a hit point.
So, we need a fixed small number of darts (up to 100, depending on our method of choice) to find a point inside the dartboard, and each binary search needs at most 31 = ceil(log2 (2 × 109 + 1)). That is at most 4 × 31 + 100, which is a lot less than the 300 limit. In the first version, you need one fewer binary search — 3 edge points are enough to find a unique center — so after finding the center with error, you could have 150 darts left to explore its vicinity. Notice that if your initial point is actually one of the points (X - R, Y), (X + R, Y), (X, Y - R) or (X, Y + R), you would end up with two points instead of three and be unable to find the center. If we use the random procedure to find (x0, y0), the probability of this happening is negligible. Otherwise, we can detect the case and know that the two found points are opposite each other, so the center is their middle point.
Test set 1 contains the 12 possible inputs allowed by the limits. We can try to solve the problem via a breadth-first search (BFS), on the graph of states, where a state is the current arrangement of cards in the deck. Notice, however, that cases with 14 total cards would yield an enormous graph and make the solution run too slowly — probably even too slowly for us to run the code locally to precompute answers that we can then hardcode!
However, one observation will help us: since the success condition does not involve the suits of the cards at all, we can ignore them and work only with the ranks. That dramatically cuts down the number of possible states, by going from (R × S)! to (R × S)! / ((S!)R). This allows a BFS to finish fast enough for this test set. We can also use this observation while solving the next test set...
For test set 2, the worst case (R=40, S=40) has around 1.8 x 102517 unique orderings. This means that the brute force solution will not work.
Our first important observation is that the reordering operation can decrease the number of adjacent cards of different ranks by at most two. In the starting configuration there are (R × S)-1 adjacent cards of different ranks. In the ending configuration there are R-1 adjacent cards of different ranks. So to get from (R × S)-1 to R-1 we need at least ceil((R × S - R) / 2) operations.
Now that we know ceil((R × S - R) / 2) is a lower bound on the answer, if we can come up with a method that is guaranteed to use no more than ceil((R × S - R) / 2) steps, then it will always produce a valid answer.
Now we will outline a way to sort the cards using exactly that many operations. The invariant we maintain is that at all times, for the ranks X and Y of any two consecutive cards, either Y = X, or Y = (X + 1) mod R. This is of course true for the initial ordering of the deck.
We repeatedly perform the following operation, as long as the number of adjacent pairs of cards of the same rank is less than R - 1 and the operation would not pick up the bottom card of the deck: find the largest block of consecutive cards from the top that contains exactly 2 different ranks to use as pile A. By the invariant, this will be one or more cards with rank X, followed by one or more cards with rank (X+1) mod R. Then, starting from the first card from the top that is not on pile A, take as pile B the largest block of consecutive cards that does not contain any cards of rank X, plus all consecutive cards of rank X that immediately follow that block. Notice that at least one such card of rank X must exist; otherwise, by the invariant, the number of adjacent pairs of cards of different ranks would already be R-1.
We can show that this operation reduces the number of adjacent cards of different ranks by 2 every time it does not pick up the bottom card of the deck. To show this, notice that the bottom of pile B is a card of rank X and the first card left over in the deck is, by the invariant, (X + 1) mod R. That means that the new adjacent pairs are two cards of rank X (the bottom of pile B and the top of pile A) and two cards of rank (X + 1) mod R (the bottom of pile A and the top of the leftover deck). The broken adjacent pairs are — by definition of piles A and B — both of cards of different rank. Therefore, the number of adjacent pairs of cards of different rank decreases by 2 with this operation.
Suppose that performing the operation would pick up the bottom card of the deck. That means that all cards of rank X are in two contiguous blocks at the top and bottom of the deck before the operation is performed. In addition, since this is the first time the bottom card of the deck is picked up for an operation, X = R. Because of the invariant, that requires every other rank to be in a single contiguous block. In this ordering, there are exactly R adjacent pairs of cards with different ranks. Instead of the operation above, we finish by making pile A consist of the largest block of consecutive cards of rank R, starting at the top, and pile B be the rest of the deck. After performing the operation, R - 1 pairs of adjacent cards of different ranks remain (by a similar argument as before, ignoring the broken and created pairs that involved the leftover deck, since there is none leftover) and the final card of the deck is still R.
After performing the repeated operation floor((R × S - R) / 2) times, the number of adjacent pairs of cards of the same rank decreases to R - 1 if R × S - R is even or R if it's odd. Notice that the number remains greater than R before each such operation, so we would never have picked up the bottom card of the deck. In the even case, the number of adjacent pairs of cards of the same rank is now minimum and we never picked up the bottom card of the deck, so we are at exactly the target ordering. In the odd case, we arrive at the case in which we do pick up the bottom card of the deck with our last operation, but as argued above, that operation also leaves the deck in the target order.