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:
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.
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.
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.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ L ≤ 50.
The two strings A and B will consist only of the characters A and B.
No additional constraints.
6 3 ABB BAB 3 BAB ABB 6 CATYYY XXXTAC 9 SUBXXXXXX SUBBUSUSB 4 AAAA AAAA 19 PLEASEHELPIMTRAPPED INAKICKSTARTFACTORY
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.
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.
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.
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.
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.
Li ≠ Lj for all i ≠ j.
1 ≤ Ai < Bi ≤ V, 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.
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
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.
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.
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.
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.
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.
2 2 3 4 2 3 9
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.
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 As
and the same number of Bs.
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.
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.
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.
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}.
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 K ≤ N, 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 as? To make a rough count, let's consider only the
palindromes with length exactly N. Of the 200 letters between the as, 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.