# Google Kick Start Archive — Round F 2018 problems

## Overview

This Kickstart round began with Common Anagrams, which was a simple strings problem. Then came Specializing Villages, which required some good graph theory insights. Finally, we had Palindromic Sequence, whose large dataset involved an elegant observation on the possible characters of the required string.

Thanks to everyone who participated!

Cast

Problem A (Common Anagrams): Written by Kevin Tran and prepared by Satyaki Upadhyay‎.

Problem B (Specializing Villages): Written and prepared by Lin Jin.

Problem C (Palindromic Sequence): Written and prepared by Kevin Tran.

Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Ian Tullis, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Satyaki Upadhyay, Shashank Gupta and Yang Xiao.

Analysis authors:

• Common Anagrams: Jonathan Irvin Gunawan
• Specializing Villages: Lin Jin
• Palindromic Sequence: Kevin Tran

## A. Common Anagrams

### Problem

Ayla has two strings A and B, each of length L, and each of which is made of uppercase English alphabet letters. She would like to know how many different substrings of A appear as anagrammatic substrings of B. More formally, she wants the number of different ordered tuples (i, j), with 0 ≤ i ≤ j < L, such that the i-th through j-th characters of A (inclusive) are the same multiset of characters as at least one contiguous substring of length (j - i + 1) in B.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line, containing L: the length of the string. The next two lines contain one string of L characters each: these are strings A and B, in that order.

### 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 answer Ayla wants, as described above.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ L ≤ 50.

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

The two strings A and B will consist only of the characters `A` and `B`.

### Sample

Sample Input
```6
3
ABB
BAB
3
BAB
ABB
6
CATYYY
XXXTAC
9
SUBXXXXXX
SUBBUSUSB
4
AAAA
AAAA
19
INAKICKSTARTFACTORY
```
Sample Output
```Case #1: 5
Case #2: 6
Case #3: 6
Case #4: 6
Case #5: 10
Case #6: 9
```

In Sample Case #1, L = 3, A = `ABB`, and B = `BAB` There are 6 substrings of A:

• `A`. The substring `A` in B is (trivially) an anagram.
• `B`. The substring `B` in B is (trivially) an anagram.
• `B`. The substring `B` in B is (trivially) an anagram.
• `AB`. The substring `AB` in B is (trivially) an anagram.
• `BB`. There is no corresponding anagrammatic substring in B.
• `ABB`. The substring `BAB` in B is an anagram.

In total, there are 5 substrings with a corresponding anagrammatic substring in B, so the answer is 5.

In Sample Case #2, note that it is the same as Sample Case #1, except that A and B are swapped. This changes the answer to 6!

In Sample Case #3, note that the substring `CAT` in A has the corresponding substring `TAC` in B which is an anagram. This still counts, even though the strings are at different indices in their respective strings.

In Sample Case #4, note that although the substring `SUB` in A has several corresponding substrings in B which are anagrams, it only counts once.

In Sample Case #5, note that every substring of A has a corresponding anagrammatic substring in B, so the answer is 10.

## B. Specializing Villages

### Problem

The countryside of Kickstartia consists of V villages, connected by E bidirectional roads. Because the citizens appreciate diversity in their road construction, no two roads have the same length. Each road connects exactly two villages, and no two roads connect the same two villages.

The new king, eager to show off his progressiveness, would like to create a plan in which each village will specialize in producing exactly one food: either fruit or vegetables. If a village produces fruit, then they will find a shortest path (perhaps using multiple roads) to some village that produces vegetables. Similarly, if a village produces vegetables, then they will find a shortest path to some village that produces fruit.

To keep things running smoothly, the king would like to minimize the average of the distances that each village needs to travel to get the food that it does not produce.

There could be many plans that minimize this average distance, so the king would like you to tell him how many there are. Two plans are different if there is a village that produces fruit in one plan, but vegetables in the other. The king guarantees that it is possible to find a plan which allows each village to get both fruit and vegetables.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line, containing two integers V and E: the number of villages, and the number of roads, respectively. The villages are labeled from 1 to V. E lines follow; the i-th of these lines contains three integers Ai, Bi and Li, indicating that the i-th road connects village Ai to village Bi and has length Li.

### 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 answer the king wants, as described above.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ E ≤ min(1000, V * (V - 1) / 2).
0 ≤ Li ≤ 105, for all i.
LiLj for all i ≠ j.
1 ≤ Ai < BiV, for all i.
(Ai, Bi) ≠ (Aj, Bj) for all i ≠ j.
There is at least one plan that allows every village to get both types of food.

