Google Kick Start Archive — Round E 2017 problems
Overview
Thanks to everyone who participated! Kickstart Round F will take place next month; check the Kickstart schedule for more details.
Cast
Problem A (Copy & Paste): Written and prepared by Satoru Yamauchi.
Problem B (Trapezoid Counting): Written and prepared by Xuanang Zhao.
Problem C (BlackHole): Written and prepared by Ruoyu Zhang.
Solutions and other problem preparation and review by Ian Tullis, Yiming Li, Yang Xiao, Xuanang Zhao, Beiyu Li and Lin Jin. Thanks for their great help!
Analysis authors:
- Copy & Paste: Yang Xiao
- Trapezoid Counting: Beiyu Li
- BlackHole: Ruoyu Zhang
A. Trapezoid Counting
Problem
In this problem, we will consider a trapezoid to be a convex quadrilateral with exactly one pair of parallel sides. If the lengths of the two non-parallel sides are equal, we say the trapezoid is isosceles.
You have some wooden sticks of various lengths, and you need to pick exactly four of them to form the four sides of an isosceles trapezoid. How many different sets of four sticks will allow this? Even if two sticks have the same length, they are considered to be different sticks. Sticks could not be bended and broke into parts.
Input
The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. The first line consists of one integer N, the number of sticks. The second line consists of N integers; the i-th of these, Li, represents the length of the i-th stick.
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 different sets of four sticks that can form an isosceles trapezoid, as described
above.
Limits
1 ≤ T ≤ 100.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ Li ≤ 109.
Small dataset (Test set 1 - Visible)
1 ≤ N ≤ 50.
Large dataset (Test set 2 - Hidden)
1 ≤ N ≤ 5000.
Sample
4 5 2 3 3 4 3 4 1 5 3 1 4 2 2 3 3 9 3 4 1 4 2 5 3 1 3
Case #1: 5 Case #2: 0 Case #3: 0 Case #4: 73
In Sample Case #1, there are five ways to choose four out of the five given sticks, and any one of those five sets of four sticks can be used to form an isosceles trapezoid. In Sample Case #2, note that the set {1, 1, 3, 5} cannot form an isosceles trapezoid, even though two of its sticks are of equal length. In Sample Case #3, note that the set {2, 2, 3, 3} can form a rectangle, but in this problem, a rectangle is not considered to be an isosceles trapezoid.
B. Copy & Paste
Problem
You want to create a certain target string S, which consists only of lowercase English letters. You start with an empty string, and you are allowed to perform the following operations:
- Add any single lowercase letter to the end of your string.
- Copy any substring of your string (that is, all of the characters between some start point in your string and some end point in your string) to the clipboard. Doing this overwrites whatever was in the clipboard before. The clipboard starts off empty.
- Add the entire contents of the clipboard to the end of your string. (The contents of the clipboard do not change.)
What is the smallest number of operations needed to create your target string? Note that you must create exactly the target string, with no additional letters.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line contains the target string S.
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 minimum number of operations (as described in the problem statement) needed to create the target string.
Limits
Time limit: 40 seconds per test set.Memory limit: 1GB.
S consists only of lowercase English letters in the range
a through z.
Small dataset (Test set 1 - Visible)
1 ≤ T ≤ 100.
1 ≤ length of S ≤ 6.
Large dataset (Test set 2 - Hidden)
1 ≤ T ≤ 100.
1 ≤ length of S ≤ 300.
Sample
3 abcabab aaaaaaaaaaa vnsdmvnsnsdmkvdmkvnsdmk
Case #1: 6 Case #2: 7 Case #3: 15
The optimal solution for Sample Case #1 is:
- Type
a. - Type
b. - Type
c. - Copy
abto the clipboard. - Paste
abat the end of the string. - Paste
abat the end of the string.
- Type
a. - Type
a. - Type
a. - Copy
aaato the clipboard. - Paste
aaaat the end of the string. - Copy
aaaaato the clipboard. - Paste
aaaaaat the end of the string.
C. Blackhole
Problem
Alice is trying to prevent dangerous black holes from threatening Earth. Right now, there are three black holes that are different points in 3-D space. Alice will create exactly three containment spheres, and all three must have the same radius. Spheres do not interfere with each other, so they may overlap.
Alice must place these spheres so that each black hole is covered by at least one sphere. Moreover, to ensure stability, the total set of points covered by at least one sphere must form a single connected area.
Alice wants to solve this critical problem as inexpensively as possible. What is the minimum radius that she can use?
Input
The input starts with one line with one integer T: the number of test cases. T test cases follow. Each test case consists of three lines. The i-th of those lines consists of three integers Xi, Yi, and Zi, representing the 3-D coordinates of the i-th black hole.
Output
For each test case, output one line Case #x: y, where x is the test case number (starting from 1) and y is a rational representing the minimum radius that Alice can use to solve the problem. y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Limits
Time limit: 20 seconds per test set.Memory limit: 1GB.
-1000 ≤ Xi ≤ 1000, for all i.
For all j ≠ k, (Xj, Yj, Zj) ≠ (Xk, Yk, Zk). (No two of the points have the same coordinates.)
Small dataset (Test set 1 - Visible)
Yi = 0, for all i.Zi = 0, for all i.
Large dataset (Test set 2 - Hidden)
-1000 ≤ Yi ≤ 1000, for all i.-1000 ≤ Zi ≤ 1000, for all i.
Sample
4 0 0 0 1 0 0 -1 0 0 4 0 0 5 0 0 -2 0 0 0 0 0 1 1 1 -1 -1 -1 -4 2 -2 5 1 -4 0 4 -9
Case #1: 0.3333333333 Case #2: 1.1666666667 Case #3: 0.5773502692 Case #4: 2.1373179212
In Sample Case #1, the smallest radius we can use is 1/3. Our three spheres should be centered at (-2/3, 0, 0), (0, 0, 0), and (2/3, 0, 0).
Analysis — A. Trapezoid Counting
Trapezoid Counting: Analysis
Small dataset
There are at most 50 sticks, which means we can enumerate all different sets of four sticks directly.
For a set of sticks to form the four sides of an isosceles trapezoid, it must meet all of the following conditions:
- There must be a pair of sticks with equal length. Call this length C.
- The remaining two sticks must have unequal lengths. Call the shorter of those lengths A, and the longer one B.
- The four sticks must be able to actually connect to form an isosceles trapezoid, so we need to obey an isosceles trapezoid equivalent of the triangle inequality: B < A + 2 × C.
Large dataset
First, we can create a Length array with all the unique length values, and a Count array with the counts of each of those values. For example, for sticks with lengths [3, 4, 1, 4, 2, 6, 3, 1, 3], we would get the Length array [1, 2, 3, 4, 6] and the Count array [2, 1, 3, 2, 1].
Consider the inequality above: B < A + 2 × C. There are two possible situations in which valid isosceles trapezoids can be formed:
- A is equal to C or B is equal to C.
- A, B, and C are all different values. (Recall that we cannot have A equal B, or else the shape would not meet the problem's definition of an isosceles trapezoid.)
For the first situation, we consider all possible values C = Length[i] such that Count[i] ≥ 3. For each of these, we have to count how many sticks have length less than 3 × C but not equal to C. We can do this quickly by using a prefix sum of the Count array (which we only need to create once). Then we add that number, multiplied by (Count[i] choose 3), to our answer.
For the second situation, we consider all possible values C = Length[i] such that Count[i] ≥ 2. For each of these, we consider all A = Length[j] (with i ≠ j). For each of those (C, A) pairs, we need to count how many sticks have length B such that B ≠ C, A < B, and B < A + 2 × C. The number of valid B is the prefix sum of Count up to A + 2 × C, minus the prefix sum of Count up to A, possibly minus the Count of C if it is in that range. Then we add that number, multiplied by (Count[i] choose 2), to our answer.
This method avoids double-counting any sets, and it runs in O(N2) time, which is easily fast enough for N ≤ 5000.
Analysis — B. Copy & Paste
Copy & Paste: Analysis
Small dataset
Let N be the length of the target string S. We can observe that:
- Copying and pasting a single character is always strictly worse than just typing another instance of that character, which takes only one operation.
- Copying and pasting two or more characters can be useful, but it turns out not to be for N ≤ 5. Suppose that we wanted to use copying and pasting to create a string of length 5. Then the only possible copy/paste operation that uses two or more characters is to start with a string of length 3 and copy/paste two of its characters. But then we could have just typed the two characters instead, using the same number of operations.
- For N = 6, there are some patterns for which the optimal strategy requires copying and pasting. With some brute-force experimentation or case-based analysis, you can find that they are of all of the of the form 111111, 121212, or 123123 (in which each number consistently stands for a particular letter)..
It is also possible to use a brute-force breadth/depth-first search to solve the Small.
Large dataset
For the Large dataset, we can use dynamic programming. We will keep track of the minimum number of operations used to reach a state with the following parameters, as the target string is being built from left to right:
- Current length - the length of the prefix of the target string that we have built so far
- Clipboard content - the content in the clipboard
There can be at most O(N2) substrings, so there are O(N3) states in total. For each state, we can choose to type a character, paste the contents of the clipboard, or copy something into the clipboard. Since there are O(N2) substrings that we could choose to copy, there are O(N2) possible moves from each of the O(N3) possible states, and so the overall time complexity is O(N5). This approach is fast enough to pass all the test cases within the time limit.
Notice that the copy operation is needed only when the copied string needs to be pasted as the next operation. It reduces the number of candidate strings that need to be copied in each move to O(N) because the number of substring starting with next character is O(N). Thus, this approach leads to an O(N4) solution.
There is even an O(N3) approach. Can you find it?
Analysis — C. Blackhole
Black Hole: Analysis
Small Dataset
In the Small dataset, all three black holes are along the x-axis, so the solution is simple: the three spheres should be placed in a row (touching only at single points) to cover the distance spanned by the leftmost and rightmost of the black holes. So the answer is just the distance between leftmost and rightmost black holes, divided by 6.
Large Dataset
To solve the Large dataset, it is helpful to notice that although this is a 3-D problem, it only has three points (black holes), and there is at least one plane that contains all three of the points. It is therefore possible to simplify the problem into a 2-D problem: how can we use three connected circles of equal radius to cover three points on a plane?
Suppose that we have Circles A, B, and C, with circle A connected to circle B, circle B connected to circle C, and circles A and C possibly (but not necessarily) connected. Then these are the only two potentially optimal ways to cover the points:
Type I: Each point is in a different circle.
Type II: Two points are in circle A, and a third point is in circle C.
If we call the points X, Y, and Z, then there are three Type I possibilities and three Type II possibilities. For example, one possibility for Type I is to have Point X in Circle A, Point Y in Circle B, and Point Z in Circle C. One possibility for Type II is to have Points Y and Z in Circle A, and Point X in Circle C.
Any other arrangement cannot be optimal. For instance, if all three points are in one circle, we are wasting the other two circles. If two points are in one circle and one point is in another circle, and the third circle does not connect the first two, then we could make the circles smaller and use the third to connect the first two.
To find the minimum valid radius for a possible configuration, we can use binary search. But we still need a way to determine whether a radius is valid.
For Type I possibilities, how can we determine whether a radius R is valid? Let K be the center of circle B. Then:
- The distance between K and the point in circle B must be no greater than R, or else the point would not be in B.
- The distance between K and the point in circle A must be no greater than 3R, or else circles A and B would not be connected.
- The distance between K and the point in circle C must be no greater than 3R, or else circles B and C would not be connected.
It is equivalent to check that point K is in all three of these circles:
- A circle of radius R centered at the point in circle B
- A circle of radius 3R centered at the point in circle A
- A circle of radius 3R centered at the point in circle C
So, if those three circles have any common intersection, then we know that radius R is valid, without having to choose a specific point K.
We can use a similar strategy for Type II possibilities. Let K be the center of circle A. Then:
- The distance between K and the point in circle C must be no greater than 5R, or else circles A and C would not be connected.
- The distance between K and the first point in circle A must be no greater than R, or else the point would not be in circle A.
- The same is true of the second point in circle A.
and so we only need to look for a common intersection of these three circles:
- A circle of radius 5R centered at the point in circle C
- A circle of radius R centered at the first point in circle A
- A circle of radius R centered at the second point in circle A
To determine whether the three circles have at least one point in common, we can start by finding the intersections of the perimeters of each pair of circles. If two circles' perimeters intersect at...
- ...two points, we can check whether either of those points is in the third circle.
- ...one point, we can check whether that point is in the third circle.
- ...infinitely many points (that is, the two circles are the same), it suffices to check whether either of those circles intersects the third circle.
- ...zero points, then either one circle is completely within the other, or the circles are disjoint. If the circles are disjoint, there can be no common point. Otherwise, we can disregard the outermost circle and check whether the innermost circle intersects the third circle.
If none of these checks succeed, then the three circles have no point in common. Otherwise, they have at least one.
Once we have found the minimum radius for each cover method, the minimum of those is our final answer.