This Kickstart round was easier than our previous rounds and began with Big Buttons, which was a simple problem solvable by the Trie data structure. Then came Mural, whose large dataset required an interesting insight, but a rather easy implementation. Finally, we had Let Me Count The Ways, whose large dataset involved the use of the inclusion-exclusion principle.
Thanks to everyone who participated!
Cast
Problem A (Big Buttons): Written by Akashdeep Nain and prepared by Lalit Kundu.
Problem B (Mural): Written by Zhang Che and prepared by Kevin Tran.
Problem C (Let Me Count The Ways): Written by Chao Li and prepared by Yan Li.
Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Anirudh GP, Celestine Lau, Ian Tullis, Jonathan Irvin Gunawan, Himanshu Jaju, Kevin Tran, Lalit Kundu, Satyaki Upadhyay, Tony Wong and Yan Li.
Analysis authors:
You are a contestant on a popular new game show and are playing for the grand prize!
There are two big buttons, a red one and a black one. You will make a sequence of exactly N button presses.
There are lots of different sequences of presses you could make, but there are P forbidden prefixes, each of length no greater than N. If you make a sequence of presses which begins with any of the forbidden sequences, you will not win the grand prize. It is fine for your sequence to contain one or more forbidden prefixes as long as they do not appear at the start of your sequence.
A winning sequence must consist of exactly N button presses and must not begin with one of the forbidden prefixes. How many different winning sequences are there?
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with a line containing two integers N and P, as described above.
Then, there are P more lines, each of which contains a string of between 1 and N characters, inclusive,
describing one of the forbidden sequences of presses. An R represents pressing
the red button, whereas a B represents pressing the black button.
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 winning sequences, as desribed above.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ P ≤ min(2N, 100).
Each forbidden prefix is between 1 and N characters long, inclusive.
No two forbidden prefixes will be the same.
1 ≤ N ≤ 10.
1 ≤ N ≤ 50.
3 3 2 BBB RB 5 1 R 4 3 R B RBRB
Case #1: 5 Case #2: 16 Case #3: 0
In the first case, you must make a sequence of 3 presses. There are 8 possible sequences of three presses, but some of them will cause you to lose the game. They are listed below:
RBB. This is forbidden since it starts with the first forbidden sequence (RB).RBR. This is forbidden since it starts with the first forbidden sequence (RB).BBB. This is forbidden since it starts with the second forbidden sequence (BBB).
In the second case, you must make a sequence of 5 presses. There is only one forbidden sequence,
which is R. This means that the first press must be B, and the next
4 presses can be either button. This gives a total of 16 different button presses.
In the third case, you must make a sequence of 4 presses. There are three forbidden sequences,
but since every possible sequence begins with either R (the first forbidden sequence) or
B (the second forbidden sequence), there are no winning sequences.
So the answer is 0.
1 50 5 BRBRBBBRBRRRBBB BRBRBRRRBRRRBRB BBBRBBBRBRRRBBB BRBRBRRRBRRRB BRBRBBBRBBBRB
Case #1: 1125556309458944
Thanh wants to paint a wonderful mural on a wall that is N sections long. Each section of the wall has a beauty score, which indicates how beautiful it will look if it is painted. Unfortunately, the wall is starting to crumble due to a recent flood, so he will need to work fast!
At the beginning of each day, Thanh will paint one of the sections of the wall. On the first day, he is free to paint any section he likes. On each subsequent day, he must paint a new section that is next to a section he has already painted, since he does not want to split up the mural.
At the end of each day, one section of the wall will be destroyed. It is always a section of wall that is adjacent to only one other section and is unpainted (Thanh is using a waterproof paint, so painted sections can't be destroyed).
The total beauty of Thanh's mural will be equal to the sum of the beauty scores of the sections he has painted. Thanh would like to guarantee that, no matter how the wall is destroyed, he can still achieve a total beauty of at least B. What's the maximum value of B for which he can make this guarantee?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing an integer N. Then, another line follows containing a string of N digits from 0 to 9. The i-th digit represents the beauty score of the i-th section of the wall.
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 maximum beauty score that Thanh can
guarantee that he can achieve, as described above.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
2 ≤ N ≤ 100.
For exactly 1 case, N = 5 × 106; for the other T - 1 cases, 2 ≤ N ≤ 100.
4 4 1332 4 9583 3 616 10 1029384756
Case #1: 6 Case #2: 14 Case #3: 7 Case #4: 31
In the first sample case, Thanh can get a total beauty of 6, no matter how the wall is destroyed. On the first day, he can paint either section of wall with beauty score 3. At the end of the day, either the 1st section or the 4th section will be destroyed, but it does not matter which one. On the second day, he can paint the other section with beauty score 3.
In the second sample case, Thanh can get a total beauty of 14, by painting the leftmost section of wall (with beauty score 9). The only section of wall that can be destroyed is the rightmost one, since the leftmost one is painted. On the second day, he can paint the second leftmost section with beauty score 5. Then the last unpainted section of wall on the right is destroyed. Note that on the second day, Thanh cannot choose to paint the third section of wall (with beauty score 8), since it is not adjacent to any other painted sections.
In the third sample case, Thanh can get a total beauty of 7. He begins by painting the section in the middle (with beauty score 1). Whichever section is destroyed at the end of the day, he can paint the remaining wall at the start of the second day.
To celebrate the anniversary of Googleland, N couples are going to go for a boat ride in a rowboat. The rowboat is very long, but it is only one person wide, so the people will sit in a line from front to back.
However, during a rehearsal of the voyage, the boat did not move! After investigating, the organizers found that some newlywed couples were not rowing, but writing love poems for each other the whole time. Specifically, there are M pairs of newlywed couples. If the two members of a newlywed couple are sitting next to each other, they will be so busy writing poems that they will not row.
Now the organizers have come to you, the smartest person in Googleland, to ask, how many possible ways are there to arrange all 2N people on the rowboat, such that for each of the M newlywed couples, the two members are not sitting next to each other? Two ways are different if there is some position in the boat at which the two ways use different people. Notice that for the purpose of counting the number of ways, the two members of a couple are not considered to be interchangeable. Since the number can be very large, the organizers only want to know the value of the answer modulo 1000000007(109+7).
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers N and M 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 number of possible arrangements,
modulo 1000000007(109+7).
1 ≤ T ≤ 100.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
1 ≤ M ≤ N ≤ 100.
1 ≤ M ≤ N ≤ 100000.
5 2 1 2 2 3 1 3 2 10 5
Case #1: 12 Case #2: 8 Case #3: 480 Case #4: 336 Case #5: 560963525
In Sample Case #1, there are 2 couples. To make the
description simpler, we use the characters A and a to represent the
newlywed couple, and B and b to represent the other couple.
Per the rules of the problem, A and a cannot be adjacent.
There are 12 ways to arrange the four people:
ABab ABba AbaB AbBa
aBAb aBbA abAB abBA
BAba BabA bABa baBA
In Sample Case #2, both two couples are newlywed couples, so A and
a cannot be adjacent, and B and
b cannot be adjacent. They can be arranged in the following 8 ways:
ABab AbaB aBAb abAB
BAba BabA bABa baBA
Since we have 2 choices at every step, there are 2N possible strings of length N. We can generate all of these strings in O(2N) time using a naive recursion. For each string, we need to check if any of the P strings is its prefix. A simple implementation of the above would run in O(2N × P × N) time for each case. Since N ≤ 10 in this dataset, this is fast enough.
In this dataset, since N can be as large as 50, it is not feasible to generate all 2N strings. The main idea in solving the Large dataset is to find the number of invalid strings of length N and subtract it from the total number of strings (2N).
If a forbidden prefix has length L, we have 2(N - L) invalid strings of length N with that prefix. Also, if we have two strings A and B, and A is a prefix of B, then all strings that have B as their prefix will also have A as their prefix. So we can remove all forbidden prefixes that themselves begin with a different forbidden prefix to avoid overcounting the sum of invalid strings.
We can now easily count the sum of invalid strings by finding the number of invalid strings for each remaining forbidden prefix. We can remove redundant forbidden prefixes in O(P × P × N) time, and find the counts of strings with the remaining forbidden prefixes in O(P × N) time, so the overall running time is O(P2N). This is fast enough to solve the Large data set, but can you see how to improve the first step to O(P × N) time by using a trie?
We can observe that we will have painted ceil(N/2) sections in the end, and all these sections would form a contiguous subarray of the input array. Since painting and destroying is done alternatively, it might not be possible to paint any subarray of our choice. Our objective is to find the maximum subarray sum among the set of "paintable" subarrays.
An intuitive approach would rely on
Dynamic Programming and try to define a DP state that could
encapsulate the state of the painted and the destroyed sections at any point in time.
Note that painted section is contiguous, and the destroyed sections are prefixes and suffixes of
the input array.
Hence, we can define f(i, j, l, r) as the maximum possible achievable score if i and
j are the lengths of the destroyed prefix and suffix, respectively; whereas l and
r denote the left and the right boundaries of the painted subarray. A recurrence can easily
be derived by considering at most four further possibilities: we have two
ways to extend the mural (by painting the section either to the left or to the right of the already
painted boundary), and two ways to extend the destroyed part (either the prefix or the suffix).
Note that it would seem that there are O(N4) different valid states in the above
approach, but that is not the case since the sum of lengths of painted and destroyed parts is always
the same. We can get rid of the index of the right boundary of the painted subarray (i.e. variable r),
as it can be implicitly derived from the variables i and j.
The overall complexity of this approach is O(N3) and that will suffice for the
Small dataset.
The solution to the Large dataset relies on an interesting observation that all possible contiguous subarrays of length ceil(N/2) are "paintable". If we can prove this fact, we can simply do an O(N) rolling window approach over all such subarrays and output the maximum possible sum.
Let's think of an intuitive way to prove this. Say, if we paint the i-th section on the first
day, what could be the smallest possible index of the left boundary of the mural in the worst case?
To achieve the smallest possible index, we will always extend the boundary on the left side; and
in the worst case the flood can always extend the prefix, allowing us to paint only the
indices after index ceil(i/2)(inclusive). And similarly, there would be an upper limit on
the maximum possible index of the right boundary.
This means that given the desirable left boundary of the mural, we can figure out the "central point"
from which we would begin painting. Now, irrespective of the sequence of destructions, we can always
meet the desirable left boundary by always extending our subarray to the left whenever a section on the
left is destroyed. Similar arguments can be applied to the right boundary.
We can solve the Small dataset using dynamic programming. Let f(x, y, z) (x and y are non-negative integers, while z is 0 or 1) be the number of ways to arrange a seating order for x non-newlywed people and y newlywed couples (thus the total is x + 2y people and seats), such that:
The base case of this function occurs when there are no people left (i.e. x = y = 0), then f(x, y, z) = 1. Otherwise, f(x, y, 0) can be defined recursively as follows:
Therefore, f(x, y, 0) = x × f(x - 1, y, 0) + 2 × y × f(x + 1, y - 1, 1). The cases for f(x, y, 1) are similar, except that we can't put one of the x non-newlywed people in the first seat. Therefore, f(x, y, 1) = (x - 1) × f(x - 1, y, 0) + 2 × y × f(x + 1, y - 1, 1).
This dynamic programming solution runs in O(N × M) space and time.
We can solve the Large dataset using the inclusion-exclusion principle. Since M can be up to 100000, it is infeasible to iterate all possible subset of the newlywed couples. However, we can observe that the number of ways to arrange a seating order such that the newlywed couple P sits adjacently (i.e. the two members of a newlywed couple P sit next to each other) is the same as the number of ways to arrange a seating order such that the newlywed couple Q sits adjacently. In general, for a fixed number k of newlywed couples, regardless of which particular couples we choose, the number of seating orders in which all of those k newlywed couples have their two members adjacent is the same.
Therefore, we can define a function g(k) as the number of ways to arrange a seating order such that for each of the first k newlywed couples, the two members of a couple are sitting next to each other. g(k) can be computed by multiplying the following:
Finally, we should not forget that g(k) counts the number of ways to arrange a seating order such that the first k newlywed couples sit adjacently. To consider all subset of newlywed couples of size k, we need to multiply g(k) by C(M, k).
Putting all the pieces together, the answer we are looking for is Σ (-1)k × g(k) × C(M, k) for all 0 ≤ k ≤ M. By precomputing the value of powers of two, factorials, and their modular inverses, this answer can be computed in O(N + M) space and time.