# Google Kick Start Archive — Round E 2019 problems

## Overview

Thank you for participating in Kick Start 2019 Round E!

Cast

Cherries Mesh: Written by Bartosz Kostka and prepared by Seunghyun Jo and Lalit Kundu.

Code-Eat Switcher: Written by Archie Pusaka and prepared by Reyno Tilikaynen.

Street Checkers: Written by Bartosz Kostka and prepared by Jonathan Irvin Gunawan.

Solutions, other problem preparation, reviews and contest monitoring by Anushi Maheshwari, Himanshu Jaju, Zhang Chen, Sadia Atique, Yang Xiao, Teja Vardhan Reddy Dasannagari.

Analyses were authored by Kevin Tran, Alan Huang and Anushi Maheshwari.

## A. Cherries Mesh

### Problem

Your friend is recently done with cooking class and now he wants to boast in front of his school friends by making a nice dessert. He has come up with an amazing dessert called Cherries Mesh. To make the dish, he has already collected cherries numbered 1 to N. He has also decided to connect each distinct and unordered pair of cherries with a sweet strand, made of sugar. Sweet strands are either red or black, depending on the sugar content in them. Each black strand contains one units of sugar, and each red strand contains two units of sugar.

But it turns out that the dessert is now too sweet, and these days his school friends are dieting and they usually like dishes with less sugar. He is really confused now and comes to your rescue. Can you help him find out which all sweet strands he should remove such that each pair of cherries is connected directly or indirectly via a sugar strand, and the dish has the minimum possible sugar content?

### Input

The first line of input gives the number of test cases, T.

Each test case begins with a line containing two integers N and M, the number of cherries and the number of black sweet strands, respectively.

Then M lines follow, each describing a pair of cherries connected to a black strand. The i-th line contains cherries numbered Ci and Di, it indicates that Ci and Di cherry are connected with a black strand of sugar.

Note: Any other pair of cherries not present in the input means that they are connected by a red strand.

### 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 minimum possible sugar content.

### Limits

Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100
MN*(N-1)/2
1 ≤ CiN, for all i.
1 ≤ DiN, for all i.
CiDi, for all i.
Every {Ci, Di} is distinct.

1 ≤ N ≤ 100.
0 ≤ M ≤ 100.

#### Test set 2 (Hidden)

For at least 90% of the test cases:
1 ≤ N ≤ 1000.
0 ≤ M ≤ 1000.

For all test cases:
1 ≤ N ≤ 105.
0 ≤ M ≤ 105.

### Sample

Sample Input
```2
2 1
1 2
3 1
2 3
```
Sample Output
```Case #1: 1
Case #2: 3
```
In the first sample case, there are two cherries and they are connected with a black strand. Removing any of the strand causes cherries to get disconnected. Hence, the minimum sugar content is 1.

n the second sample case, we can keep the black strand between cherry numbered 2 and cherry numbered 3, and remove any of the red strands, which leads to a minimum sugar content of 3.

## B. Code-Eat Switcher

### Problem

Umon is a foodie coder. Do you know what two activities that he loves the most? Of course, coding and eating! He always spends the whole day doing only those two activities. However, he thinks that some times of the day are better spent coding, and others are better spent eating.

To illustrate this problem, Umon divides his day into S time slots. During the i-th time slot, if Umon codes 100% of the time, he will achieve Ci units of coding. On the other hand, if he eats 100% of the time, he will achieve Ei units of eating. But of course, Umon can also use only a fraction of the time for coding, and the remaining for eating. Formally, he will choose a real number f (0 ≤ f ≤ 1), code for f of the time, and use the remaining (1 - f) time to eat. This way, he will achieve f × Ci units of coding and (1 - f) × Ei units of eating. The total amount of coding Umon achieves for the day is simply the sum of all units of coding he achieved in each of the time slots. The total amount of eating is calculated in a similar way.

Umon needs to plan his schedule for the next D days. On the i-th day, he needs to achieve at least a total amount of Ai units of coding and Bi units of eating. For each day, determine whether there is a way for Umon to achieve his target.

### Input

The first line of input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers D and S, the number of days and the number of time slots in a day, respectively.

Then S lines follow, each describing a time slot. The i-th line contains two integers Ci and Ei, the amount of coding units achieved if Umon codes for 100% of the time slot, and the amount of eating units achieved if he eats for 100% of the time slot, respectively.

Then D lines follow, each describing a day. The i-th line contains two integers Ai and Bi, the minimal total amount of coding and eating that needs to be achieved on that day.

### 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 a string with D characters, where the i-th character is `Y` if there exists a schedule that can fulfill the target for the i-th day, otherwise it should be `N`.

### Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ci ≤ 104, for all i.
1 ≤ Ei ≤ 104, for all i.
0 ≤ Ai ≤ 108, for all i.
0 ≤ Bi ≤ 108, for all i.

1 ≤ S ≤ 2.
1 ≤ D ≤ 10.

#### Test set 2 (Hidden)

For at least TODO% of the test cases:
1 ≤ S ≤ 103.
1 ≤ D ≤ 103.

For all test cases:
1 ≤ S ≤ 105.
1 ≤ D ≤ 105.

### Sample

Sample Input
```2
4 2
3 8
6 10
0 18
3 13
10 0
7 3
1 2
4 4
4 4
0 0
```
Sample Output
```Case #1: YYNY
Case #2: Y
```

In the first sample case, there are 4 days and 2 time slots for each day.

• For day 1, Umon can just eat 100% for both time slots, and therefore achieving a total of 0 units of coding and 8 + 10 = 18 units of eating, thus reaching the target.
• For day 2, Umon can eat 100% of the time for the first time slot, and use 50% of the second time slot for coding and 50% for eating, achieving a total of 0 × 3 + 0.5 × 6 = 3 units of coding, and 1 × 8 + 0.5 × 10 = 13 units of eating, thus reaching the target.
• For day 3, it is impossible to get a total of 10 units of coding.
• For day 4, there are an infinite amount of ways to achieve the target. One possible strategy is to code 42% (and eat 58%) in the first time slot, then code 98.76% (and eat 1.24%) in the second time slot. That strategy yields a total of 0.42 × 3 + 0.9876 × 6 = 7.1856 units of coding, and 0.58 × 8 + 0.0124 × 10 = 4.764 units of eating.
Thus, the answer should be YYNY.

In the second sample case, note that the value of characteristics for the time slots may not necessarily be different from each other.

## C. Street Checkers

### Problem

Alice and Bob are playing a new virtual reality team game - Street Checkers. The game is set on an insanely long street divided into tiles which are numbered from 0 to 109(inclusive of both). At the start of the game, Alice and Bob are standing on tile number 0 and are given a random number X in range [L, R] (both ends are inclusive). Alice only jumps to odd numbered tiles, while Bob only jumps to even numbered tiles. If the number on the tile divides X, then the player landing on it has to color it with their favorite color. The game is over after tile X has been colored.

A game is considered interesting by both the players if the absolute difference between the number of tiles painted by each is not greater than 2. Help Alice and Bob find how many numbers in the interval [L, R] could make for an interesting game.

### Input

The first line of the input gives the number of test cases, T. T lines follow each containing two integers L and R, the start and end of the interval used to generate the random number X.

### 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 count of numbers in interval [L, R] which results in an interesting game for Alice and Bob.

### Limits

Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ R - L ≤ 105.

1 ≤ LR ≤ 106.

1 ≤ LR ≤ 109.

### Sample

Sample Input
```2
5 10
102 102
```
Sample Output
```Case #1: 5
Case #2: 1
```

For the first sample case, let us look at all the possible number in range [5, 10]:

• 5 - Alice would paint 2 tiles : {1, 5}, and Bob would not paint any tile. The game would be interesting since the absolute difference is 2.
• 6 - Alice would paint 2 tiles : {1, 3}, and Bob would paint 2 tiles : {2, 6}. The game would be interesting since the absolute difference is 0.
• 7 - Alice would paint 2 tiles : {1, 7}, and Bob would not paint any tile. The game would be interesting since the absolute difference is 2.
• 8 - Alice would paint 1 tile : {1}, and Bob would paint 3 tiles : {2, 4, 8}. The game would be interesting since the absolute difference is 2.
• 9 - Alice would paint 2 tiles : {1, 3, 9}, and Bob would not paint any tile. The game would not be interesting since the absolute difference is greater than 2.
• 10 - Alice would paint 2 tiles : {1, 5}, and Bob would paint 2 tiles : {2, 10}. The game would be interesting since the absolute difference is 0.
Thus, the answer for this test case is 5.

In the second sample case, we have only one number 102. Alice would paint 4 tiles : {1, 3, 17, 51} while Bob would paint 4 tiles : {2, 6, 34, 102}. The game would be interesting since the absolute difference is 0.

## Analysis — A. Cherries Mesh

### Test set 1 (Visible)

First, let's rephrase the problem: Given a complete undirected graph, where each edge has weight 1 or 2, what is the cost of the Minimum Spanning Tree? There are a few different algorithms for solving this problem, such as Prim's Algorithm and Kruskal's algorithm. Using Kruskal's Algorithm gives an O(N2 log N) solution per test case, while Prim's Algorithm gives an O(N2) solution per test case.

