The last Round 1 again had an attendance in the vicinity of 5000 — pretty impressive, given that 2000 people already advanced. Our contestants were faced with a substring-counting problem Consonants, where to solve the large you had to deal with million-character names; followed by the tricky puzzle of Pogo and an implementation-intense problem called Great Wall.
The large input size in consonants caused the solutions of a large number of contestants to time out — quadratic solutions weren't cutting it, after all, and nearly 60% of contestants who attempted the large failed. The large of pogo was even more tricky — while for the small you could do some variation around exhaustive search, for the large you needed a few observations to come up with a greedy solution. Only 19% of contestants who attacked this problem succeeded. Finally, the Great Wall had a rather complex input that scared many people off, the first submission for the small came over half an hour into the contest; and the large required some variation on the theme of interval trees.
The competition was off to a blazing start, with xiaowuc1 solving the small of Consonants in an astounding time below two minutes! The other problems proved more problematic, however. In the end, it turned out that solving any one problem by itself was not enough to advance. The most popular way to get a spot in Round 2 was to deal with Consonants large and both remaining smalls, followed by dropping the Great Wall small in favor of doing the other problems really fast.
Congratulations to everybody who got through to Round 2, and we hope you enjoyed all the Round 1 problems!
Cast
Problem A. Consonants written by Khaled Hafez and Petr Mitrichev. Prepared by Onufry Wojtaszczyk and Hackson Leung.
Problem B. Pogo written by David Arthur. Prepared by Onufry Wojtaszczyk and Ahmed Aly.
Problem C. The Great Wall written by Onufry Wojtaszczyk. Prepared by Adrian Kuegel and Steve Thomas.
Contest analysis presented by Onufry Wojtaszczyk, John Dethridge and Hackson Leung. Solutions and other problem preparation by Igor Naverniouk, Jan Kuipers, Tomek Czajka and Tomek Kulczynski.
In English, there are 26 letters that are either vowels or consonants. In this problem, we consider a, e, i, o, and u to be vowels, and the other 21 letters to be consonants.
A tribe living in the Greatest Colorful Jungle has a tradition of naming their members using English letters. But it is not easy to come up with a good name for a new member because it reflects the member's social status within the tribe. It is believed that the less common the name he or she is given, the more socially privileged he or she is.
The leader of the tribe is a professional linguist. He notices that hard-to-pronounce names are uncommon, and the reason is that they have too many consecutive consonants. Therefore, he announces that the social status of a member in the tribe is determined by its
All members in the tribe must have their names and n given by the leader. Although the leader is a linguist and able to ensure that the given names are meaningful, he is not good at calculating the
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the name of a member as a string of length L, and an integer n. Each name consists of one or more lower-case English letters.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 < n ≤ L.
1 ≤ L ≤ 100.
1 ≤ L ≤ 106.
The input file will be no larger than 6MB.
4 quartz 3 straight 3 gcj 2 tsetse 2
Case #1: 4 Case #2: 11 Case #3: 3 Case #4: 11
You have just got the best gift ever, a Pogo stick. The pogo stick is something you use to jump off the ground while standing on it.
This Pogo stick is a special one: the first jump will move you a distance of 1 unit, the second jump will move you 2 units, the third jump will move you 3 units and so on. You can jump in only four directions using this stick: north (increasing y), south (decreasing y), east (increasing x) or west (decreasing x).
Now you want to play a game in your backyard, which we model as an infinite plane. You are standing with your stick in at point (0, 0) and you want to go to point (X, Y).
The point (X, Y) will never be (0, 0), and it will always be reachable from your starting point.
Check the output section carefully, because the required outputs for the small and large datasets are not the same.
The first line of the input gives the number of test cases, T. T test cases follow, one per line. Each line consists of 2 integers separated by a single space, X and Y, the coordinates of the point you want to reach.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a string represents the directions of the moves, for example if you are going to move north then south then east then west, this string should be NSEW.
For the small dataset, the output is considered correct if it does not take more than 500 moves to reach the destination in each test case.
For the large dataset, the output is considered correct if it reaches the destination point in the minimum possible number of moves.
If there are multiple correct solutions, print any of them.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 50.
0 ≤ |X|, |Y| ≤ 100.
1 ≤ T ≤ 100.
0 ≤ |X|, |Y| ≤ 106.
2 3 4 -3 4
Case #1: ENWSEN Case #2: ENSWN
The output for the first sample test case will not be considered correct if it is in the large dataset, because the number of moves is not the minimum. WNSEN would be a correct output for this test case if it were in the large dataset.
You are studying the history of the Great Wall of China, which was built by the Chinese to protect against military incursions from the North. For the purposes of this problem, the Great Wall stretches from infinity in the East to minus infinity in the West. As this is a lot of distance to cover, the Great Wall was not built at once. Instead, for this problem we assume that the builder used a reactive strategy: whenever a part of the border was attacked successfully, the Wall on this part of the border would be raised to the height sufficient to stop an identical attack in the future.
The north border of China was frequently attacked by nomadic tribes. For the purposes of this problem, we assume that each tribe attacks the border on some interval with some strength S. In order to repel the attack, the Wall must have height S all along the defended interval. If even a short stretch of the Wall is lower than needed, the attack will breach the Wall at this point and succeed. Note that even a successful attack does not damage the Wall. After the attack, every attacked fragment of the Wall that was lower than S is raised to height S — in other words, the Wall is increased in the minimal way that would have stopped the attack. Note that if two or more attacks happened on the exact same day, the Wall was raised only after they all resolved, and is raised in the minimum way that would stop all of them.
Since nomadic tribes are nomadic, they did not necessarily restrict themselves to a single attack. Instead, they tended to move (either to the East or to the West), and periodically attack the Wall. To simplify the problem, we assume they moved with constant speed and attacked the Wall at constant intervals; moreover we assume that the strength with which a given tribe attacked the Wall changed by a constant amount after each attack (either decreased from attrition, or grew from experience).
Assuming that initially (in 250 BC) the Wall was nonexistent (i.e., of height zero everywhere), and given the full description of all the nomadic tribes that attacked the Wall, determine how many of the attacks were successful.
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 a single integer N: the number of the tribes attacking the Wall. N lines follow, each describing one tribe. The ith line contains eight integers di, ni, wi, ei, si, delta_di, delta_pi and delta_si separated by spaces, describing a single nomadic tribe:
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of attacks that succeed.
Time limit: 60 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 20.
0 ≤ di.
1 ≤ delta_di ≤ 676060.
di + (ni - 1) * delta_di ≤ 676060.
1 ≤ si ≤ 106.
-105 ≤ delta_si ≤ 105.
si + (ni - 1) * delta_si ≥ 1.
1 ≤ N ≤ 10.
1 ≤ ni ≤ 10.
-100 ≤ wi < ei ≤ 100.
-10 ≤ delta_pi ≤ 10.
1 ≤ N ≤ 1000.
1 ≤ ni ≤ 1000.
-106 ≤ wi < ei ≤ 106.
-105 ≤ delta_pi ≤ 105.
2 2 0 3 0 2 10 2 3 -2 10 3 2 3 8 7 2 0 3 1 2 0 5 10 2 8 0 0 3 0 1 7 1 2 2 3 3 0 5 1 1 4 0
Case #1: 5 Case #2: 6
In the first case, the first tribe attacks three times: on day 0 it hits the interval [0,2] at height 10, on day 2 it hits [3,5] at height 8 and on day 4 it hits [6,8] at height 6; all three attacks succeed. Then the second tribe attacks three times, each time at height 8 - on day 10 it hits [2,3] (this succeeds, for example at position 2.5, where the Wall has still height 0), on day 17 it hits [4,5] (this fails, the Wall is already of height 8 in the interval [3, 5], which covers [4, 5]), and on day 24 it hits [6,7] (this succeeds, as the Wall there was of height 6).
In the second case there are three tribes, and their attacks intermingle. The sequence is as follows:
It cannot be simpler than trying each possible substring given the name. For a given substring, we just check if there exists n consecutive consonants. If it is true, we count this substring into part of the n-value. There are O(L2) substrings, and it takes O(L) time to check for at least n consecutive consonants. In total each case takes O(L3) time to solve, which is acceptable to solve the small input. This approach is, of course, not fast enough to solve the large input.
In fact we can skip the linear time checking for all possible substrings. Here we assume the index is zero based. Suppose we start from the i-th character. We also have c that starts as zero. When we iterate up to the j-th character, if it is a consonant, we increase c by 1, otherwise reset it to zero. Actually c is the number of consecutive consonants that starts after the i-th character and ends at the j-th character. If we meet the first instance such that c ≥ n, we can conclude that every substring which starts at the i-th character and ends at the k-th character, where k ≥ j, is the desired substring. Then we know that we can add L - j to the answer, and proceed to the next starting character. This algorithm runs in O(L2) time, which is still not sufficient in solving the large input. But the concept of computing c is the key to solve the problem completely.
Let us extend the definition of c to every character, call it ci: the number of consecutive consonants that ends at the i-th character. For example, suppose the string is quartz, then c0 = 1, c2 = 0, and c5 = 3. We can use similar approach mentioned in the last section to compute every ci in O(L) time. Also define a pair (x, y) to be the substring that starts at the x-th character and ends at the y-th character.
Knowing from the previous section, if we know that ci ≥ n, then we know that substrings (i - ci + p, i + q), where 1 ≤ p ≤ ci - n + 1 and 0 ≤ q ≤ L - i - 1, are the desired substrings. It implies that there are (ci - n + 1) × (L - i) substrings. If you proceed like this, you missed some substrings. Consider the string axb with n = 1. We see that c1 = 1 but we only count 2 substrings, namely x and xb. We miss the prefix options, namely ax and axb. It looks like we can consider the substrings (p, i + q), where 0 ≤ p ≤ i - n + 1 and 0 ≤ q ≤ L - i - 1. Unfortunately, in this case we may count certain substrings multiple times. Consider the string xaxb with n = 1, where we count xax and xaxb twice since c0 = c2 = 1.
To correctly count the substrings, we need to choose the appropriate range of p. In fact, we just need one more value: the last j < i such that cj ≥ n. Let r = j - n + 2 if there is such j, or r = 0 otherwise. Then we have the right set of substrings (p, i + q), where r ≤ p ≤ i - n + 1 and 0 ≤ q ≤ L - i - 1. In fact, r means the longest possible prefix so that (r, i - n) contains at most n - 1 consecutive consonants and therefore we avoid repeated counting. Hence for each ci ≥ n we count (i - n - r + 2) × (L - i). Summing up we have the answer. r is updated whenever we see that ci ≥ n before iterating the next position. Therefore it takes constant time to update the value. Overall the running time is O(L), which is enough to solve the large input.
Despite the complications, the algorithm is extremely simple. The following is a sample solution:
def Solve(s, n):
L = len(s)
cnt, r, c = 0, 0, 0
for i in range(L):
c = c + 1 if s[i] not in "aeiou" else 0
if c >= n:
cnt += (i - n - r + 2) * (L - i)
r = i - n + 2
return cnt
The small dataset did not require finding the optimal solution, instead accepting any solution that solved the problem within 500 moves. This allowed for a variety of approaches. One such approach is as follows: note that with two subsequent jumps in two opposite directions you can move one unit in a chosen direction. By a sequence of at most 200 such pairs (so in total at most 400 moves) you can reach any point with |X|, |Y| ≤ 100.
There were also other approaches possible, for instance a shortest-path search, if one could prove or guess that it's OK to limit the search space somehow. It turns out that one can actually just search for a path within the points with |x|, |y| ≤ 100, we will see why in the next section. Thus, Dijkstra's algorithm or just breadth-first search will provide a short enough path to the target.
For the large dataset, we not only need to return the best possible solution, but also deal with more distant targets, so neither of the approaches above will work. We will begin with a few easy observations:
Let's consider a point (X, Y), and any N satisfying the two conditions above. For the sake of brevity, assume |X| ≥ |Y|, and X ≥ 0 (it's easy to provide symmetric arguments for the other four cases). In this case, we will assume the last move was East. This means the first N-1 moves have to reach (X-N, Y). We will proceed recursively, so we just have to prove that (X-N, Y) and N-1 satisfy the conditions above.
For N = 1 or 2, it's easy to enumerate all the possible X and Y. For N = 1, there are four possibilities, and in each case our strategy produces the correct move. For N = 2, if we assume X is positive and greater than |Y|, the only possibilities are (3, 0), (2, 1), (2, -1) and (1, 0); after the move they turn to (1, 0), (0, 1), (0, -1) and (-1, 0) — all of which satify the conditions for N = 1.
For larger N, the parity condition is trivial — both considered parities stay the same if N was even, and both change if N is odd. For the inequality condition, if N ≤ X, both sides just decrease by N, so the only interesting case is if X < N. However, in this case, we move to (X - N, Y), and the sum of absolute values is N - X + |Y| ≤ N - X + X = N ≤ 1 + ... + N - 1. Thus, the conditions are satisfied after one move, and we can continue with our strategy.
This logic again translates to simple code:
def Solve(x, y):
N = 0
sum = 0
while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1:
N += 1
sum += N
result = ""
while N > 0:
if abs(x) > abs(y):
if x > 0:
result += 'E'
x -= N
else:
result += 'W'
x += N
else:
if y > 0:
result += 'N'
y -= N
else:
result += 'S'
y += N
N -= 1
return result.reversed()
Despite the very long statement, solving the small input wasn't actually that hard. Still, the long statement scared many contestants off, which is probably why we saw the first submission only after half an hour of the contest, and relatively few submissions to the problem in general. With at most 10 tribes, at most 10 attacks and all the attacks happening on a short section of the Wall, we can just simulate all that happens. Let's look at it a bit more carefully.
Since delta_p is limited by 10, a tribe attacks at most 10 times, and the initial attack is between -100 and 100, all the attacks will occur between -200 and 200. Thus, we can afford to remember the height of the wall at each interesting point. This brings us to the first trick of this problem — what are the points we should be interested in?
Note that since the edges of attacked areas are always integers, the height of the wall in each open interval (x, x+1) for integral x is always constant. Moreover, the height at the integral points is never lower than at any of the two neighboring open intervals, since any attack that affects any of these intervals will also affect the integral point next to it. As wi < ei, any attack always affects at least one whole interval, and so the success of the attack depends only on the height of the wall in the intervals, and not on the edges. Thus, it is enough to keep information about the height of the wall in points of the form x + 0.5 for integral x. There are 400 such points to consider in the small input, and the height of each is initially zero.
There are a 100 attacks to consider. We can begin by generating all of them explicitly (noting the beginning and end point, day and strength for each of them), and sorting them by time of occurrence. For each day on which at least one attack occurs, we first check for each attack whether it succeeds (by examining the wall height at each attacked interval). Afterwards, for all attacks we go over all affected intervals and increase the height of the wall if necessary. Note that it is important to increase the wall height only after checking all the attacks that occur on a given day.
The numbers are much bigger for the large input. We can have 106 attacks, and they can range over an interval of length over 108. Let's analyse which parts of the previous approach will work, and which will not.
We can still generate all the attacks explicitly, and sort them by time. We probably need a more concise way to represent the Wall, though, and we surely need a faster way to check whether an attack succeeds and updating wall heights.
The problem of concise representation can be solved by noticing that since we have only 106 attacks, we will have around 106 interesting points. A sample way to take advantage of this it to "compress" all attack coordinates — sort all the coordinates that are beginnings or ends of attacks, and consider as interesting only the points in the middles of intervals of adjacent endpoints. We will end up with at most 2 x 106 points, and each will represent an interval such that the height of the wall on this interval is always the same. Using this tric to compress the attack coordinates, we can assume all attacks happen in a space of at most 2 x 106 points. We can rename these points to be consecutive for convenience.
To attack the problem of checking attack success and updating the wall, we will need some variant of an interval tree. We will present two interval-tree based approaches below.
An interval tree is a tree, in which each node represents an interval [m x 2k, m x 2k] for some m,k. The parent of a node containing an interval I will be the node representing a twice longer interval containing I (so, if I is [m x 2k, m x 2k], the parent is [(m / 2) x 2k+1, (m/2 + 1) x 2k+1]). This is the common pattern for interval trees, the trick is in what to store in nodes.
In the first approach, we will try to answer the questions directly by the means of using a modified interval tree. We will store two values in each node — hi and lo. The "hi" value will be pretty standard, and will be defined so that the height of the wall at any given point is the maximum "hi" value of all the intervals containing this point. This can be updated in logarithmic time when any interval of the wall is attacked - we can split any interval into a logarithmic number of intervals represented by nodes, and update the hi value in each of them. This will allow us to update the wall height, and to figure out what the height of the wall at a given point is, each in logarithmic time. We still need a way to figure out whether an attack will succeed in logarithmic time, though.
We will use the "lo" values for that. For a given node X and a path to a leaf from X we can define the maximum "hi" value on this path as the "partial height" of the leaf node. This is what would be the height, if we disregarded all the nodes above X (in particular, "partial heights" measured from the root node are simply wall heights). We now define the "lo" value of X as the smallest partial height of a descendant of X. We need to see how this is useful, and how to update it in logarithmic time when updating the "hi" values.
Note that if we have a "lo" value for a node calculated, we can easily figure out the height of the lowest wall point in this interval - it's the maximum of the "lo" value of this node and the "hi" values of all the ancestors of this node. Thus, to figure out whether an attack will succeed on a general interval we split it into a logarithmic number of intervals represented by nodes, and figure out the lowest wall segment in each of these sub-intervals. If any of these is lower than the strength of the attack, it will succeed. This is logarithmic-squared as described, but it's easy to implement it to actually be logarithmic.
Now note that the "lo" values have a simple recursive definition - take the minimum of the "lo" values of the children, or the "hi" value of the node itself, whichever is higher. This means that when updating the "hi" value for a node, we only need to update the "lo" values for this node and its ancestors - meaning we can update "lo" values in logarithmic-squared time for each attack (and, again, it's simple to update them in logarithmic time).
Another approach that allows us to solve this problem with an interval tree is to order the attacks by strength, descending, and not by chronology. In this approach, for each point we know what was the earliest time at which it was attacked. Note that since we process from the strongest attack, any section of the wall that was attacked earlier by an attack we already processed is immune to attacks that come later and are processed later. Thus, to learn whether the attack is successful we need to find what's the latest attack time in the whole interval this attack covers; and subsequently we need to update the attack times to the minimum of the time that was stored so far, and the time of the currently processed attack.
This is called a min-max interval tree (we update with the minimum, and we query for the maximum). We encourage you to figure out what to store in the nodes to make this work in logarithmic time!