# Google Kick Start Archive — Round B 2018 problems

## Overview

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: Lin Jin
• Sherlock and the Bit Strings: Jonathan Irvin Gunawan
• King's Circle: Kevin Tran

## Problem

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:

• it is a natural number (i.e. in the set {1, 2, 3...})
• it does not contain the digit 9 anywhere in its base 10 representation
• it is not divisible by 9

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).

### Input

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.

### Output

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.

### Limits

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.

#### Large dataset (Test set 2 - Hidden)

1 ≤ F < L ≤ 1018.

### Sample

Sample Input
```2
16 26
88 102
```
Sample Output
```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.

## B. Sherlock and the Bit Strings

### Problem

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 `1`s 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.

### Input

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.

### Output

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.

### Limits

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 ≤ AiBiN for all 1 ≤ i ≤ K.
0 ≤ CiN, for all 1 ≤ i ≤ K.
(Ai, Bi) ≠ (Aj, Bj), for all 1 ≤ i < j ≤ K.

#### Small dataset (Test set 1 - Visible)

Ai = Bi for all 1 ≤ i ≤ K.

#### Large dataset (Test set 2 - hidden)

Bi - Ai ≤ 15 for all 1 ≤ i ≤ K.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
```2
3 1 2
2 2 1
3 1 1
2 2 0
```
Sample Output
```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].

### Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.
Sample Input
```1
4 3 1
1 2 1
2 3 1
3 4 1
```
Sample Output
```Case #1: 0101
```

In Sample Case #1, the bit strings that obey the given constraints in lexicographically increasing order are [0101, 1010].

## C. King's Circle

### Problem

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.)

### Input

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:

• Vi = (A × Vi-1 + B × Hi-1 + C) modulo M
• Hi = (D × Vi-1 + E × Hi-1 + F) modulo M

### Output

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.

### Limits

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.

### Sample

Sample Input
```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
```
Sample Output
```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.

## No Nine: Analysis

### Small dataset

To solve the Small dataset, we can check all numbers in the range [A, B] and count how many of them are legal.

### Large dataset

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

• Y < floor(X/10i)
• Y does not contain 9 in its decimal representation;
• Y ≡ j (mod 9).
Then f(X) = dp[0][1] + dp[0][2] + ... + dp[0][8] + 1.

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)}|.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Bit String: Analysis

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.

### Small dataset

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.

### Large dataset

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:

• assigning `0`s and `1`s 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),
• the last 15 characters (i.e. from (`x` - 15)-th position to the (`x` - 1)-th position) are represented in `last`, and
• the assignment has to satisfy all the constraints i where Bi ≥ x.

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.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — C. King's Circle

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).

This idea is simple enough to start working with even without a thorough proof (which we will get back to later).

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).

So what do we do if both long sides have a point on them (not at a corner)? This is actually impossible. For a contradiction, suppose that both long sides do have a point on them, not at a corner. It doesn't matter where the third point is, there is one side with no points on it at all (not even at the corners)! This means the bounding box can be shrunk, which contradicts our definition of the bounding box being as small as possible.
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Statistics — A. No Nine

First
Nikki371 4:35
strawstack 5:11
tyfkda 5:29
FrankHu 5:51
nik.xyz 6:01

### Test set 2: 177 correct solutions (23.5% solve rate)

First
vicennial 8:11
Invin.Amit 9:40
Sarvagya3943 10:06
Egor.Lifar 11:35
thundercracker 11:44

## Statistics — B. Sherlock and the Bit Strings

First
wbb 20:38
Ashishgup 22:28
0x486F626F 28:35
panyuchong 29:06
rkm0959 29:58

### Test set 2: 19 correct solutions (2.5% solve rate)

First
Benq 33:39
chinmay0906 63:01
VageshVerma 70:05
Egor.Lifar 74:55
teja349 84:53

## Statistics — C. King's Circle

First
peak000333 52:28
esrever 53:25
Invin.Amit 60:18
Benq 64:52
Simonsch 72:15

### Test set 2: 14 correct solutions (1.9% solve rate)

First
esrever 53:25
Invin.Amit 60:18
Benq 64:52
Georeth.0v0 76:51
rkm0959 80:30