2 ≤ V ≤ 10.

2 ≤ V ≤ 50.

### Sample

Sample Input
```2
3 3
1 2 1
1 3 6
2 3 4
6 5
1 2 6
3 4 0
5 6 7
3 5 1
4 6 2
```
Sample Output
```Case #1: 2
Case #2: 16
```

In Sample Case #1, one possible plan is to make villages 1 and 3 produce fruit and make village 2 produce vegetables. Village 1 and 2 can travel to each other to get to the food they lack, so they both have to travel distance of 1. Village 3 needs to travel to village 2 to get vegetables, traveling a distance of 4. In total, the average distance is (1 + 1 + 4)/3 = 2, which is the minimum possible. There is one other optimal plan (in which villages 1 and 3 produce vegetables and village 2 produces fruit), so the final answer is 2.

In Sample Case #2, there are 16 possible plans. One way is to have villages 1, 3 and 5 produce fruit while villages 2, 4 and 6 produce vegetables. Village 1 and 2 must travel to each other to get to the food they lack. Villages 3 and 5 can travel to village 4 to get vegetables, while villages 4 and 6 can travel to village 3 to get fruit. The average distance is (6 + 6 + 0 + 1 + 0 + 2)/6 = 2.5, which turns out to be the minimum possible. Even if two villages are connected by a road of length 0, they are considered to be distinct villages.

## C. Palindromic Sequence

### Problem

Hannah is working on a new language which consists only of first L lowercase letters of the English alphabet. She is obsessed with palindromes, which are words that read the same forward and backward, e.g. `hannah` and `civic`. She has written down all of the words in her language of length at most N, that are also palindromes.

Now, she is interested in finding the length of the word that is lexicographically Kth smallest among all the words she has written. A word composed of ordered letters a1, a2, ..., ap is lexicographically smaller than word b1, b2, ..., bq if ai < bi, where i is the first index where characters differ in the two words. Also, a prefix of a word is considered lexicographically smaller than the word itself. For example, the following words are arranged in lexicographically increasing order: `a`, `aa`, `aba`, `cabac`, `d`.

### 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 three integers L, N, and K, 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 length of the lexicographically Kth smallest palindromic word among all palindromic words of length at most N in Hannah's language.
If no such word exists, output `0`.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ L ≤ 26.
1 ≤ K ≤ 1012.

1 ≤ N ≤ 100.

1 ≤ N ≤ 1012.

### Sample

Sample Input
```2
2 3 4
2 3 9
```
Sample Output
```Case #1: 3
Case #2: 0
```

In Sample Cases #1 and #2, Hannah's language consists only of the letters `a` and `b`. All the palindromic words of length at most 3 in her language, in lexicographic order, are: `a`, `aa`, `aaa`, `aba`, `b`, `bab`, `bb` and `bbb`.

In Sample Case #1, the fourth-smallest word is `aba`, which is 3 characters long, so we output 3.

In Sample Case #2, K exceeds the total number of possible words, and hence we output 0.

## Common Anagrams: Analysis

### Small and Large dataset

We can create a boolean function f(i, j, k, l) that returns whether the substring from the i-th through the j-th characters of A (inclusive) is anagrammatic to the substring from the k-th through the l-th characters of B (inclusive).

To do this for the Small dataset, we only need to check that both substrings contain the same number of `A`s and the same number of `B`s.

To do this for the Large dataset, we can loop from i to j to get the number of occurrences of each character in A[i .. j]. Similarly, we also loop from k to l to get the occurrences of each character in B[k .. l]. We then check whether each character occurs the same number of times in the two substrings.

We want to return the number of ordered pairs (i, j) such that there exists an ordered pair (k, l) satisfying f(i, j, k, l). Since computing a single value of f(i, j, k, l) takes O(L), this solution runs in O(L5) time. We can optimize this by observing that if j - i ≠ l - k, then f(i, j, k, l) will certainly return false. Therefore, for each value of (i, j, k) we only need to check f(i, j, k, k + (j - i)). This removes one O(L) loop and improves the algorithm to O(L4) time.

### Further improvements

Although O(L4) is fast enough, we can improve the algorithm further. Instead of looping through all substrings of B for each substring of A, we can do some preprocessing. Before we even process A, we can loop through all substrings of B. For each substring, we count the occurrences of each character and store it in a hashset. Note that this can be done in O(L2) time, since we can use the character occurrences of B[i .. j] to compute the character occurrences of B[i .. j+1].

