# Google Kick Start Archive — Round H 2019 problems

## Overview

Thank you for participating in Kick Start 2019 Round H.

Cast

H-Index: Written and prepared by Himanshu Jaju and prepared by Bartosz Kostka.

Diagonal Puzzle: Written by Max Ward and prepared by Jonathan Irvin Gunawan.

Elevanagram: Written by Bartosz Kostka and prepared by Zhang Chen.

Solutions, other problem preparation, reviews and contest monitoring by Bartosz Kostka, Himanshu Jaju, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Sadia Atique, Raihat Zaman Neloy, Viplav Kadam, Yossi Matsumoto, Yang Xiao, and Zhang Chen.

Analysis authors:

• Elevanagram: Zhang Chen

## A. H-index

### Problem

It is important for researchers to write many high quality academic papers. Jorge has recently discovered a way to measure how impactful a researcher's papers are: the H-index.

The H-index score of a researcher is the largest integer h such that the researcher has h papers with at least h citations each.

Jorge has written N papers in his lifetime. The i-th paper has Ai citations. The number of citations that each paper has will never change after it is written. Please help Jorge determine his H-index score after each paper he wrote.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing N, the number of papers Jorge wrote.

The second line contains N integers. The i-th integer is Ai, the number of citations the i-th paper has.

### 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 space-separated list of integers. The i-th integer is the H-index score after Jorge wrote his i-th paper.

### Limits

Time limit: 50 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ai ≤ 105.

1 ≤ N ≤ 1000.

1 ≤ N ≤ 105.

### Sample

Sample Input
```2
3
5 1 2
6
1 3 3 2 2 15
```
Sample Output
```Case #1: 1 1 2
Case #2: 1 1 2 2 2 3
```
In Sample Case #1, Jorge wrote N = 3 papers.
• After the 1st paper, Jorge's H-index score is 1, since he has 1 paper with at least 1 citation.
• After the 2nd paper, Jorge's H-index score is still 1.
• After the 3rd paper, Jorge's H-index score is 2, since he has 2 papers with at least 2 citations (the 1st and 3rd papers).

In Sample Case #2, Jorge wrote N = 6 papers.
• After the 1st paper, Jorge's H-index score is 1, since he has 1 paper with at least 1 citation.
• After the 2nd paper, Jorge's H-index score is still 1.
• After the 3rd paper, Jorge's H-index score is 2, since he has 2 papers with at least 2 citations (the 2nd and 3rd papers).
• After the 4th paper, Jorge's H-index score is still 2.
• After the 5th paper, Jorge's H-index score is still 2.
• After the 6th paper, Jorge's H-index score is 3, since he has 3 papers with at least 3 citations (the 2nd, 3rd and 6th papers).

## B. Diagonal Puzzle

### Problem

Kibur has made a new puzzle for you to solve! The puzzle consists of an N by N grid of squares. Each square is either black or white. The goal of the puzzle is to make all the squares black in as few moves as possible.

In a single move, you may choose any diagonal of squares and flip the color of every square on that diagonal (black becomes white and white becomes black). For example, the 10 possible diagonals for a 3 by 3 grid are shown below.

```/..      ./.      ../      ...      ...
...      /..      ./.      ../      ...
...      ...      /..      ./.      ../

...      ...      \..      .\.      ..\
...      \..      .\.      ..\      ...
\..      .\.      ..\      ...      ...
```

Given the initial configuration of the board, what is the fewest moves needed to make all the squares black? You are guaranteed that it is possible to make all the squares black.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N, the size of the grid. Then, N lines follow, each containing N characters that describe the initial configuration of the grid. The c-th character on the r-th line is the character `.` (ASCII number 46) if the square in the r-th row and c-th column is initially white. Otherwise, it is `#` (ASCII number 35), indicating that it is black.

### 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 fewest moves needed to make all the squares black.

### Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
You are guaranteed that it is possible to make all the squares black.

2 ≤ N ≤ 8.

2 ≤ N ≤ 100.

### Sample

Sample Input
```3
3
..#
#.#
#..
5
.####
#.###
##.##
###.#
#####
2
##
##
```
Sample Output
```Case #1: 3
Case #2: 2
Case #3: 0
```
In sample case #1, the fewest moves needed is 3, as shown below:
```..#    ..#    .##    ###
#.# -> ..# -> #.# -> ###
#..    ##.    ##.    ###
```
In sample case #2, the fewest moves needed is 2, as shown below:
```.####    #####    #####
#.###    #####    #####
##.## -> ##### -> #####
###.#    #####    #####
#####    ####.    #####
```
In sample case #3, all the squares in the grid are already black, so the answer is 0.

