The 2019 Finals presented a full complement of six challenges. Board Meeting was our now-customary interactive Finals problem; it was not as tough as last year's , but it still required some careful thought about which board positions to check. Sorting Permutation Unit presented another design challenge — which permutations would work most efficiently and most generally? — but in a non-interactive format. Won't Sum? Must Now entailed building numbers out of a small number of palindromes, thanks to a mathematically beautiful guarantee.
Moving on to the back half of the set, the two Juggle Struggle problems were a pair like the New Elements problems from this year's Round 2, and these two were even more closely related! Part 2 in particular featured a test set 1 that was quite straightforward, but just getting below O(N2) to O(N log N) proved to be one of the toughest hurdles in this year's problem set! Finally, Go To Considered Helpful required our contestants to find the shortest program to get through a maze; it was not too hard to see that breadth-first searches were needed, but the details were as treacherous as the obstacles that our fish friend had to avoid.
At first, our solvers fanned out and worked on different problems. ecnerwala went right for the most valuable problem, and solved it just over an hour into the contest. Other contestants chipped away at the (relatively) easier 27-point problems. At the halfway point, every problem except for Juggle Struggle: Part 2 had been fully solved by someone, but the judges knew that only ecnerwala and Radewoosh had two full solves; xiaowuc1 had an impressive four test set 1 solves, but not the 124 points displayed on the optimistic scoreboard.
By the final hour, every problem had been solved (always a goal of the Code Jam problem setters!), and several contestants vied fiercely for the top triple-digit score, struggling with the age-old Code Jam dilemma: solve more test set 1s to rack up potentially tiebreaking points, or go for a big step with a test set 2? The lead changed several times, and by the end of the contest, we had some huge numbetrs on the board, but how many of those test set 2 solves were real?
When the true results were laid bare, the various ultra-high scores melted away, but there were some impressive results underneath! The judges' room was hanging on every scoreboard change in the last 15 minutes. For a while, it looked as if Gennady.Korotkevich didn't have enough time to solve a full problem to reclaim the lead, but he pulled it off, sealing his win with 143 points. rng..58 and ecnerwala were behind by a test set 2 (and time), at 121 points. mnbvmar took a close fourth with 118, and Radewoosh had the other triple-digit score at 103.
Goodbye for now, San Francisco! That's one more Code Jam season in the books, and we already can't wait for the next one! (And one more gold medal for Gennady.Korotkevich!) Congratulations to all of our finalists and T-shirt winners, and to everyone who had just the right flash of insight needed to solve that tricky problem that had seemed intractable only a few minutes earlier. We hope to see all of you — and more — back here in 2020!
Cast
Sorting Permutation Unit: Written by Kevin Tran. Prepared by Jonathan Irvin Gunawan and Trung Thanh Nguyen.
Board Meeting: Written and prepared by Petr Mitrichev.
Won't Sum? Must Now: Written by Igor Naverniouk. Prepared by Darcy Best, Igor Naverniouk, and Ian Tullis.
Go To Considered Helpful: Written by David Arthur. Prepared by John Dethridge.
Juggle Struggle (Parts 1 & 2): Written by Pablo Heiber. Prepared by Timothy Buzzelli and Pablo Heiber.
Solutions and other problem preparation and review by Darcy Best, Timothy Buzzelli, Shane Carr, John Dethridge, Natalia Giraud, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Yuta Kitamura, Petr Mitrichev, Igor Naverniouk, Trung Thanh Nguyen, Ray Robinson, Pi-Hsun Shih, Kevin Wang, and Peter Whalan.
Analysis authors:
Note that it is not necessary to know anything about the rules of chess to solve this problem.
There are N kings on an infinite chessboard (two-dimensional grid), located in cells with coordinates (X1, Y1), (X2, Y2), ..., (XN, YN). Both N and the kings' coordinates are unknown to you. However, you do know the following things:
The kings want to meet in a single cell of the board. If some cell (X, Y) were to be chosen as the meeting cell, then in order to get there, the i-th king would use a number of moves equal to the maximum of the absolute values of the differences of coordinates between its cell and the meeting cell: max(|X-Xi|,|Y-Yi|). The total number of moves used by all kings is thus equal to the sum of those maximums over all values of i. Note that it is not relevant to this problem exactly how the kings move on the board — only the source and destination cells matter, and the number of moves can always be computed using the above formula.
This problem has two phases. In the first phase, you may repeatedly do the following: propose a meeting location (A, B) (with each of A and B between -10×M and 10×M, inclusive), and have the judge tell you the total number of moves the kings would use to get there — the sum (over all i) of max(|Xi-A|,|Yi-B|). You can have at most R such exchanges with the judge, choosing your values of A and B each time. Note that the kings do not actually move, so their locations (Xi, Yi) stay the same for all requests within one test case.
In the second phase, the roles are swapped: the judge gives you a meeting cell location (C, D) (with each of C and D between -10×M and 10×M, inclusive), and you must respond with the total number of moves the kings would use to get there, assuming that the kings are in the same locations as in the first phase. There are at most R such exchanges, and you must correctly respond to all of the judge's requests.
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 four integers T, Nmax, M and R: the number of test cases, the maximum number of kings, the maximum absolute value for any coordinate for any king, and the maximum number of requests per phase, respectively. (Note that the values of M and R are fixed, and are provided as input only for convenience; see the Limits section for more details.) Then, you need to process T test cases.
In each test case, there are two phases. In the first phase, the i-th exchange is as follows:
You may initiate at most R such exchanges in this phase. If you make
more than R exchanges, or send a request that the judge can not parse
or is out of bounds, the judge responds with one line with a single string
ERROR.
To end the first phase and switch to the second phase, you must send one line
with the string READY (the case does not matter), to which the
judge responds with the first request of the second phase.
In the second phase, the i-th exchange is as follows:
The judge is guaranteed to send at least 1 and at most R such
requests. If you send an answer that is incorrect or unparseable, the judge
responds with ERROR as described above. If you answer all of the
requests correctly, the judge sends one line with a single string
DONE, at which point your program should initiate the next
test case, or terminate with no error if all T test cases have been
handled.
After the judge sends a line with ERROR, it does not send any
other output. If your program continues to wait for the judge after receiving
ERROR, 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.
The number and location of the kings, as well as the number and positions of the requests that the judge sends during the second phases, are chosen before any exchanges occur.
Time limit: 60 seconds per test set.
Note that a program that just makes valid exchanges with the judge (and
does no other processing) takes the following time in our environment:
~13 seconds for C++, ~24 seconds for Java, ~19 seconds
for Python and Go.
Memory limit: 1GB.
1 ≤ T ≤ 15.
M = 106.
-M ≤ Xi ≤ M, for all i.
-M ≤ Yi ≤ M, for all i.
The pairs (Xi, Yi) are distinct.
-10×M ≤ Ci ≤ 10×M,
for all i.
-10×M ≤ Di ≤ 10×M,
for all i.
R = 1000.
Nmax = 1.
Nmax = 10.
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.
Note that the following sample interaction is for test set 1, in which there is always exactly one king.
// Suppose that the judge has decided that in the first test case, the king // is at the coordinates (1, -2), and the requests will be (5, -1) and // (7, 7). t, nmax, m, r = readline_int_list() // Reads 10 1 1000000 1000 // Our solution decides (for whatever reason) to check (3, 3) first. printline 3 3 to stdout flush stdout result = readline_int() // Reads 5 // Our solution now decides (for whatever reason) to check (2, 0). printline 2 0 to stdout flush stdout result = readline_int() // Reads 2 // Our solution concludes that the king is at (3, -2), which is consistent // with the observed information so far, but unfortunately not correct. // Our solution moves on to the request phase. printline READY to stdout request_line = readline() // Reads 5 -1 printline 2 to stdout // Wrong answer! request_line = readline() // Reads ERROR exit // exits to avoid an ambiguous TLE error
You may have heard of Google's Tensor Processing Units, which are used to build neural networks. However, there is one research area that is even deeper and more important than machine learning: sorting!
We are working on a special new chip called the Sorting Permutation Unit, which is very fast at applying permutations to arrays of integers. Formally, a permutation is an ordering of the first n positive integers
p1, p2, ..., pn
and applying it to an array of n integers
a1, a2, ..., an
yields the new array
ap1, ap2, ..., apn.
For example, applying the permutation 3, 1, 2, 4 to the array 99, 234, 45, 800 would yield the new array 45, 99, 234, 800.
However, permutations are expensive to represent in the hardware, so the unit can only have access to at most P distinct permutations. We need your help figuring out what those permutations should be!
Given K arrays of N integers each, you must first specify up to P permutations (of size N) of your choice. Then, for each of those K input arrays, you must provide one sequence of up to S instructions (each of which is a permutation from your specified set). When the instructions in this sequence are applied, in the given order, to the array, they must yield an array sorted in nondecreasing order. In each of your K sequences of instructions, you may use each of your P permutations zero or more times (not necessarily consecutively).
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with four integers P, S, K, and N: the maximum number of permutations allowed, the maximum number of instructions you are allowed to use to sort each array, the number of arrays, and the number of integers in each array. Then, there are K more lines of N integers Ai1, Ai2, .., AiN each, where the j-th integer on the i-th line, Aij, represents the j-th value of the i-th array.
For each test case, first output the following, in this order:
Case #x:, where x is the
test case number (starting from 1).pij is the j-th element of the i-th
permutation.Then, output K more lines. The i-th of these gives the instructions that you will apply to the i-th array given in the input. Each such line must begin with one integer S', where 0 ≤ S' ≤ S, and must continue with S' integers X1, X2, ..., XS', where 1 ≤ Xk ≤ P' for all k. Here, Xk represents that the k-th instruction you apply to the i-th array is the Xk-th permutation (counting starting from 1) in your list of permutations. These instructions must yield an array with the elements of the i-th input array, sorted in nondecreasing order.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 10.
S = 450.
1 ≤ K ≤ 30.
2 ≤ N ≤ 50.
1 ≤ Aij ≤ 1000, for all i and j.
P = 20.
P = 5.
2 20 450 4 3 10 10 11 17 4 1000 999 998 997 10 10 11 20 450 5 5 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4
Case #1: 2 3 1 2 2 1 3 0 1 2 2 2 1 1 2 Case #2: 1 5 1 2 3 4 0 1 1 2 1 1 3 1 1 1 4 1 1 1 1
In Sample Case #1, we can define up to P = 20 permutations. One viable strategy uses only these two:
We can handle the four arrays as follows:
10 10 11: This is already sorted in nondecreasing order, so
we do not need to do anything.17 4 1000: We can apply permutation #2 to yield
4 17 1000.999 998 997: One option is to first apply permutation #2 to
turn the array into 998 999 997, then apply permutation #1 to turn the array
into 997 998 999.10 10 11: This is the same as the first array. Applying
permutation #2 also yields array sorted in nondecreasing order. (But we
could have used the line 0 as we did before.)In Sample Case #2, notice that we can use the same permutation instruction more than once on the same array, if desired.
In 2016, it was shown that every positive integer can be written as the sum of three or fewer palindromic terms. For the purposes of this problem, a palindromic term is a string of digits (with no leading zeroes) that represents a positive integer and reads the same forward and backward.
Given a positive integer S, find K palindromic terms that sum to S, such that K is minimized.
The first line of input gives the number of test cases, T. T lines follow, each containing a positive integer S.
For each test case, output one line of the form
Case #x: A1 (if only one term is needed),
Case #x: A1 A2
(if only two terms are needed), or
Case #x: A1 A2 A3
(if three terms are needed), where
x is the case number (counting starting from 1), each
Ai is a palindromic term (as described above), and the sum of the
Ais equals S.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ S ≤ 1010.
1 ≤ S ≤ 1040.
3 1 198 1234567890
Case #1: 1 Case #2: 191 7 Case #3: 672787276 94449 561686165
In Sample Case #1, the input is already a palindrome.
In Sample Case #2, note that 99 99, for example, would also be
an acceptable answer. Even though there are multiple instances of
99, they count as separate terms, so this solution uses the same
number of terms as 191 7.
Also note that 191 07, 181 8 9,
0110 88, 101 97, 7.0 191.0,
and -202 4, for example, would not be acceptable answers.
The first two paragraphs (not counting this one) of this problem and "Juggle Struggle: Part 2" are identical. The problems can otherwise be solved independently; you do not need to read or solve one in order to read or solve the other.
As manager of the Graceful Chainsaw Jugglers group, you have decided to spice the show up a bit. Instead of having each juggler individually juggle their own chainsaws, you want them to form pairs, with each pair throwing the chainsaws back and forth to each other. In this new performance, 2 × N jugglers will be on stage at the same time, arranged into N pairs, with each juggler belonging to exactly one pair.
You think the show will be more impressive if the chainsaws being juggled by different pairs of jugglers are at risk of collision. Let the stage be a two-dimensional plane, and let the straight line segment in that plane that connects the positions of two jugglers in a pair be called the pair's juggling path. When two juggling paths instersect, we say the chainsaws juggled by those pairs are at risk of collision. We call the spatial positions and the pairings of the jugglers an arrangement. An arrangement is magnificent if every two pairs of jugglers' chainsaws are at risk of collision.
After a lot of thinking and designing, you came up with a magnificent arrangement. You wrote down the positions of the jugglers on the stage and the pairings of the jugglers on a piece of paper. Unfortunately, a bad chainsaw throw cut the paper in half, and you have lost the half with the pairings. Since the stage decorations have already been designed based on the positions of the jugglers, those positions cannot be changed. The show's highly anticipated debut is a mere few hours away, so you need to find a magnificent arrangement that works! Given every juggler's position on a two-dimensional stage, find a pairing of them that yields a magnificent arrangement.
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 a single integer N, the number of pairs of jugglers. Then, 2 × N lines follow. The i-th of these lines contains two integers Xi and Yi, representing the coordinates of the position of the i-th juggler.
For each test case, output one line containing
Case #x: j1 j2 ... j2 × N, representing
that jugglers i and ji are to be paired together, for every i.
Notice that jji = i for every i.
Memory limit: 1GB.
-109 ≤ Xi ≤ 109, for all i.
-109 ≤ Yi ≤ 109, for all i.
No three juggler positions are collinear. (Note that this also implies that no two jugglers are in
the same position.)
There exists at least one way to pair the jugglers such that the resulting arrangement
is magnificent.
Time limit: 20 seconds.
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
Time limit: 60 seconds.
1 ≤ T ≤ 10.
2 ≤ N ≤ 105.
3 2 -1 -1 -1 1 1 1 1 -1 3 1 2 2 1 2 3 3 1 3 3 4 2 3 7 1 1 1 7 2 5 5 3 5 1 2
Case #1: 3 4 1 2 Case #2: 6 5 4 3 2 1 Case #3: 5 4 6 2 1 3
In Sample Case #1, the jugglers' positions form a square. The only valid solution is to pair up jugglers 1 and 3, and pair up jugglers 2 and 4.
The first two paragraphs (not counting this one) of this problem and "Juggle Struggle: Part 1" are identical. The problems can otherwise be solved independently; you do not need to read or solve one in order to read or solve the other.
As manager of the Graceful Chainsaw Jugglers group, you have decided to spice the show up a bit. Instead of having each juggler individually juggle their own chainsaws, you want them to form pairs, with each pair throwing the chainsaws back and forth to each other. In this new performance, 2 × N jugglers will be on stage at the same time, arranged into N pairs, with each juggler belonging to exactly one pair.
You think the show will be more impressive if the chainsaws being juggled by different pairs of jugglers are at risk of collision. Let the stage be a two-dimensional plane, and let the straight line segment in that plane that connects the positions of two jugglers in a pair be called the pair's juggling path. When two juggling paths instersect, we say the chainsaws juggled by those pairs are at risk of collision. We call the spatial positions and the pairings of the jugglers an arrangement. An arrangement is magnificent if every two pairs of jugglers' chainsaws are at risk of collision. That is, for the arrangement to be magnificent, each of the N juggling path segments must intersect each of the other N-1 juggling path segments (but these intersections do not necessarily all have to be in the same place).
After some last minute fixes, you have what you think is a magnificent arrangement. Given the rush to put it together, you want to write a checker that can determine whether it is indeed magnificent. If it is not, then at most 25 juggler pairs fail to intersect every other pair. You want your checker to report a list of all those juggler pairs for inspection.
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 a single integer N, the number of pairs of jugglers. Then, N lines follow. The i-th of these lines contains four integers Xi, Yi, X'i, Y'i. (Xi, Yi) and (X'i, Y'i) are the coordinates of the positions of the two jugglers comprising the i-th juggler pair.
For each test case, output one line containing
Case #x: y, where y is uppercase MAGNIFICENT if the input
represents a magnificent arrangement. Otherwise, y should be a strictly increasing
list of integers. Integer i should be on that list if and only if the juggling path
of the i-th juggler pair fails to intersect at least one other juggling path.
Memory limit: 1GB.
-109 ≤ Xi ≤ 109, for all i.
-109 ≤ Yi ≤ 109, for all i.
-109 ≤ X'i ≤ 109, for all i.
-109 ≤ Y'i ≤ 109, for all i.
No three juggler positions are collinear. (Note that this also implies that no two jugglers
are in the same position.)
For all but up to 25 pairs of jugglers, their juggling paths intersect all N - 1 other
juggling paths.
Note: There may or may not exist a way to pair the jugglers such that
the resulting arrangement is magnificent.
Time limit: 20 seconds.
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
Time limit: 45 seconds.
1 ≤ T ≤ 13.
2 ≤ N ≤ 105.
4 2 -1 -1 -1 1 1 1 1 -1 2 -1 -1 1 1 -1 1 1 -1 4 1 2 4 2 2 1 3 1 2 4 3 0 3 3 2 3 3 1 1 2 2 3 7 4 8 8 3 9 3
Case #1: 1 2 Case #2: MAGNIFICENT Case #3: 1 2 4 Case #4: 1 2 3
In Sample Case #1, there are only two pairs, and their paths do not cross.
In Sample Case #2, the arrangement is magnificent: every pair's path crosses every other pair's path.
In Sample Case #3, only pair 3's path crosses every other pair's path.
Marlin is a fish who lost his son and is trying to find him. Fortunately, he ran into Cynthia, a turtle, as she swam around with her brothers, Wally and Seymour. Cynthia knows exactly where Marlin needs to go, and she can be very precise in giving directions. While Marlin is smart and can follow them perfectly, keeping track of a long list of directions can be problematic. Cynthia needs to find a way to make the list of directions short.
Marlin lives in a matrix of R rows and C columns. Some cells of the matrix are dangerous and cannot be entered. Marlin and his son are currently in different non-dangerous cells. Marlin's son never moves to a different cell. Cynthia decided to give Marlin directions in the form of a program consisting of a list of instructions, each on a single line. Each instruction is of one of 5 types:
N: move one cell North (up),S: move one cell South (down),W: move one cell West (left),E: move one cell East (right), andG(i): jump to the i-th line of the instruction list
(counting starting from 1).After executing a line with any of the first 4 instructions, Marlin jumps to the next line on the list if there is one. If there is no next line, Marlin just stands still forever.
For example, if Marlin were following the program
1: N 2: E 3: G(6) 4: S 5: G(1) 6: W 7: G(4)
he would move North (line 1), then East (2), then jump to line 6 without physically moving (3), then move West (6), then jump to line 4 (7), then move South (4), then jump to line 1 (5), then move North (1), etc.
If at any point Marlin and his son are at the same cell, they will be reunited
and Marlin will no longer follow any instructions. Cynthia the turtle wants to find out the
smallest number of lines in a program that would get Marlin to the same cell as his
son, without him ever going into a dangerous cell or moving outside of the matrix
boundaries. All G instructions must jump to existing lines in the program.
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with a line containing R and C, the number of
rows and columns in the matrix. Then, R lines follow containing a string of
C characters each. The j-th character of the i-th of these lines Aij
represents the cell in the i-th row and j-th column of the matrix. The character is #
if the cell is dangerous, an uppercase M if the cell is the one Marlin is currently
at, an uppercase N if the cell is the one Marlin's son is currently
at and . if the cell is an unoccupied non-dangerous cell.
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 there is no program that would get Marlin to his son
under the conditions explained above, or the smallest number of instructions in such a
program.
Memory limit: 1GB.
1 ≤ T ≤ 100.
Aij is either #, ., uppercase M
or uppercase N, for all i and j.
Aij = M for exactly one pair of i and j.
Aij = N for exactly one pair of i and j.
Time limit: 30 seconds.
1 ≤ R ≤ 10.
1 ≤ C ≤ 10.
Time limit: 120 seconds.
For at most 10 test cases:
1 ≤ R ≤ 100.
1 ≤ C ≤ 100.
For the remaining test cases:
1 ≤ R ≤ 50.
1 ≤ C ≤ 50.
5 2 5 N...# ....M 2 5 N#... ...#M 5 5 N..## #.### #...# ##.## ##..M 5 5 ..N## #.### #...# ##.## ##..M 3 3 #M# ### #N#
Case #1: 4 Case #2: 7 Case #3: 5 Case #4: 6 Case #5: IMPOSSIBLE
Below are some shortest programs for each of the possible sample case.
1: W
2: N
3: S
4: G(1)
or
1: W
2: N
3: W
4: G(3)
.
1: N
2: W
3: W
4: S
5: W
6: W
7: N
.
1: W
2: W
3: N
4: N
5: G(2)
.
1: W
2: W
3: N
4: N
5: E
6: G(1)
.
Notice that even though the program must contain the smallest possible number of lines, it is not required to minimize the number of moves that Marlin makes.
In the first test set, there is only one king. There are various ways for us to deduce its position; we will describe one that requires three queries and is relatively easy to understand.
First, we query (-1000000, 1000000), which is the upper left corner of the board; let A1 be the result. It tells us which J-shaped region of the board the king is in, illustrated as follows starting from the upper left corner:
0123...
1123
2223
3333
. .
. .
. .
Next, if we did not happen to get lucky and find the king, we query (-1000000 + A1, 1000000 - A1). That is, we query the corner of that J-shaped region. Call the result A2; it tells us how far away from the corner the king is, within that region. However, we do not know whether the king is to the left of or above the corner.
Finally, if we have still not found the king, we query (-1000000 + A1 - A2, 1000000 - A1). That is, we guess that the king is to the left of the corner. If the result is 0, then we have found the king; otherwise, we know the king is above the corner, at (-1000000 + A1, 1000000 - A1 + A2).
With more than one king, we find that it is not possible to determine the exact location of each king. For example, we cannot distinguish between a case with kings at (+1, 0) and (-1, 0) and a case with kings at (0, +1) and (0, -1). So it must be possible to answer queries with less complete information about the kings' locations.
The "L∞" metric in the problem, for which we take the maximum of the absolute differences of two coordinates, is a little inconvenient to work with directly, which results in the fairly ad-hoc nature of the test set 1 solution above.
Converting to diagonal coordinates makes things simpler. If a point is at (x, y) in the original coordinates, let (u, v) = (x + y, x - y) / 2 be its diagonal coordinates. Then if the diagonal coordinates of two points are (u1, v1) and (u2, v2), the distance between them is |u1 - v1| + |u2 - v2|. So if the kings are located at diagonal coordinates (ui, vi) for i= 1, ..., N, then the result of a query for the point (u, v) is Σi (|u - ui| + |v - vi|) = (Σi |u - ui|) + (Σi |v - vi|)
We can handle these two sums separately. To compute the first one, we need to know which "downright-sloping" diagonal lines the kings lie on, and to compute the second one, we need to know which "upleft-sloping" diagonal lines the kings lie on.
Now we need a method to compute these diagonals. Consider the point (-2M, 0). This point is far enough to the left that, if we propose this point, the total distance we get will be the sum of the differences in x coordinates. If we propose (-2M, 1), we will get the same answer, unless there is a king at (-M, -M), in which case we will get an answer one higher.
More generally, for a positive integer K, let d(K) for a positive integer K be the difference in the results of proposals of (-2M, K) and (-2M, K-1). d(K) will be equal to the number of kings below the diagonal x + y = -2M + K. We can use binary searches to find the places where d(k) changes value, and the magnitudes of those changes, to find out which diagonals of the form x + y = c contain kings, and how many they contain.
Similarly, by proposing points (-2M, -K), we can find out how many kings lie on the diagonals that go in the other direction. Once we have this data, we are able to compute the sums above and respond to queries from the judge.
For simplicity, let's assume that none of the arrays we want to sort contain any repeated entries. If there are repeatred entries, we can arbitrarily choose a correct sorted order for them.
To illustrate the sorting algorithm, let's first ignore the constraint on the number of permutations, and use N-1 permutations: the i-th permutation (1 ≤ i ≤ N-1) swaps the i-th element with the N-th element.
For example, when N = 5, we use the following 4 permutations:
With this setup, we can use the N-th element as a "buffer" to sort the first N-1 elements. The algorithm is as follows:
For example, let's consider the array [30, 50, 40, 10, 20]. We can:
Note that this solution uses N-1 permutations and 1.5N operations:
To fit within the limit on the number of allowed permutations, we can instead use the following 5 operations:
Our new algorithm is similar to the one above.
For example, let's consider the array [30, 50, 40, 10, 20]. We will use 3 permutations:
The algorithm works as follows:
The number of operations we use are:
For each N ≤ 50, there also exists a set of 4 rotations that allows us to rotate the first N-1 elements by any amount (from 1 to N-2) in at most 4 operations, making use of the fact that rotating by k is the same as rotating by k+N-1. As an example, for N = 50, {1, 3, 12, 20} is one such set.
This yields a solution that uses just 325 operations in the worst case.
In an alternative solution, instead of four rotations of the other= N-1 elements, we have four random involutions which swap randomly selected pairs of the N-1 elements.
Now we use the same algorithm as in the rotation solution, but instead of rotating elements into place, we use a sequence of the random permutations to move the right element to where it can be swapped with the buffer, and then apply the sequence in reverse to move everything back to where it was.
(We can use a breadth-first search to find the shortest sequence to move any given element into place.)
This process may result in a set of permutations that can't solve the input or can't solve it in few enough permutations, but we can simply retry by choosing a new set of random involutions, as getting a solution with under 450 permutations is highly likely.
The fact that we never need more than 3 palindromes is not obvious, and it was proved in a long, complicated paper. Numberphile made a video that explains the basics of the paper's argument. Knowing this upper bound is useful, but is not necessary to solve the problem.
Even if we haven't read every paper on arXiv for fun, we might also reasonably guess that the number of palindromes required is unlikely to be large because there are approximately sqrt(S) palindromes smaller than S, which means that there are approximately S palindrome pairs, which should result in Θ(S) numbers smaller than S that should be representable as sums of palindrome pairs. The number of triples is larger by another factor of sqrt(S), and their sums are all smaller than 3S, which does not leave much space to hide a number that could not be represented by a triple of palindromes, unless many triples add up to the same number.
The first step is to check if S is itself a palindrome. If it is a palindrome, then we are done. In the remaining explanation, we will assume that S is not a palindrome. Checking if a number is a palindrome takes O(log S) steps, one step per digit.
Key insight: There are only roughly 2 × 105 palindromic terms up to 1010. In the analysis below, we will call this number P.
To check if S is the sum of 2 palindromes, we simply loop through all palindromes, p, less than S and check if S-p is a palindrome. This takes O(P × log S) steps.
We were told that every number is the sum of 3 palindromes, so we must find such a sum! On first glance, it seems that doing the same as above for 3 palindromes is too slow since there are O(P2) pairs of palindromes to check. However, for all numbers up to 1010, one of the 3 palindromic terms is always at most 404 (which is needed for 1086412253, for example). Thus, as long as we search the pairs of palindromes in a way that searches triples containing a small value first, we will be fine.
Unfortunately, there are as many as 2 × 1020 palindromes less than 1040, so it is hopeless to even iterate through the palindromes. Something quicker will be needed.
We will assume X ≥ Y. The first step is to fix the numbers of digits in X and Y. Note that the number of digits in X must be either (1) the number of digits in S or (2) one less than the number of digits in S (otherwise, X + Y < S).
Let's assume that X and Y have a different number of digits (we will deal with the same-number-of-digits case below). The trickiest part about this problem is dealing with the pesky carries that occur while adding. For example, if we want to find 2 palindromes that add up to 2718281828 with lengths 10 and 8, then the first digit of X can be either 1 or 2 (depending whether there is a carry on the most significant digit). Because we don't know, let's try both! First, let's assume that we do not need a carry (so the first digit of X is 2). This also means that we can determine the least significant digit of Y by considering the sum modulo 10 (which also fills in the most significant digit of Y since it is a palindrome).
.......... 2........2 2........2 + ........ -> + ........ -> + 6......6 ============ ============ ============ 2718281828 2718281828 2718281828
At this point, to fill in the remaining unknown digits, we need a 9 digit palindrome and a 7 digit palindrome that sum to 2718281828 - (2000000002 + 60000006) = 658281820. This is a subproblem and we may recurse (with leading zeroes now allowed). The other option is that there is a carry on the most significant digit. In this case, the first digit of X must be 1.
When the numbers of digits in X and Y are different, there is always at least one unknown digit that we can determine. However, if X and Y have the same number of digits, this is not necessarily true. However, we can combine two simple observations to determine viable options for the first (and last) digits of both numbers. First, we consider the sums modulo 10. This narrows the possible values we may choose. Second, the number of digits in S compared to the number of digits in X (and Y) tells us if we want the sum of the most significant digits to be at least 10 (causing a carry). For example, if S has 5 digits, while X and Y only have 4 digits, then we must provide a carry in order for this sum to work. Similarly, if the number of digits in S and X are equal, then we cannot have a carry, so the sum must be at most 9. Even after these constraints, we still have some options (for example, if we need a sum of 8, we can use 0+8, 1+7, ... , 7+1, 8+0). Note that it doesn't matter* which of these options we take, since the only way they interact with other digits is with the carry.
* - There is one case where it matters: we must avoid creating a leading zero in a number.
Let D be the number of digits in S. There are O(D) possible lengths for X and Y. For each pair of lengths, we must decide if there is a carry on each digit on the left-hand side of S. Depending on implementation, this is O(2D/2 × D) operations. This leads to a total of O(2D/2 × D2) operations. Note that instead of just computing one digit at a time, we can determine the whole "overhang" values. In the example above, we can determine that the first two digits are either 26 or 27:
.......... 27......72 27......72 + ........ -> + ........ -> + 65....56 ============ ============ ============ 2718281828 2718281828 2718281828
This means that we only need to make D/overhang choices for the carries instead of D/2 choices. Thus, when the overhang is large, those computations do not contribute heavily to the complexity. This reduces the total complexity to O(2D/2 × D) operations.
In the paper listed above, the authors describe an algorithm to write any number as the sum of 3 palindromes is described. This was obviously not needed to solve this problem, but it does require an algorithm to find the sum of three palindromes.
To solve this problem, we will use the fact that there are O(S sqrt(S)) triples of palindromes less than S, which means that each number can be written with an average of O(sqrt(S)) different triples. This allows us to randomly select palindromes as one of our three values, then use the algorithm above to check whether the remaining value can be wrritten as the sum of 2 palindromes.
It is possible that there is a number that can only be represented in one different way as a sum of three palindromes, but we were unable to find any case that was not the sum of triples in many different ways. In fact, we were unable to find an input number such that one of the three numbers was more than 10801 (though, we expect that many such cases exist).
We are given a set of 2N points that we are to pair into N line segments such that they all intersect each other. That makes the set of line segments magnificent.
We can extend any line segment S into a full line L that divides the plane in two. In a magnificent set of line segments, since S intersects all other segments, all those other segments have one endpoint on each side of L (no other point can be on L or it would be collinear with the endpoints of S). This means that if we pick a point P in the input, it must be paired with another point Q such that the line that goes through both leaves exactly the same number of other points on each side. This hints at an algorithm: choose a point P, find a Q according to the definition above, pair P and Q, and repeat. However, what if there is more than one such Q?
One way to deal with the problem is by choosing P intelligently. For example, if we choose a leftmost point as P, all candidates for Q end up in the right half of the plane cut by a vertical line through P (with at most one other point possibly on the line). Consider a line rotating clockwise centered on P, going from vertical to vertical again (rotating 180 degrees). At the starting point, there are no points on the left side of the line, because P is leftmost. As it rotates, it will pass over all points, repeatedly adding one point to one side and removing one from the other. Since there are no collinear triples of points, this shift is always by 1. This means there is exactly one such line that has P and one more point on it, with N-1 points on each side. Moreover, if we sort all non-P points by the angle they form with P (choosing 0 to coincide with the vertical line), the point that ends up on the line is exactly the median of the sorted list.
Choosing P as a leftmost point gives a unique choice of another point Q to pair P with. We can then remove both and continue. The algorithm requires N iterations, and in each of them we must find a leftmost point, and sort O(N) points by angle. Calculating the cosine of the angles to compare without loss precision takes constant time. Picking the median and removing the pair of points all can be done in O(N) time or better. Therefore, the overall algorithm requires O(N2 log N) time, and it is enough to solve Test Set 1. If one uses a linear algorithm to find the median instead of sorting, it would improve the time complexity to O(N2). However, sorting to find the median is likely to be faster in practice due to constant factors.
A consequence of the reasoning above is that the solution is actually unique. Another observation is that any point in the convex hull of the points has the same property as a leftmost point, because the definition is invariant through rotations and any point in the convex hull can be made a leftmost point through a rotation. But a leftmost is one of the easiest to find.
There is another approach requiring an additional proof but leading to a slightly simpler algorithm for Test Set 1. Most importantly, it leads us one step closer to solving Test Set 2.
The additional key observation for this approach is that if a set of 2N points admits a magnificent pairing, then for every point P in the set (not just those in the convex hull) there is exactly one Q such that the line through P and Q leaves half the points on each side. The fact that there is at least one is immediate from the existence of a magnificent arrangement. The argument that there cannot be more than one requires more thought.
Assume there is a point P and two other points Q1 and Q2 such that both of the lines that go through P and each Qi have half of all the other points on each side. Moreover, without loss of generality, assume Q1 is the one that actually pairs with P in the magnificent pairing (we know it is unique). The following picture illustrates the situation.
In the picture, we have labeled the four areas into which the two lines divide the plane. Let A, B, C and D be the sets of input points contained in each area (not including P, Q1 or Q2). Notice that any point in A must be paired with a point in C in order for the produced segment to intersect PQ1. Similarly, any point in D must be paired with a point in B. All points below the line that goes through P and Q2 are in either A or D, which means there are |A| + |D| of them. The number of points above, on the other hand, is |B| + |C| + 1. Since we showed |A| ≤ |C| and |B| ≤ |D|, |B| + |C| + 1 ≥ |A| + |D| + 1 > |A| + |D|. This contradicts the assumption that the line that goes through P and Q2 has the same number of input points on each side.
This observation by itself only allows us to avoid the "find a leftmost point" step of the previous algorithm, which does not change its overall time complexity. The definite improvement is to more quickly shrink the set of points that we must consider, so that all steps within the iteration take less time. To do that, consider that after we have paired M pairs of points, the lines through each pair divide the plane into 2M areas, with only the outside areas (the ones with unbounded area) possibly containing leftover points. Moreover, each point is to be paired with one in the area that is opposite in order to cross all the lines, which is a necessary condition to intersect all line segments. When we create a new pair, exactly two of the areas are split in half. The idea is then: instead of removing the new pair and continuing with the full set, continue recursively with two separate sets. If we consider sets X and Y coming from opposite areas, split after pairing into X1 and X2 and Y1 and Y2, respectively, then we need to solve recursively for X1 and Y1 separately from solving for X2 and Y2 (assuming the areas are labeled such that X1, X2, Y1, Y2 appear in that order when going through them in clockwise order).
The last thing to do is to make sure we split X and Y more or less evenly with the new line. Notice that if we restrict ourselves to start with a point P that is part of the convex hull of X or Y or X ∪ Y, this might be impossible (i.e., all those pairs may split X and Y, leaving most remaining points on one side). Hence the need for the property with which we started this section. However, notice that if we sort all pairs to be made between points in X and points in Y by the slope of their produced segments, the first and last will split X and Y into an empty set and a set with |X| - 1 points (notice that |X| = |Y|). The second and next-to-last will split them into a set with 1 point and a set with |X| - 2 points. The i-th will split them into a set with i - 1 points and a set with |X| - i points. Therefore, if we choose randomly, we end up with a recursion similar to quicksort's, in which the reduction on the size of the sets is expected to be close enough to always partitioning evenly. Since the time it takes for the non-recursive part of a set of size M is O(M log M) — notice that calculating the partitions is only an additional linear time step — the overall expected time complexity of this recursive algorithm is (N log2 N).
We can represent each pair of jugglers from the input as the endpoints of a segment. The problem then asks us to find two of those segments that do not intersect, or report that there is no such pair.
Test Set 1 can be solved by checking every possible pair of segments to see if they intersect. Let pq be the segment between points p and q, and rs be the segment between points r and s; then these segments intersect if and only if
Let Li be the line that fully contains segment Si. Let Si and Sj be two segments that do not intersect. If Li and Lj are not parallel, at least one of Si and Sj does not contain the intersection between Li and Lj. We can find for every input segment Si, we can find whether its line Li intersects some other line at a point outside of Si (or not at all). Let F be the set of all such segments. Then, every non-intersecting pair contains at least one segment in F and the size of F is at most 25. We can do a linear pass over all other segments to see whether or not they intersect each segment in F to find the segments not in F that also participate in non-intersecting pairs. We focus now on finding all segments to put in F.
We now present three algorithms. The first two are ultimately similar: the first one uses less
advanced theory, but requires more problem-specific proofs because of it. They both
require somewhat large integers. For C++, __int128 is enough to represent all values,
but since we need to compare fractions that are the ratio of two __int128s, we'll
need special comparison code. For Java, BigInteger will do. The third algorithm is
a separate approach that uses a more advanced data structure, and requires only 64-bit integer
arithmetic.
First, assume there is a purely vertical segment (that is, its two endpoints have the same x coordinate). If we find more than one of those, we add all of them to F, since they don't overlap. If we find a single one, we can check it against all others like in the previous solution in linear time. In what follows, we assume no vertical segment is present.
Consider the extension of each segment Si to a full line Li. We will find the x coordinates of the leftmost and rightmost intersection of Li with all other Ljs and check that they are inside the range of x coordinates where Si exists. If one of those intersections is not inside that range, then we found one or two segments to put in F. Notice that finding all rightmost intersections is equivalent to finding all leftmost intersections in the input symmetric to the y axis, so if we have an algorithm that finds the leftmost ones, we can just run it twice (and reflecting the input takes linear time). Moreover, suppose we restrict ourselves to the leftmost intersection of Li such that Li is above the other intersecting line to the left of the found intersection. Let us call these "leftmost above intersections". We can use an algorithm that finds those intersections once on the unchanged input and once on the input reflected across the x axis to find the analogous "leftmost below intersections". In summary, we develop an algorithm that finds "leftmost above intersections" and then run it 4 times (using all combinations of reflecting / not reflecting the input across each axis), to find all combinations of "leftmost/rightmost below/above intersections".
To find all "leftmost above intersections", the key observation is that if two lines L1 and L2 intersect at x coordinate X, and L2 is below to the left of the intersection, then L2 cannot participate in any leftmost below intersection at coordinates X' > X. L2's own intersections at coordinates X' > X are not leftmost. If L2 intersects an L3 that is below L2 to the left of their intersection at X' > X, then L3 intersects L1 to the left of X' because of continuity: L1 is below L2 to the right of X.
This leads to the following algorithm: let X0 be the minimum x coordinate among all endpoints. Sort the lines by y coordinate at X0. Let Li be the line with the i-th highest y coordinate. We iterate over the lines in that order, while keeping a list or ranges of x coordinates and which previously seen line is below all others there, since that is the only one that can produce leftmost below intersections in that range. We keep that list as a stack.
At the beginning, we push (X1, 1) onto the stack, where X1 is the maximum x coordinate among all input points. This signifies that L1 is currently below in the entire range of x coordinates. Then, we iterate through L2, L3, ... LN. When processing Li, we find the x coordinate of its intersection with Lj and call it X, where (j, X') is the top of the stack. We check the intersection to see if it is within the x coordinate range of the two corresponding segments. Then, if X < X', we simply push (i, X) onto the stack. Otherwise, we pop (j, X') from the stack and repeat, since j was not the line below all others at X. Notice that this keeps the stack sorted increasingly by line index and decreasingly by intersection coordinate at all times.
Since every line is processed, pushed onto the stack and popped from the stack at most once, and everything else can be done in constant time, this iteration takes linear time. Other than that, the sorting by y coordinate takes time O(N log N), which is also the overall time complexity of the entire algorithm, since it dominates all other linear steps.
Notice that the way we use the stack in the above algorithm is quite similar to how a stack is used in the most widely known algorithm to compute the convex hull of a set of points. As we show in the next section, that is no coincidence.
In this solution we change how we find leftmost intersections. Treating vertical lines and reflecting to find rightmost intersections, and the way to use leftmost/rightmost intersections to find the solution to the problem, are the same as in the solution above.
To find the leftmost intersections, we can apply the point-line duality to the input. With duality between points and lines, a line y=mx+b in the original space can be represented as the point (m, -b) in the dual space. Similarly, a point (a, b) in the original space can be represented as a line of the form y=ax-b in the dual space. Notice that the dual space of the dual space is the original space. Vertical lines have no corresponding point. This duality has the property that when two lines L1 and L2 intersect in the original, their intersection point P corresponds to the line dual(P) in the dual space goes through the points dual(L1) and dual(L2).
Thus, if we take all lines that are extensions of input segments and consider the points that correspond to them in the dual space, the leftmost intersection for a given line L1 occurs when intersecting L2 such that the slope of the segment between dual(L1) and dual(L2) is minimal.
We now work on the dual space with an input set of points, and for each point P we want to find another point Q such that the slope of PQ is minimal. For each point in the convex hull of the set, the minimal slope occurs between that point and the next point in the convex hull. For points not in the convex hull, however, the appropriate choice is the temporary "next" point of the convex hull as calculated by the Graham scan. This leads to similar code as for the solution above, but using the duality saves us quite a few hand-made proofs. Just as for the algorithm above, all of the steps of this algorithm take linear time, with the exception of the sorting step needed for the Graham scan, yielding an overall O(N log N) algorithm.
Another solution requires more code overall, but some of that code might be present in a contestant's comprehensive library. It uses an incremental convex hull, which is a data structure that maintains a convex hull of a set of points and allows us to efficiently (in logarithmic time) add points to the set while updating the convex hull if necessary.
The algorithm checks for a condition that we mentioned in the analysis for Part 1: each
segment has the two endpoints of all other segments on different sides.
The algorithm uses a rotating sweep line. Assume the endpoints of all input segments are swapped
as necessary such that the segments point right (the first endpoint has an x coordinate no greater
than the x coordinate of the second endpoint). Then, we sort the segments by slope and consider a
rotating line that stops at all those slopes — that is, we iterate through the slopes in
order. If we number the segments S1, S2, ..., SN in that
order, S1 must have
all left endpoints on one side, and all right endpoints on the other. S2 is the same,
except the left endpoint of S1 goes with the right endpoints of all others, and vice
versa. In general, for Si we need to check for the left endpoint of all segments
S1, S2, ..., Si-1 to be on one side together with the right
endpoints of all segments Si+1, Si+2, ..., SN, and
all other endpoints are on the other side. If we find an endpoint of Sj
on the wrong side of Si, then Si and Sj do not intersect. If we
find no such example, the answer is MAGNIFICENT.
If we knew the convex hull of all the points that are supposed to be on each side, we could use ternary search on the signed distance between the convex hull and the line to efficiently find the point from that set whose signed distance perpendicular to the current Si is smallest (for the side where the distances are supposed to be positive) or largest (for the other side). If one of those finds us a point on the wrong side, we are done; otherwise, we know all other points are also on the correct side. Unfortunately, to keep those two convex hulls as we rotate would require us to both add and remove a point from each set. Removing is a lot harder to do, but we can avoid it.
When considering the slope of Si, instead of using the convex hull of the full set on one side, we can use the convex hull of the left endpoints that are on that side, and separately, the convex hull of the right endpoints on that side. That leaves us one additional candidate to check for that side, but one of those is the optimal candidate. Since we are calculating left and right endpoints separately, the 4 × N - 1 convex hulls we need are the ones of the set of left endpoints of the segments in a prefix of the list of segments, the left endpoints of the segments in a suffix of the list of segments, and similarly, the right endpoints of the segments in a suffix or prefix of the list of segments. We can calculate all of those convex hulls with a data structure that only provides addition of a point by calculating the convex hulls for prefixes in increasing order of segment index, and the ones for suffixes in decreasing order of segment index. Notice that this means we will calculate the convex hulls in an order different from the order in the original form of the algorithm.
We are doing O(N) insertions into the convex hull data structure and O(N) ternary searches, and each of these operations takes O(log N) time, making the time complexity of this algorithm also O(N log N).
For this particular use, we only need one half of the convex hull: the half that is closer to the line being inspected. In this half convex hull, the points in the hull are sorted by y coordinate, so a tree search can yield us the tentative insertion point, and we can maintain the convex hull by searching and inserting in a sorted tree. This is simple enough that it does not necessarily require prewritten code. Additionally, we can further simplify by using binary search on the angle between the convex hull and the line instead of the ternary search mentioned above.
There are two kinds of programs: those that terminate, and those that don't!
For any set of instructions for Marlin that does not loop indefinitely (because it reaches the end of the program), there is an equivalent program that has no goto instructions, and this is the shortest way to write that program.
Similarly, if a program loops indefinitely, there is an equivalent program that consists only of move instructions with a single goto at the end of the program, and this is the shortest way to write that program.
So we only need to consider those two cases: programs that consist only of move instructions, and programs with only a single goto, as the last instruction. Then we take the shortest of all of these.
We can easily find a minimal program of the first type with a breadth-first search (BFS) which
starts at M and stops when it reaches N, avoiding #s.
If the search terminates without reaching N, then we can output that the case is impossible.
Finding a minimal program of the second type is harder. The program can be split into two sections
which compute two separate paths: an initial path P produced by the instructions which do not
repeat, and then a path Q which repeats until N is reached.
Let B be the point where P ends. We can use a BFS, as in the previous case, to find a minimal P for all possible points B.
Optimizing Q is slightly more involved.
The first time through Q, Marlin walks through some set of grid cells. The second time through,
Marlin walks through grid cells of the same pattern, but offset by some displacement vector D.
This continues for
some number of iterations K until Marlin reaches the N cell.
So the first iteration of Q takes Marlin from B to B+D, but the path must avoid not only cells with
a #, but also cells which have an equivalent cell in a later iteration which is a #.
Additionally, the first iteration of Q must include a cell which, in a later iteration, will be N.
It is not easy to satisfy these constraints unless we already know the displacement D, and the number of iterations, K. So, we loop over all possibilities for these.
Inside this loop, we determine the shortest program for all possibilities for B, for the given
values of D and K.
We split Q into two parts, Q1 and Q2. Q1 contains the instructions
which repeat K times, and reach
cell N on the final iteration.
Q2 contains the instructions which only repeat K-1 times. (If we reach N at
the end of an iteration, Q2 is empty.)
Let N be the location of the cell containing N.
Q1 is a path from B to N-(K-1)×D, and Q2 is a path from N-(K-1)×D to B+D.
The path for Q1 can only touch cells X such that X+i×D is empty for 0<i<K. We do a BFS from N-(K-1)×D, using these cells, to find an optimal Q1 for all possibilities for B.
The path for Q2 can only touch cells X such that X+i×D is empty for 0<i<K-1. We do a BFS from N-(K-1)×D, using these cells, to find an optimal Q2 for all possibilties for B.
Finally, we loop over all possible cells for B, and sum up the lengths of the shortest P, Q1 and Q2, plus one for the goto statement.
Let max(R,C)=N. For the outer loop that iterates over D and K, there are O(N2) choices for D and O(N) choices for K. However, not all combinations are possible. If the number of iterations, K, is large, then the displacement D for each iteration must be small; otherwise Marlin's path would have to leave the grid to complete K iterations. The total number of valid combinations of D and K is O(N2) — we leave the proof as an exercise for the reader.
Inside the loop, setting up the grids for the BFS, running the two BFSs, and trying all values for B all take O(N2) time. So the loop takes O(N4) time.
The BFS outside the loop that computes all optimal paths P takes O(N2) time, and so does the search for the optimal solution with no goto statements. So the overall solution is O(N4), and runs fast enough to solve both test sets.
Being less careful can result in an O(N5) solution — for example, by doing O(K) work to check whether a cell is valid for the two BFSs inside the loop. This is sufficient to solve test set 1.
An exponential-time solution that naively tries all possibilities for Q is unlikely to work even for test set 1, since the maximum length of Q is too large.