This Kickstart round began with No Nine, which was a adhoc problem with an alternate dynamic programming solution. Then came Sherlock and the Bit Strings,which could be solved with dynamic programming. Finally, we had King's Circle, involving a nice observation augmented by the sweep line technique.
Thanks to everyone who participated!
Cast
Problem A (No Nine): Written and prepared by Lin Jin.
Problem B (Sherlock and the Bit Strings): Written by Lalit Kundu. Prepared by Lalit Kundu and Akashdeep Nain.
Problem C (King's Circle): Written by Kevin Tran. Prepared by Kevin Tran and Lalit Kundu.
Solutions and other problem preparation and review by Ian Tullis, Lalit Kundu, Satyaki Upadhyay, Jonathan Irvin Gunawan, Akashdeep Nain, Pi-Hsun Shih and Md Imrul Hassan.
Analysis authors:
No Nine is a counting game that you can try when you are bored. In this game, you are only allowed to say numbers that are legal. A number is legal if and only if all of the following are true:
For example, the numbers 16 and 17 are legal. The numbers 18, 19, 17.2, and -17 are not legal.
On the first turn of the game, you choose and say a legal number F. On each subsequent turn, you say the next legal number. For example, if you played a game with F = 16, you would say 16, 17, 20, 21, and so on.
Alice is very good at this game and never makes mistakes. She remembers that she played a game in which the first number was F and the last number was L (when she got tired of the game and stopped), and she wonders how many turns were in the game in total (that is, how many numbers she said).
The input starts with one line containing one integer T; T test cases follow. Each test case consists of a single line containing two integers F and L: the first and last numbers from the game, as described above.
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 the turns played in the game.
1 ≤ T ≤ 100.
Time limit: 60 seconds per test set.
Memory limit: 1 GB.
F does not contain a 9 digit.
F is not divisible by 9.
L does not contain a 9 digit.
L is not divisible by 9.
1 ≤ F < L ≤ 106.
1 ≤ F < L ≤ 1018.
2 16 26 88 102
Case #1: 9 Case #2: 4
In Sample Case #1, the game lasted for 9 turns, and the numbers Alice said were: 16, 17, 20, 21, 22, 23, 24, 25, 26.
In Sample Case #2, the game lasted for 4 turns, and the numbers Alice said were: 88, 100, 101, 102.
Sherlock and Watson are playing a game involving bit strings, i.e., strings
consisting only of the digits 0 and 1.
Watson has challenged Sherlock to generate a bit string S of N
characters S1, S2, ..., SN. The string
must obey each of K different constraints; each of these constraints is
specified via three integers Ai, Bi, and
Ci. The number of 1s in the substring
SAi, SAi + 1, ...,
SBi must be equal to Ci.
Watson chooses the constraints in a way that guarantees that there is at least one string of the right length that obeys all of the constraints. However, since there could be multiple such strings, Watson wants Sherlock to choose the string from this set that is Pth in lexicographic order, with P counted starting from 1.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line containing three integers N, K, and P, as described above. Then, there are K more lines; the i-th of these contains three integers Ai, Bi and Ci, representing the parameters of the i-th constraint, as described above.
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 Pth lexicographically smallest bit string among all
possible strings following the K specified constraints.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ N ≤ 100.
1 ≤ K ≤ 100.
1 ≤ P ≤ min(1018, the number of bit strings that obey
all of the constraints).
1 ≤ Ai ≤ Bi ≤ N for all 1
≤ i ≤ K.
0 ≤ Ci ≤ N,
for all 1 ≤ i ≤ K.
(Ai, Bi) ≠
(Aj, Bj),
for all 1 ≤ i < j ≤ K.
Ai = Bi
for all 1 ≤ i ≤ K.
Bi - Ai ≤ 15
for all 1 ≤ i ≤ K.
2 3 1 2 2 2 1 3 1 1 2 2 0
Case #1: 011 Case #2: 000
In Sample Case #1, the bit strings that obey the only constraint in lexicographically increasing order are [010, 011, 110, 111].
In Sample Case #2, the bit strings that obey the only constraint in lexicographically increasing order are [000, 001, 100, 101].
1 4 3 1 1 2 1 2 3 1 3 4 1
Case #1: 0101
In Sample Case #1, the bit strings that obey the given constraints in lexicographically increasing order are [0101, 1010].
For the first time in as long as anyone can remember, the kingdom of Kickstartia is alive with celebration: it is the coronation day for the new King. As is customary for the coronation, a Royal Parade will march its way through the streets of the capital.
The capital can be thought of as an infinite 2D plane, with infinitely many, infinitely long, streets spaced one meter apart, running horizontally and vertically throughout. The horizontal streets are labelled from negative infinity to infinity from top to bottom, while the vertical streets are labelled from negative infinity to infinity from left to right.
There are N cafes in the capital, and the i-th one is located at the intersection of vertical street Vi and horizontal street Hi. No two cafes lie on the same intersection. In order to keep the parade technicians happy and well-fed, you will pick exactly three of these cafes for them to stop at along the way.
To introduce some order to the chaos, you have additionally decided that a parade should end where it starts, and that its path through the streets must make the shape of a square (with straight sides, all of equal length). Each cafe can be anywhere along the square (on the sides or at a corner).
This immediately presents a problem: depending on which three cafes you pick, it may not be possible to make a square parade that goes through those three cafes. So, your task is to find out: how many different sets of three cafes are there such that there exists at least one square parade that includes all three cafes in the set? (Two sets are different if and only if there is a cafe in one that is not present in the other.)
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line containing ten integers N, V1, H1, A, B, C, D, E, F and M.
N is the number of cafes. The first cafe lies at the intersection of vertical street V1 and horizontal street H1.
The locations of the remaining cafes Vi, Hi, can be generated for i = 2 to N as follows:
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 sets of cafes satisfying the conditions explained above.
1 ≤ T ≤ 100.
Time limit: 100 seconds per test set.
Memory limit: 1 GB.
0 ≤ A < M.
0 ≤ B < M.
0 ≤ C < M.
0 ≤ D < M.
0 ≤ E < M.
0 ≤ F < M.
0 ≤ V1 < M.
0 ≤ H1 < M.
For all i ≠ j, (Vi, Hi) ≠
(Vj, Hj).
3 ≤ N ≤ 1000.
2 ≤ M ≤ 1000.
3 ≤ N ≤ 5 × 105.
2 ≤ M ≤ 106.
3 4 1 1 4 1 1 4 2 4 5 6 3 1 1 0 1 0 1 0 9 3 7 24 34 11 17 31 15 40 50
Case #1: 3 Case #2: 20 Case #3: 0
In Sample Case #1, there are four cafes and they are at (1, 1), (1, 0), (0, 3) and (4, 0). It would be possible for a square parade to go through the set of cafes (1, 1), (1, 0), (0, 3), or the set (1, 1), (1, 0), (4, 0) or the set (1, 0), (0, 3) (4, 0) as shown in the diagram below. There is no possible square parade that goes through the set of cafes (1, 1), (0, 3), (4, 0).
In Sample Case #2, there are 6 cafes and they are at (3, 1), (4, 1), (5, 1), (6, 1), (7, 1) and (8, 1). Since they are all on the same vertical street, every triplet of cafes has a square parade going through it. So the answer is 6 choose 3 = 20.
In Sample Case #3, there are 3 cafes and they are at (7, 24), (19, 17), (0, 34). There is no square parade that goes through these cafes, so the answer is 0.
Note: We do not recommend using interpreted/slower languages for the Large dataset of this problem.
To solve the Small dataset, we can check all numbers in the range [A, B] and count how many of them are legal.
Let f(X) be the number of legal numbers in the range [0, X]. Then the answer is f(B) - f(A) + 1, since A and B are both legal numbers.
To calculate f(X), let x[0], x[1], ..., x[n-1] be the decimal representation of X, such that X = Σ0≤i<nx[i]×10i. For numbers in the range [X - x[0], X], we will check each number individually to see if it is legal.
If we list numbers without the digit 9 in their decimal representations, we can find that their decimal representations are the same as listing numbers in base 9. So for numbers in the range [0, X-x[0]), there are C = Σ1≤i<nx[i]×9i numbers consisting only of digits in the range [0, 8]. According to the formula, C is divisible by 9.
For any integer Y, there is exactly one number divisible by 9 in the set {10Y + 0, 10Y + 1, ..., 10Y + 8}. The C numbers form C/9 such groups, and in each group, there are exactly 8 legal numbers, so there are 8C/9 legal numbers in the range [0, X-x[0]).
Alternative solution (Dynamic Programming): To calculate f(X), we can define dp[i][j] to be the number of integers Y such that
The Bellman equation is dp[k-1][j] = sum[dp[k][j'] for 0≤d≤8, 10j'+d ≡ j (mod 9)] + |{g | 10floor(X/10k)≤g<floor(X/10k-1), g ≡ j (mod 9)}|.
The main challenge of finding the P-th lexicographically smallest valid string is to count the number of valid strings given a prefix requirement (i.e. the string must begin with a given prefix) and the K constraints given in the problem. The prefix requirement is necessary since we're going to fill the characters of the string one by one from the first character. Once we have solved the counting problem, the original problem becomes easier.
We can loop through each of the valid characters i in lexicographically increasing order (i.e. 0 and 1 in this problem) for the first position. Then we count the number of valid strings with prefix i. Let's say this value is X. If X ≥ P, we know that i is the right character for the first position. Otherwise, we continue the loop and subtract X from P until we find the right character for the first position. We keep doing this for each position until the last position.
To avoid an overflow when counting the number of valid strings, we can limit our computation to maxP, where maxP is the maximum value of P (i.e. 1018 in this problem). In other words, whenever we find that the number of valid strings would be more than maxP, we can set it to maxP.
Finding the number of valid strings in the Small dataset is easier since Ai = Bi in each of the constraints. It is the same as saying that the Ai-th character must be Ci. Therefore, the set of possible characters for each position is independent of what character we choose for any other position. The number of valid strings is simply 2Y, where Y is the number of positions without a constraint. For example, the number of valid strings without a given prefix requirement is 2N - K.
Finding the number of valid strings in the Large dataset is trickier since the set of possible characters for each position is no longer independent of what character we choose for any other position.
We can solve this dataset using a dynamic programming solution. Let us define
a function f(x, last), where x is a [1, N]
integer and last is a 15-bit (15 is the maximum possible value of
Bj - Aj) integer, is the number of ways
of:
0s and 1s to the bit string from the
x-th position to the N-th position (in other words,
assume that the bit string has been "filled" until the
(x - 1)-th position),
x - 15)-th position to
the (x - 1)-th position) are represented in
last, and
How do we calculate f(x, last)? We loop over i in the list
[0, 1], the character that we consider putting in the x-th
position. Together with last, we now know what the last 16
characters we have placed are. Since
Bj - Aj ≤ 15, and using the
information of last 16 characters that we have placed, we can check all the
constraints j where Bj = x.
If at least one of these constraints is violated, then i is not a valid
character to be placed in on the x-th position. Otherwise,
placing in i on the x-th position contributes
f(x + 1, g(last, i)) to f(x, last), where
g(last ,i) is updating the last mask by ignoring the
first bit of last (since we won't need the character from the
(x - 15)-th position anymore) and appending an i bit to
the end.
With the prefix requirement s, the number of valid strings is the
value of f(length(s) + 1, the last 15 characters of s). Since
there are N possible values for x, 215 possible
values for last, and each computation of f(x, y)
requires a loop for checking the constraints, this solution runs in
215 × O(N + K) time. Even though 215
is a constant multiplicative factor that does not affect the big-O time of the
solution, it is relevant to the running time, particularly because
215 is much greater than the largest possible value of
N + K, so we include it here for clarity.
Let's set the story aside and consider the underlying geometry problem: given N points in the 2D plane, how many triplets of points have an axis-aligned square that goes through them?
It is natural to first tackle this subproblem: given three points in the 2D plane, is there an axis-aligned square that goes through those three points?
After trying different sets of points, it is not too difficult to come up with the key restriction. Consider the axis-aligned bounding box (that is, the rectangle which contains all the points which is as small as possible) for the three points. An axis-aligned square that goes through the three points exists if and only if all three points lie somewhere on the edges of the bounding box (see below).
A bounding box around two points will always have those points at opposite corners. The bounding box might have zero area (if both points are horizontally or vertically aligned), but that's fine. This gives us enough information to solve the Small dataset: If two points are chosen as the corners of a bounding box, then these two points will form a valid triplet with any point that is not strictly inside the bounding box. That is, any point outside the bounding box or along its edges will form a valid triplet with these two points. This gives us an O(N2) solution: For every pair of points, count the number of points that are strictly inside their bounding box, which can be done in O(1) using a 2D cumulative sum array, taking advantage of the small bounds on the coordinates in the small test set. Since every invalid triplet is counted exactly once (for any invalid triplet, exactly one of the points will be inside the bounding box defined by the other two points).
For the Large dataset, we need to turn around our thinking. Instead of fixing the bounding box and counting the number of points inside it, we will fix a point as the "inside" point, and count how many different bounding boxes contain it. Let's say we fix an inside point. Let A be the set of points above and to the right of our fixed point, and B be points below and to the left. Then there are A × B bounding boxes that contain our fixed inside point: every point in A forms a bounding box containing our fixed inside point with any of the points in B. The same can be said for the points above and to the right combined with those below and to the left.
This gives us an O(N log N) solution: for each point, count the number of bounding boxes that would contain it by finding the number of points above and to the left, above and to the right, below and to the left and below and to the right, and multiplying accordingly. Counting these points can be done ine O(log N) using a linear sweep with a range tree or with a self balancing binary search tree (among other ways).
To wrap things up, we need to prove our original assertion: An axis-aligned square that goes through the three points exists if and only if all three points lie somewhere on the edges of the bounding box. The negative case is easy. If there is a point not on the edges of the bounding box, then there is no axis-aligned rectangle that goes through the three points, let alone a square. The affirmative case is more difficult. We will start with the bounding box and morph it into a square. If the bounding box is already a square, then we are done. Otherwise, one pair of parallel sides is longer. If either of these sides does not have a point on it excluding the corners, then that side can be extended until the shape is a square (see below).