## C. Elevanagram

### Problem

It is a well known fact that a number is divisible by 11 if and only if the alternating sum of its digits is equal to 0 modulo 11. For example, 8174958 is a multiple of 11, since 8 - 1 + 7 - 4 + 9 - 5 + 8 = 22.

Given a number that consists of digits from 1-9, can you rearrange the digits to create a number that is divisible by 11?

Since the number might be quite large, you are given integers A1, A2, ..., A9. There are Ai digits i in the number, for all i.

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains the nine integers A1, A2, ..., A9.

### 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 `YES` if the digits can be rearranged to create a multiple of 11, and `NO` otherwise.

### Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ A1 + A2 + ... + A9.

#### Test set 1 (Visible)

0 ≤ Ai ≤ 20, for all i.

#### Test set 2 (Hidden)

0 ≤ Ai ≤ 109, for all i.

### Sample

Sample Input
```6
0 0 2 0 0 1 0 0 0
0 0 0 0 0 0 0 0 12
0 0 0 0 2 0 1 1 0
3 1 1 1 0 0 0 0 0
3 0 0 0 0 0 3 0 2
0 0 0 0 0 0 0 1 0
```
Sample Output
```Case #1: YES
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: YES
Case #6: NO```
• In Sample Case #1, the digits are `336`, which can be rearranged to `363`. This is a multiple of 11 since 3 - 6 + 3 = 0.
• In Sample Case #2, the digits are `999999999999`, which is already a multiple of 11, since 9 - 9 + 9 - 9 + ... - 9 = 0.
• In Sample Case #3, the digits are `5578`, which cannot be rearranged to form a multiple of 11.
• In Sample Case #4, the digits are `111234`, which can be rearranged to `142131`. This is a multiple of 11 since 1 - 4 + 2 - 1 + 3 - 1 = 0.
• In Sample Case #5, the digits are `11177799`, which can be rearranged to `19191777`. This is a multiple of 11 since 1 - 9 + 1 - 9 + 1 - 7 + 7 - 7 = -22 (which is 0 modulo 11).
• In Sample Case #6, the only digit is `8`, which cannot be rearranged to form a multiple of 11.

## Analysis — A. H-index

### Test set 1 (Visible)

For a set of papers, let's define a function score(x), which denotes the number of papers in the set with citations at least x. We can calculate the score for every integer x ≤ n, where n is the number of papers in the set. For each set of papers, the answer is maximum x such that score(x) ≥ x. We can store the counts of each of the citation numbers in the input in an array, and calculate cumulative sum to find the score for any x.

We need to find the maximum x where score(x) ≥ x, each time a new paper is added. We can find that using the approach mentioned above in O(max(A)) time, where max(A) is the maximum citation number in the set of papers. An observation here is, we can consider all citations ≥ N as N, which allows us to find H-index for any set of papers in O(N). This leads to a total time complexity of O(N2) per test case, which is sufficient for test set 1.

### Test set 2 (Hidden)

For test set 2, we initialize the H-index with 0, and after adding each paper, we need to update the current H-index. We can use a minimum priority queue data structure to store the citation numbers. As we go through each of the papers, we keep updating the current H-index. We also keep updating the priority queue so that it only contains numbers greater than the current H-index and remove the rest. For each new paper, we can follow these steps

1. If the current citation number is bigger than the current answer, add it in the priority queue
2. Remove all the citation numbers from the priority queue which is not greater than the current answer
3. If the size of priority queue is not less than the current answer + 1, increment the answer by 1

A single operation of priority queue takes O(logN) time, and a number is added and removed at most once. This leads to a total time complexity of O(N × logN) per test case, which is sufficient for test set 2.

A solution with linear time complexity is also possible, if we store the citation numbers in an array or a hashtable to calculate the answer. This is left as an exercise for the readers.

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

## Analysis — B. Diagonal Puzzle

### Test set 1 (Visible)

For a square grid of size N, there's total 2 × N − 1 diagonals that are parallel to the main diagonal, and 2 × N − 1 diagonals that are perpendicular to the main diagonal.

For each of the diagonals parallel to the main diagonal, we can fix either we would flip them or not, and then check if each of the perpendicular diagonals contain cells of the same color. If all cells are the same for each of the perpendicular diagonals, then this would lead to a solution. If all white, just flip the whole diagonal, if not, nothing is necessary.

There are total 22 × N − 1 possible combinations for flipping diagonals parallel to the main diagonal, and we can check if the perpendicular diagonals have all same coloured cells in O(N2) time complexity, which leads to a total time complexity of O(22 × N − 1 × N2) per test case, which is sufficient for test set 1.

