This Kickstart round began with Even Digits, which was a simple adhoc problem. Then came Lucky Dip,which could be solved with some knowledge of basic probability theory. Finally, we had Scrambled Words, whose large dataset involved an elegant observation on the number of distinct lengths of words possible given a fixed total length.
Thanks to everyone who participated!
Cast
Problem A (Even Digits): Written and prepared by Jonathan Irvin Gunawan.
Problem B (Lucky Dip): Written and prepared by Celestine Lau.
Problem C (Scrambled Words): Written by Karthik Sundara Raghavan and Akashdeep Nain. Prepared by Lalit Kundu.
Solutions and other problem preparation and review by Ian Tullis, Lalit Kundu, Satyaki Upadhyay, Jonathan Irvin Gunawan, Akashdeep Nain, Shi-Jie Khor, Trung Thanh Nguyen and Hyeonjong Ryu.
Analysis authors:
Supervin has a unique calculator. This calculator only has a display, a plus button, and a minus button. Currently, the integer N is displayed on the calculator display.
Pressing the plus button increases the current number displayed on the
calculator display by 1. Similarly, pressing the minus button decreases the
current number displayed on the calculator display by 1. The calculator does
not display any leading zeros. For example, if 100 is displayed
on the calculator display, pressing the minus button once will cause the
calculator to display 99.
Supervin does not like odd digits, because he thinks they are "odd". Therefore, he wants to display an integer with only even digits in its decimal representation, using only the calculator buttons. Since the calculator is a bit old and the buttons are hard to press, he wants to use a minimal number of button presses.
Please help Supervin to determine the minimum number of button presses to make the calculator display an integer with no odd digits.
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the integer initially displayed on Supervin's calculator.
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 minimum number of button presses, as described above.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ N ≤ 105.
1 ≤ N ≤ 1016.
4 42 11 1 2018
Case #1: 0 Case #2: 3 Case #3: 1 Case #4: 2
In Sample Case #1, the integer initially displayed on the calculator has no odd digits, so no button presses are needed.
In Sample Case #2, pressing the minus button three times will cause the
calculator to display 8. There is no way to satisfy the
requirements with fewer than three button presses.
In Sample Case #3, either pressing the minus button once (causing the
calculator to display 0) or pressing the plus button once will
cause the calculator to display an integer without an odd digit.
In Sample Case #4, pressing the plus button twice will cause the calculator
to display 2020. There is no way to satisfy the requirements with
fewer than two button presses.
You are participating in the Grand Kickstart Lucky Dip with many fantastic and amazing prizes (and some not so good ones)!
In this Lucky Dip, there is a bag with N items. The i-th item in the bag has value Vi. You will put your hand into the bag and draw one item at random; all items in the bag have an equal probability of being chosen. The organizers want contestants to feel that they have some element of choice, so after you draw an item, you can either keep it, or "redip" by returning it to the bag and drawing again. (Note that the returned item is now just as likely to be chosen as any of the other items in the bag.) You may only redip a maximum of K times. If you use K redips, you must keep the item that you draw on your (K + 1)-th draw.
If you play optimally to maximize the value of the item you will end the game with, what is the expected value of that item?
The input starts with one line containing one integer T: the number of test cases. T test cases follow.
Each test case consists of two lines. The first line consists of two integers N and K: the number of items in the bag, and the maximum number of times you may redip. The second line consists of N integers Vi, each representing the value of the i-th item.
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 expected value described above. Your answer will be
considered correct if it is within an absolute or relative error of
10-6 of the correct answer. See the
FAQ
for an explanation of what that means, and what formats of real numbers we
accept.
5 4 0 1 2 3 4 3 1 1 10 1 3 15 80000 80000 80000 1 1 10 5 3 16 11 7 4 1
Case #1: 2.500000 Case #2: 6.000000 Case #3: 80000.000000 Case #4: 10.000000 Case #5: 12.358400
In Sample Case #1, you cannot redip, so the expected value is just the mean of the items in the bag which is (1 + 2 + 3 + 4) / 4 = 2.5.
In Sample Case #2, the best strategy is to keep the item of value 10 if you get it, and redip otherwise. The chance of getting that item (on either the first or second draw) is 1 - (2/3)2 = 5/9, hence the expected value is (5/9 * 10) + (4/9 * 1) = 6.
In Sample Case #3, since all the items have the same value, it does not matter how many times you redip and hence the expected value is 80000.
Note that cases #3 and #5 would not appear in the Small dataset.
Professor Scrmable noticed spelling mistakes in a research paper she was reviewing, but she had no difficulty in reading or understanding the words. Upon doing some research, she found an interesting article as described below:
According to a study at an English University, it doesn't matter in what order the letters in a word are, the only important thing is that the first and last letter be at the correct place. The rest can be a total mess and you can still read it without a problem. This is because the human mind does not read every letter by itself but the word as a whole.
Or rather ...
Aoccdrnig to a study at an Elingsh uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the corecrt pclae. The rset can be a toatl mses and you can sitll raed it wouthit a porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.
Professor Scrmable wants to explore this concept further and starts compiling different sentences containing similarly scrambled words to send to a popular publication. Unfortunately, the space key on the professor's keyboard is not working, so she has produced one long string of characters. She has asked you to determine how many of the words in her dictionary appear (at least once) as substrings in the long string of characters, either in their original or scrambled forms. (A scrambled form consists of the same set of letters with the first and last letters in the same places, and the others in any order.)
Note that a dictionary word can appear multiple times in the string (though it should be counted
only once since we only need to know whether it shows up at least once). For example, if we had the
word this in the dictionary, the possible valid words which would be counted are
this (original version) and tihs (scrambled version), whereas
tsih, siht and other variations are not valid since they do not start
with t and end with s. Also, tis, tiss, and
thiss are not scrambled forms, because they are not reorderings of the original set of letters.
Since the professor is extremely busy, she gives this task to you, her favorite and most trusted research assistant. Given a dictionary, can you count the number of words in the dictionary that appear as a substring in the professor's string at least once, in either their scrambled or original forms.
The first line of the input gives the number of test cases, T. T test cases follow. Each testcase contains three lines. The first line contains an integer L. The second line contains a list of L words made of lowercase English letters; these make up the dictionary. The third line contains two lowercase English letters S1 and S2, and five integers N, A, B, C and D. S1 and S2 are the first two characters of the professor's string S, N is the length of S, and the other four integers are parameters that you should use to generate the characters of S, as follows:
First we define ord(c) as the decimal value of a character c and
char(n) as the character value of a decimal n. For example,
ord('a') = 97 and char(97) = 'a'. You can refer to
ASCII table
for other conversions.
Now, define x1 = ord(S1), x2 = ord(S2). Then,
use the recurrence below to generate xi for i = 3 to N:
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 words from the
dictionary that appear (in their original or scrambled forms, as defined above) as substrings of the given string.
1 ≤ T ≤ 20.
Memory limit: 1 GB.
No two words in the dictionary are the same.
Each word in the dictionary is between 2 and 105 letters long, inclusive.
The sum of lengths of all words in the dictionary does not exceed 105.
S1 and S2 are lowercase English letters.
0 ≤ A ≤ 109.
0 ≤ B ≤ 109.
0 ≤ C ≤ 109.
1 ≤ D ≤ 109.
Time limit: 20 seconds.
1 ≤ L ≤ 1000.
2 ≤ N ≤ 1000.
Time limit: 150 seconds.
1 ≤ L ≤ 20000.
2 ≤ N ≤ 106.
1 5 axpaj apxaj dnrbt pjxdn abd a a 50 1 1 1 30
Case #1: 4
In Sample Case #1, using the generation method, the generated string S is aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt.
Scrambled or original occurences of dictionary words are highlighted as follows:
axpaj occurs in its scrambled form as aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt.apxaj occurs in its scrambled form as aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt.
Note that even though apxaj is the scrambled form of another dictionary word axpaj,
both should be counted.dnrbt occurs twice in its original form as aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt,
though it should be counted only once.pjxdn occurs in its scrambled form as aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt.
Note this occurence overlaps with occurence of another dictionary word, but still they're counted independently.abd doesn't occur at all.Note: We do not recommend using interpreted/slower languages for the Large dataset of this problem.
To make our discussion easier, let us define a beautiful integer as an integer which has only even digits in its decimal representation.
One useful observation for solving this problem is that we either only want to press the minus button or only want to press the plus button. It is useless to have both types in the same sequence, since they cancel each other out.
Therefore, we want to either keep pressing the minus button, or keep pressing the plus button, until we have a beautiful integer. Let M be the minimum number of minus button presses before reaching a beautiful integer, and let P be the minimum number of plus button presses before reaching a beautiful integer. Then the answer is the smaller of M and P.
Note that for this problem, the answer for an input N is bounded above
by N, since we can just press the minus button N times to reach
the beautiful integer 0. Therefore, since
N ≤ 105, we can solve the Small dataset using complete
search.
We can loop over a value i in the range [0, N], and, for each i, check whether N+i or N-i is a beautiful integer. If that is the case, then we break the loop and return i as the answer.
Iterating over the range [0, N] would be too slow for this dataset. Therefore, we need another approach.
To find the value of M, we must find the largest beautiful integer that is still no greater than N. Let us call this integer X. Similarly, to find the value of P, we can find the smallest beautiful integer that is still no smaller than N. Let us call this integer Y.
We can find X by decreasing the first odd digit in N by one and then
replacing all digits to the right of that odd digit with the largest even
digit (i.e. 8). For example, if N=4436271,
then X=4428888. This can create a leading 0, which we can simply
drop the leading 0 in that case. If there are no odd digits in N, then
N is a beautiful integer, thus X=N.
By constructing X this way, it is guaranteed that there will be no beautiful
integer between X and N, since the next beautiful integer after X would
be larger than N at the first odd digit. For the example above, the
next beautiful integer after X is 4440000, which is larger than
N.
Similarly, we can find Y by increasing the first odd digit in N by one
and replacing all digits to the right of that odd digit with the smallest even
digit (i.e. 0). If there are no odd digits in N, then
N is a beautiful integer, thus Y=N. However, when finding Y, we
must watch out for some tricky cases. If the first odd digit is
9, then we must replace the digit directly to the left of that
odd digit as well with the next even digit. For example, if
N=86912, then Y=88000.
Another tricky case is when the digit directly to the left of the first odd
digit is 8. In this case, we must replace the digit directly to
the left of that 8 digit as well, and keep doing this until we
have a non-8 digit. For example, if
N=6488962, then Y=6600000. Finally, if all
digits to the left continue to be 8 until we reach the leftmost
digit, or if the first digit of N is a 9, then we must add the smallest
non-zero even digit (i.e. 2) as a new digit on the left. For
example, if N=88892 or N=91112, then
Y=200000.
Once we know X and Y, we also know M and P, and we can take the smallest of those values, just as we did before.
There are two cases to consider for the small dataset: K = 0 and K = 1.
When K = 0, we must accept the first item which we draw. Since the chance of obtaining each item is the same, the expected value is the average value of all the items in the bag.
When K = 1, we note that if we redip, the expected value that we draw is going to be the same as the case when K = 0. Thus, the best strategy is to keep the item if the value of the item is greater than the average value of the items in the bag, or return the item otherwise.
Thus, we have the following equations to compute the values for E[0] and E[1]:
E[0] = Σ Vi / N E[1] = Σ max(Vi, E[0]) / N
The values for E[0] and E[1] can be computed in O(N) time.
When K > 1, we may proceed with a similar recursion as in the case when K = 1. Given k redips, we should keep the item if the value of the item is greater than the expected value for k-1 redips, and we should return the item otherwise. This gives rise to the following recursion:
E[k] = Σ max(Vi, E[k-1]) / N
Computing E[K] using the above approach requires us to compute E[0], E[1], ..., E[K - 1], each of which requires O(N) time. Thus, the total runtime amounts to O(NK), which is fast enough to pass the large dataset. However, it is possible to derive an even faster solution.
Suppose we have already computed the value for E[k - 1]. If our array of Vis is sorted, we can use a binary search to quickly determine the quantity of items which have value less than or equal to E[k - 1]. Let us denote this quantity with xk. Note that the probability of drawing one of these xk items is xk / N. This corresponds to the case when we return the item and redip.
On the other hand, there is an equal likelihood for drawing each of the remaining N - xk items. This gives us the following equation for E[k]:
E[k] = xk * E[k - 1] / N + Σi>xk Vi / N
For fast computation, we precompute by sorting the array of Vis in increasing order, and computing the suffix sums for the array. We will then compute E[0], E[1], ..., E[K] accordingly, in which each step takes O(log N) time. The total runtime is then O(N + N log N + K log N) = O((N + K) log N).
Let us first discuss how to check if two words are equivalent. A word is equivalent to another if
their corresponding starting and ending letters are same and the sets of letters in between are
either the same or permutations of each other.
To check if two words are equivalent, after verifying that their starting and ending letters are
equal, we populate a frequency array of the characters in each string and check if the two
frequency arrays are same or not. Since the strings in this problem consist of only lowercase
English letters, the array only needs to hold 26 integers (the counts of those letters'
frequencies), and we can compare two such arrays very quickly.
arrays will be very fast. An example of this would be the frequency away [1, 1, 2, 0, ... 0]
for the string bcca.
Given the relatively small caps on L and N in the Small dataset, one solution that may come to mind is as follows: For each word in the dictionary, iterate over the Professor's text and check for substring match at each position in the text using the method of frequency arrays described above. But we should think carefully about how we check substrings against each other. Suppose that the length of our dictionary word is W. If we do it naively, for each position in the text (assume the length of the dict word is W), we check the substring of length W starting at that position by iterating over it, which is suboptimal. We should maintain a running frequency array. Suppose the frequency array is populated for the substring starting at position i. When we move our substring window one character to the right, we need to decrement the frequency of text[i] and increment the frequency of text[i+l]. This will give us the frequency array of the substring starting at position i+1. These two operations take constant time.
Since we iterate over the whole text for every dictionary word and there are L words and the length of the text is N, the total time complexity of this solution will be O(NL).
The above approach will not work in the large dataset because there are too many words in the dictionary.
The solution for this dataset hinges on the observation that if the total length of the words in the dictionary is bounded by M, the maximum possible number of distinct word lengths is atmost √M. This can be seen as follows. Let X be the bound on the number of distinct lengths; then X*(X+1)/2 ≤ M.
The above solution is now modified by iterating over only those lengths which are present in the dictionary, and for each such length, we perform the same process as above, checking against only the dictionary words with that length.. Let M be the upper bound on the dictionary which is given as 105. Since there are at most √M distinct lengths, the overall complexity of the solution is O(N √M).