### Test set 2 (Hidden)

Intuitively, we want to include as many edges of weight 1 as possible. Once we have included as many such edges as we can, then we know that the remaining edges in the spanning tree will be of weight 2.

Using this idea, we have the following solution: first create a spanning forest using only edges of weight 1. We can now connect each of the components of the spanning forest together using X-1 edges of weight 2, where X is the number of components (we can always connect these components since the graph is complete).

Since we only need to print the minimum cost and not the actual minimum spanning tree, we can simplify the problem to simply counting the number of components in the graph where we only consider the edges of weight 1.

This solves the problem in O(N).

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

## Analysis — B. Code-Eat Switcher

### Test set 1 (Visible)

Let's start with the brute force way of solving the problem. We can iterate through all possible coding units for slot 1, let's say X. Now, we can calculate the coding unit left for slot 2 (Ai - X). Using this we can calculate eating unit we can achieve for both slot 1 and slot 2 and compare it with Bi. Time complexity for each test case would be O(Cmax*D).

### Test set 2 (Hidden)

Let's first solve for only 1 day. So assuming two time slots Si(Ei, Ci) and Sj(Ej, Sj) we can see that to achieve every 1 unit of eating in Si slot we are losing Ci/Ei unit of coding, similarly for Sj slot. Hence, we can observe that it's always a better choice to choose time slot Si if Ci/EiCj/Ej. Now, we have the order in which we should achieve the required eating unit.

For calculating minimum coding requirement we can maintain prefix cumulative and suffix cumulative sum of maximum coding and eating unit that can be achieved in a time slot. Then using binary search on prefix cumulative sum array, we can find out which minimum indexed time slot will give us eating more than required and we can remove the excess fraction of time for use in coding. We can compute the maximum coding unit achieved from unused time slots by using the suffix cumulative sum. This will take O(SlogS + S) preprocessing time and O(DlogS) for each test case.

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

## Analysis — C. Street Checkers

### Test set 1 (Visible)

Let's rephrase the problem into counting the number of values X within the range [L, R] that satisfies |(# of odd divisors) - (# of even divisors)| ≤ 2.

To solve this problem under the constraint that R < 106. We can simply preprocesses each X between 1 and 106 whether X is interesting or not. To find whether X is interesting, we can apply any O(√X) time algorithm finding out all divisors of X. After storing the result for each X, we build a prefix sum array F storing for counts. Thus, each query can be answered by computing F[R] - F[L-1] in constant time. The total time complexity would then be O(RmaxRmax + T), which suffices to pass the first test set.

### Test set 2 (Hidden)

We need a slightly sophisticated observation here. The intuition comes from observing that any divisor to an odd integer is still odd. For any integer X we can extract all power of 2 factors and rewrite as X=A*2X, where A is an odd integer and X is a non-negative integer.

Now, we can partition all divisors to X into sets of divisors leading with each odd divisors d1, d2, ..., dk of A:

{d1, d1*2, d1*22, ..., d1*2X},
{d2, d2*2, d2*22, ..., d2*2X},
...
{dk, dk*2, dk*22, ..., dk*2X}.

By looking at the above diagram we can infer that X has X odd divisors and X*X even divisors. The criteria to a number being interesting is now equivalent to |X*(X-1)| ≤ 2.

There are only a few cases of (X, X) pairs that satisfies the above expression:

• Case 1: X=0, X=1 or 2.
• Case 2: X=1, X can be any value.
• Case 3: X=2, X=1 or 2.
• Case 4: X=3, X=1.

So, what we really need to do here is to count the number of X's in the range [L, R] satisfying each case.

Case 1 implies that X=1 or a odd prime. One can count the number of primes within range [L, R] using Sieve of Eratosthenes. Case 2 implies that A can be any odd integer, so in this case X is in the form of (4*X+2) and hence can be counted in O(1) time. Case 3 implies that A=1 or an odd prime. One can count the number of primes within range [L/4, R/4]. Case 4 implies that X=8. Count it whenever 8 belongs to the range.

From the above case analysis, one can see that the running time is dominated by Sieve of Eratosthenes. Fortunately, we only need to use sieve method on arrays of size O(R-L+1) to count the number of odd primes within ranges [L, R] and [L/4, R/4]. If we apply sieving using numbers 2, 3, 4, ..., √R, the algorithm runs in O(T*(R - L + 1)*log(√R)) time, which suffices to pass this test set.

For a more efficient algorithm, one can sieve using prime numbers no more than √R. These prime numbers again can be obtained by a sieving algorithm. At the end you will get an algorithm that runs in O(√R log log √R) + O((R - L + 1) log log √R) time per test case.

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