### Test set 2 (Hidden)

One interesting observation is that if we decide whether we would flip the two largest diagonals or not (in the case where N is odd, we decide whether we flip the largest diagonal in one direction, and the second largest diagonal in the other direction), we can pick all other diagonals to flip deterministically. The diagonals are shown for grids of size N = 6 and N = 7 below.

```\..../ \......
.\../. .\..../
..\/.. ..\../.
../\.. ...\/..
./..\. .../\..
/....\ ../..\.
./....\
```

There are four choices for flipping/not flipping the two chosen diagonals. And for each of these choices, we can go through all other diagonals in the grid. For each of these other diagonals, we can check if the square where it intersected with one of the chosen diagonals is white. If it is white, we need to flip this diagonal, otherwise not. If after all the flips, the final grid is all black squares, then we have a possible answer. We take the minimum flips of the four possible choices.

There are 4 choices for the flipping of the two chosen diagonals. And for each of the choices, the flipping of all other diagonals, and finally checking for all black cells can be done in O(N2) time, which leads to a total time complexity of O(N2), which is sufficient for test set 2.

An alternative solution is to convert this problem into a variant of 2-coloring. Each of the cells in the grid is shared by two diagonals. If a cell is white, either one of them needs to be flipped to make this cell black. Otherwise, none of these two diagonals needs to be flipped. For this problem, we can consider each diagonal as a vertex of a graph, and and the squares in the grid are the edges between the two diagonals that affect that square. If the square is initially black, then the endpoints of the corresponding edge must be colored the same, else they must be colored differently. By color, we mean chosen to be flipped or not flipped. So we should color in such a way that all conditions for all edges in the graph are satisfied and we have the minimum number of flips possible. This can be done with a DFS for each component of the graph.

There are total O(N2) edges in the graph. Building the graph and solving it can be done in O(|Edges|). This leads to a time complexity of O(N), which is sufficient for test set 2.

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

## Analysis — C. Elevanagram

### Test set 1

We need to divide each digits to two partitions: positive partition and negative partition, where positive partition means the digit is on the odd index (be calculated as add), and negative partition means the digit is in the even index (be calculated as minus).

We can use dynamic programming to solve test set 1. Let dp[i][j][k] denote if it is possible to achieve the state that when we are considering digits 1, 2, ... i, the current number of digits in the positive partition is j and the current sum modulo 11 is k. Then for each digit i, we can put 0, 1, ..., Ai digits into the positive partition, and calculate if the current state is possible. We want to calculate dp[sum(A)/2], where sum(A) means the total sum of all elements in array A.

The time complexity is O(9 * sum(A) * 11 * max(A)), which fits the time limit for test case 1. Here max(A) means the maximum of all elements in array A.

### Test set 2

Assume the positive number of digits i is Pi, and negative number of digits i is Ai - Pi. Then, we will have the following three equations:

```  (1) Σ Pi = ceil(sum(A) / 2)
(2) Σ i × (Pi - (Ai - Pi)) % 11 = 0
(3) 0 ≤ Pi ≤ Ai
```

In order to solve this, initially we can put half the number of each digits to be in positive partition (e.g. Pi = Ai / 2, take care of odd numbers), and then try to adjust each Pi to satisfy equation (2). For each i, we can adjust its Pi from -Ai / 2 to Ai / 2.

We can prove the two following conclusions:

1. If there are at least two numbers of Ai ≥ 10, then the solution must exist.

This is very easy to prove. We can only adjust these two digits from -5 to 5, and each adjustment will result in a different remain value of modulo 11. Thus, we will get 0 finally.

2. If there are at least three numbers of Ai ≥ 6, then the solution must exist.

To prove this, we can prove that:

```  For any 1 ≤ i < j < k ≤ 9, 0 ≤ r ≤ 10, the following equations:
(1) (i * x1 + j * x2 + k * x3) % 11 = r
(2) x1 + x2 + x3 = 0
(3) -3 ≤ xi ≤ 3
will have a valid solution.
```

This can be proved by iterating all possible situations, where the total number is 9C3 * 11 * 7 * 7 = 45276, quite small.

According to these two conclusions, if there are at least two numbers ≥ 10 or at least three numbers ≥ 6, we can return YES immediately. Otherwise, there are at most one value ≥ 10, and at most two values ≥ 6, we can calculate all possible situations, where in the worst case time complexity is O(67 * 10) = O(2799360) which fits the time limit for test case 2.

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