Once the preprocess is complete, we can loop through all substrings of A. Simiarly, for each substring, we count the occurrences of each character. We then check whether these occurrences of characters are present in our set. If they are, we can increment our answer counter. We can also do this in O(L2) time.

Therefore, this solution runs in O(L2) time overall.

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

## Specializing Villages: Analysis

### Small dataset

For the Small dataset, we can enumerate all plans, find the average of the distances for the villages, and count the plans with a minimal average distance.

### Large dataset

If each village can get the other food it needs from its nearest neighbor, then the average distance is clearly minimized. We will show that it is possible to construct this situation.

For each village v, let l(v) be the numerical label of v, r(v) be the shortest of the roads that have v as an endpoint, d(v) be the distance of r(v), and f(v) be the other village to which r(v) connects v. We first sort the villages by increasing d(v). Since two villages might share the same d(v), we break ties by increasing l(v).

Then, we handle each village in sorted order. We assign v the opposite food of f(v); if f(v) does not have a food assigned, we can assign either food to v. How do we know this will not cause problems later in the process? Well, this situation can only happen when d(f(v)) ≥ d(v). But we know that r(v) connects f(v) and v, so d(f(v)) ≤ d(v), and thus d(f(v)) = d(v) in this case, which implies r(f(v)) = r(v) and l(f(v)) > l(v). Since r(f(v)) = r(v), f(f(v)) = v, so f(v) will be assigned the opposite food of v when we get to it.

In our approach, some villages may have their food choices forced by the food choices of other villages, whereas some villages may be able to choose either food. So, the count of optimal plans is 2N, where N is the number of villages that can choose. N is equal to the size of {v | f(f(v)) = v and l(f(v)) > l(v)}.

Roads with length 0 pose a special case. If a 0-length road connects villages x and y, any village v other than x and y with f(v) in {x, y} has two choices, since it can get one food through r(v) and the other from a combination of r(v) and the 0-length road. So, with a 0-length road present, the answer will be 2N, where N is the size of {v | f(f(v)) = v and l(f(v)) > l(v)} ∪ {v | d(v) > 0 and d(f(v)) = 0}.

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

## Analysis — C. Palindromic Sequence

To solve the Small dataset, we will build up the palindrome one letter at a time. Suppose we know the first X letters of the Kth lexicographically least palindrome. Call this prefix of the answer S. We can guess the next letter and see how many palindromes there are with the new prefix (we will address this computation shortly). If there are more than K, then we know we need to guess a lexicographically smaller letter. Let P(S) denote the number of palindromes of Hannah's language that have S as a prefix. Then we are looking for the lexicographically largest character c such that P(S + c) ≤ K. Naively, we have to make O(NL) guesses.

So how do we actually calculate the number of possible continuations? Fortunately, the bounds are Small enough that we don't need to do anything sophisticated. For every possible length M, check and see if the current prefix S is consistent with a palindrome of length M. If it is, then there are LD possible palindromes of length M, where D = max(0, floor((M+1)/2) - X). d represents the number of characters that can be freely chosen (the rest are fixed to keep the string a palindrome). This can be done naively in O(N2) time. In total, the Small can be solved in O(N3L) time.

To solve the Large dataset, notice that when KN, the answer is a string that consists of the letter `a` repeated K times. When K > N, it's important to notice that the answer is very close to N.

For example, consider the case when N = 105 and L = 2. How many palindromes begin and end with 49900 letter `a`s? To make a rough count, let's consider only the palindromes with length exactly N. Of the 200 letters between the `a`s, the first 100 are unconstrained, while the last 100 have to match the corresponding letter in the first 100. In total this is 2100 different palindromes, which far exceeds that maximum bound for K (1018 is about 260).

The example above can be generalised to state that whenever K > N, the Kth palindrome will begin and end with at least N-logL(K) copies of the letter `a`, leaving at most 2*logL(K) letters in the middle that might not be the letter `a`. The algorithm in the Small dataset can be adapted to solve the Large dataset after these observations have been made. 2*logL(K) is no more than 100, so this has a similar running time to the Small dataset.

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

First
alexwice 3:26
vicennial 4:39
praran26 4:41
ciphereck 4:55
ivanzuki 5:04

First
alexwice 3:26
vicennial 4:39
praran26 4:41
ivanzuki 5:04
vsp4 5:18

First
arknave 14:35
pedrosorio 21:46
pandusonu 26:46
jonno 27:22
dheer1206 28:14

First
mattioli 32:12
Mahmoudian 32:15
nuip 33:42
nemopaper 37:13
famafka 37:39

First
Mahmoudian 73:29
nuip 78:09