Supervin loves to eat candies. Today, his favorite candy shop is offering N candies, which are arranged in a line. The i-th candy in the line (counting starting from 1) has a sweetness level Si. Note that the sweetness level of a candy might be negative, which means the candy tastes bitter.
Supervin likes to eat sweet candies. However, candies with a combined sweetness level of more than D would be too much sweetness even for him. Supervin also realises that a candy with an odd sweetness level is "odd", and he does not want to eat more than O odd candies. In other words, an odd candy is a candy with a sweetness level that is not evenly divisible by 2. Additionally, since Supervin is in a rush, he can only eat a single contiguous subset of candies.
Therefore, he wants to eat a contiguous non-empty subset of candies in which there are at most
O odd candies and the total sweetness level is maximized, but not more than D. Help
Supervin to determine the maximum total sweetness level he can get, or return
IMPOSSIBLE if there is no contiguous subset satisfying these constraints.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains two lines. The first line contains three integers N, O, and D, as described above. The second line contains seven integers X1, X2, A, B, C, M, L; these values are used to generate the values Si, as follows:
We define:
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 total sweetness level
Supervin can get, or IMPOSSIBLE if there is no possible contiguous subset satisfying
the problem constraints.
1 ≤ T ≤ 100.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
2 ≤ N ≤ 5 × 105.
0 ≤ O ≤ N.
-1015 ≤ D ≤ 1015.
0 ≤ X1, X2, A, B, C ≤ 109.
1 ≤ M ≤ 109.
L = 0.
-5 × 108 ≤ L ≤ 0.
2 6 1 1000000000000000 1 1 1 1 0 100 0 6 1 -100 1 1 1 1 0 100 0
Case #1: 13 Case #2: IMPOSSIBLE
In Sample Case #1, the generated array of sweetness values Si is: [1, 1, 2, 3, 5, 8], where the bold and underlined numbers are the odd numbers. Since Supervin can only eat one odd candy, he can get a maximum total sweetness level by taking the fifth and the sixth candies.
In Sample Case #2, the generated array of sweetness values Si is the same as in Sample Case #1. However, this time Supervin cannot eat candies with a total sweetness level of more than -100, so no contiguous subset of candies satisfies the constraints.
Note: We do not recommend using interpreted/slower languages for the Large dataset of this problem.
3 10 1 8 4 3 4 1 5 20 -10 10 2 8 4 3 4 1 5 20 -10 10 1 8 4 3 4 1 5 20 -19
Case #1: 7 Case #2: 8 Case #3: -5
In Sample Case #1, the generated array of sweetness values Si is: [-6, -7, -9, 2, 4, 3, 1, -8, -6, -7], where the bold and underlined numbers are the odd numbers. Since Supervin can only eat one odd candy and he cannot eat candies with a total sweetness level of more than 8, he can get the maximum total sweetness level by taking the fifth and the sixth candies.
In Sample Case #2, the generated array of sweetness values Si is the same as in Sample Case #1. However, this time Supervin can eat two odd candies. Therefore, he can get a maximum total sweetness level by taking the fifth, the sixth, and the seventh candies.
In Sample Case #3, the generated array of sweetness values Si is: [-15, -16, -18, -7, -5, -6, -8, -17, -15, -16] where the bold and underlined numbers are the odd numbers. Note that it is possible for the maximum total sweetness level to be negative.
In order to advance in his quest to defeat the villainous Graphendorf, our hero Edge has to overcome a challenge in a shrine. The shrine is two-dimensional in the xy-plane, and there are N towers (of varying heights) erected along the x-axis of the plane. Each tower can be represented by a vertical line segment in a 2D plane. For tower i, the base of the tower is at (pi, 0), and the top of the tower is at (pi, hi). There are also K balloons floating in the plane. Each balloon can be represented by a single point in the 2D plane, with balloon i at position (xi, yi). Edge has to collect as many balloons as possible in this challenge.
Fortunately, Edge has a trusty paraglider which he found in a different room of this shrine. He may choose to climb any tower and glide down from any position on the tower towards either the positive or negative direction of the x-axis. When he glides, he descends in a straight path that makes a 45 degrees angle relative to the tower. Edge can collect any balloons in his way when he glides down from the tower. He can repeat this process of climbing up a tower and jumping off any number of times. If he touches a tower during his descent, then he is considered to be on the tower at the point and climbing. You may assume Edge to be a single point in the xy-plane.
Using a pair of goggles made from ancient technology, Edge was able to figure out the height and position of each tower and balloon. With this information, can you help Edge deduce the maximum number of balloons that he can collect in this shrine?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains five lines. The first line contains the integers N and K as described above. Each of the next four lines describe a recurrence used to generate the positions and heights of the towers and the x and y coordinates of the balloons. The four lines will each contain six integers in the following format:
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 number of balloons that
Edge can collect.
1 ≤ T ≤ 100.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
0 ≤ Ai ≤ 109 for i = 1 to 4.
0 ≤ Bi ≤ 109 for i = 1 to 4.
0 ≤ Ci ≤ 109 for i = 1 to 4.
1 ≤ Mi ≤ 109 for i = 1 to 4.
1 ≤ p1, p2 ≤ 109.
1 ≤ h1, h2 ≤ 109.
1 ≤ x1, x2 ≤ 109.
1 ≤ y1, y2 ≤ 109.
pi ≠ pj for i, j = 1 to N, i $ne; j.
2 ≤ N ≤ 1000.
2 ≤ K ≤ 1000.
2 ≤ N ≤ 105.
2 ≤ K ≤ 105.
2 3 2 1 4 1 1 0 11 4 1 1 1 8 11 2 5 0 0 0 11 4 1 0 0 0 11 5 5 2 4 1 0 1 13 4 4 0 1 12 13 1 4 1 1 0 13 3 5 1 1 7 13
Case #1: 1 Case #2: 4
Note that the input for Sample Case #1 produces the scenario depicted in the problem statement. The generated arrays are:
In Sample Case #2, the generated arrays are:
Siv's birthday is next week and Cel is preparing a birthday present for her. Because Siv loves puzzles, Cel is creating a word search puzzle as a gift.
In a word search puzzle, the solver is given a rectangular grid with R rows and C columns, and the solver must find all valid words hidden inside the grid. Each hidden word may appear horizontally or vertically (but NOT diagonally) in the grid, forward or in reverse. Hidden words may overlap.
Cel has a dictionary with W different words; these are the only words that can be hidden within the puzzle grid. (Of course, not every contiguous horizontal or vertical part of the grid will necessarily contain one of the hidden words.) These words are not necessarily real English words. Each word might appear in the grid one or more times, or not at all.
Cel has already created the word search puzzle. However, there is a problem: the puzzle is too big to print on a sheet of paper. As Siv's birthday is coming soon, there is not enough time to create a new word search puzzle from scratch. So Cel is wondering whether she can reduce the size of the grid, simply by selecting a non-empty, grid-aligned subgrid from the original grid.
Randomly selecting a subgrid might result in a boring puzzle without a lot of hidden words. So Cel wants to select a subgrid with the largest fun value, where the fun value of a subgrid is defined as:
fun value = (total length of words matched) / ((width of subgrid) + (height of subgrid))
Notes:
Can you please help Cel find the largest fun value that a subgrid could have, and the number of different subgrids that have this fun value? Two subgrids are considered different if and only if there is some cell in the grid—that is, some (row, column) position—that is in one subgrid, but not the other.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is structured as follows:
For each test case, output one line containing Case #x: y/z n, where:
x is the test case number (starting from 1).y/z is an irreducible fraction equal to the largest possible fun value
(as described above) of a subgrid.y is a non-negative integer.z is a positive integer.n is the number of subgrids with fun value equal to
y/z.
y/z is called an irreducible fraction if the greatest common divisor of y and z is 1.
2 1 2 1 AA A 1 2 1 AA B
Case #1: 8/3 1 Case #2: 0/1 3
Let (i, j) denotes the cell at i-th row and j-th column.
In Sample Case #1, the subgrid with highest fun value is the entire grid. The valid word
A appears 8 times in the grid:
In Sample Case #2, there are 3 subgrids with fun value equals 0:
2 1 3 2 ABC ABC CBA 4 4 1 AAAB AAAB AAAB BBBB AA
Case #1: 3/2 1 Case #2: 8/1 1
In Sample Case #1, the subgrid with highest fun value is the entire grid. The valid word
ABC appears horizontally from cell (1, 1), and the valid word CBA
appears horizontally in reverse from cell (1, 1). So the fun value of the entire grid
equals 6/(1 + 3) = 3/2.
In Sample Case #2, the subgrid with highest fun value has top-left corner at cell (1, 1)
and bottom-right corner at cell (3, 3). The valid word AA appears 24 times in the
subgrid:
Note: We do not recommend using interpreted/slower languages for this problem.
To make our discussion easier, for each range (L, R), let us define SS(L, R) to be the sum of sweetness of the candies from index L to R (inclusive), and SO(L, R) to be the number of odd candies from index L to R (inclusive). Our problem is equivalent to finding a range (L, R) such that:
We will use the technique of two pointers to solve the Small dataset. For each value of L from 1 to N, we would like to find the value of R such that the value of SS(L, R) is maximized while observing the constraints stated above. Since the candies have non-negative sweetness in the Small dataset, for every L, we simply have to find the rightmost index R that satisfies SO(L, R) ≤ O and SS(L, R) ≤ D.
For any fixed L', suppose we have identified that R' is the rightmost index that satisifes SO(L', R') ≤ O and SS(L', R') ≤ D. For L'+1, note that S(L' + 1, R') necessarily satisfies SO(L' + 1, R') ≤ O and SS(L' + 1, R') ≤ D. Thus, we do not need to iterate through the entire array to find the value of R that maximizes SS(L'+1, R). We simply have to iterate from R' + 1 to N to find the largest value of R that still satisfies our constraints. This dramatically reduces the runtime of the algorithm, as we only iterate the array once to find the optimal value of R for each L (Hence the name two pointers — the pointers L and R only iterate over the array once). Once we obtain the optimal sweetness for each L, we can simply take the maximum and return as the answer. Total runtime of the solution is O(N).
Since Si may be negative in the Large dataset, for each L, we can no longer assume that the rightmost index that satisfies the constraints will give us the optimal value for SS(L, R). However, we can still use the above sliding window technique to identify the rightmost index that still satisfies the oddness constraint. For any fixed L', suppose we have identified that RO' is the rightmost index that satisfies the oddness constraint. That is to say, we have SO(L', RO') ≤ O and SO(L', RO' + 1) > O. Now we need to find the index R in the range [L', RO'] that maximizes the value of SS(L', R), while observing the constraint SS(L', R) ≤ D.
To do so, we shall precompute the prefix sum of the sweetness of the candies (i.e. the values of SS(1, 1), SS(1, 2), ..., SS(1, N)). Notice that SS(L, R) = SS(1, R) - SS(1, L - 1). Thus, finding the value of R that maximizes S(L', R) is equivalent to finding the value of R that maximizes SS(1, R) - SS(1, L' - 1), which is the same as finding the value of R that maximizes the prefix sum SS(1, R) while observing SS(L', R) ≤ D.
In order to identify the value of R quickly, we will need a data structure that supports adding integers, removing integers, and finding the largest integer smaller than a queried integer. A balanced binary search tree (e.g. C++ multiset) can perform each of these operations in logarithmic time. As we iterate over the value of L, we will add or remove the values of SS(1, R) to the tree such that the tree only contains prefix sums for the indices in the range [L, RO]. Then, we will query for the largest prefix sum such that SS(1, R) ≤ SS(1, L - 1) + D. This allows us to compute the maximum sweetness for a subarray that starts from L, and we may then compute the overall maximum sweetness across all subarrays.
The time needed to preprocess all prefix sums and values of RO is O(N). Subsequently, each prefix sum may only be added or removed at most once from our data structure. In addition, we will only query the data structure once for each value of L. Using a balanced binary search tree, this gives us a total runtime of O(N log N).
First, we need a way to determine if a balloon is able to be collected. Note that Edge glides at a 45 degree angle, which means that for each unit he glides horizontally, he also descends one unit vertically. Since Edge can glide down from any position on a tower, Edge can collect any balloon if and only if there is a tower such that the height of the tower is greater than or equal to the horizontal distance between the balloon and the tower. For each balloon i, we can execute a linear search of the towers for a tower j which satisfies h[j] ≥ y[i] + abs(p[j] - x[i]). The time complexity for this approach is O(N × K).
We will need to optimize our previous solution in order to have a fast enough solution for the Large dataset. Since we definitely need to iterate through every balloon, we can conclude that we should be optimizing the search for a possible tower for Edge to jump from.
A key observation is that some towers may be irrelevant. For two towers A and B, if the height of A is less than or equal to the height of B minus the distance between A and B, then any balloon which is reachable by A is also reachable by B. A is considered an irrelevant tower. All towers which are not irrelevant can be considered relevant. To eliminate irrelevant towers efficiently, we want to create a sorted array of all towers based on their positions on the x-axis. Then, we want another array to keep track of the relevant towers and their positions. We iterate through the sorted array of all towers and do the following for each tower i: compare tower i to the tower at the end of the array of relevant towers. If tower i is irrelevant with respect to that last tower, continue on to the next tower in the sorted array of all towers; otherwise, continue removing towers from the end of the relevant tower array until both tower i and the last tower are relevant or until the relevant tower array is empty. Then, add tower i to the end of the relevant tower array and continue to the next tower in the sorted array.
The end result is that we have an array of all relevant towers which are also sorted by the towers' positions on the x-axis. Now, for each balloon we can check to see if it is further left or further right than all of the relevant towers. If so, we can check the closest tower to see if it allows Edge to collect the balloon; otherwise if the balloon is not further left or further right, we can use binary search to find the two closest towers to the balloon (one on each side) on the x-axis because we removed all of the irrelevant towers, meaning the only towers which can get to a certain balloon are the closest towers. If Edge can reach the balloon from either of these towers, then the balloon is collectable.
So what is the time complexity of our new solution? Sorting the original list of towers will take O(N log N) time. During the process of determining relevant towers, each tower cannot be added or removed more than once, so that step is O(N). It is possible that all towers are relevant, so doing a binary search at each balloon will take O(K log N) time; therefore, our time complexity is O((N + K) log N).
As we approach the problem, we want to decide on what we can feasibly calculate. Since the upper bounds for R and C are reasonably low, we know that we can iterate through all combinations of (i1, j1, i2, j2) where (i1, j1) is the top left cell of a subgrid and (i2, j2) is the bottom right cell; however, recalculating the total length of words found for every subgrid will still take too long. Note that since the length of each valid word is 1 in the Small dataset, the total length from finding a single instance of a word is 4. One solution is to calculate prefix sums S(i, j) and then calculate totals[i1, j1, i2, j2] = S(i2, j2) - S(i1 - 1, j2) - S(i2, j1 - 1) + S(i1 - 1, j1 - 1).
The prefix sum solution is simpler, but we will examine a different algorithm that extends more readily to the Large dataset. For every i1, create an array column_sum[j] which, when we iterate through values for i2, will represent the total length of words found in the column bounded by (i1, j, i2, j). For every i2 ≥ i1, scan through row i2 to update column_sum[j] by adding 8 if (i2, j) is a word. After doing so, for every j1, start with totals[i1, j1, i2, j1] = column_sum[j1], and for every j2 > j1, update totals[i1, j1, i2, j2] = totals[i1, j1, i2, j2 - 1] + column_sum[j2]. As we calculate totals[], keep track of the best fun size and how many times it occurs. As a side-note, it is not necessary to store the entire totals[] array, since we only use one previous calculation. This algorithm takes O(R2C2) time.
Knowing that all words are of length 1 is very beneficial in the Small dataset for quickly updating our column sums. Luckily, with a bit of precomputation, updating can be just as easy for the Large dataset. As long as our precomputations are not slower than O(R2C2) time, we should not have any problems.
Before running our algorithm, we can add the reverse of every word to our dictionary, so we only need to scan for words going from left to right (now referred to as going right) and top to bottom (going down).
We can observe that the length of a word limits where it can begin. Using this property, we can reduce the number of words to search for at each location. As a result, we want to create a lookup table word_lookup[i] which has a list of words of length i at each respective index. Now let us use two more lookup tables right[i, j, k] and down[i, j, k] which will keep track of how many words start at cell (i, j) and have length ≤ k going right and down, respectively. We can populate the tables in the following manner: for every (i, j) start with length k = 1. While k is a valid length for a word going right starting at (i, j) with respect to the entire grid, check every word in word_lookup[k] to see if it can be found going right starting at (i, j). Record right[i, j, k] = (k * number of words found) + right[i, j, k - 1]. Increment k until it is not a valid length for a word starting at (i, j). Repeat for words going down instead of going right.
Now, we can use an algorithm which is very similar to the one we used on the Small dataset. Let us just focus on words going right. We will still use totals[i1, j1, i2, j2] for the same purpose. For every i1, have a table right_column_sums[j, k] which, when we iterate through values for i2, will represent the total length of words going right with length ≤ k which start at the column bounded by (i1, j, i2, j). For every i2 ≥ i1, scan through row i2 and update right_column_sums[j, k] = right_columns_sums[j, k] + right[i2, j, k] for all valid values of k (remember that a word must be short enough to start at column j). Then, we will work left to right. For every j2, with j2 starting at C - 1 and totals[i1, j2, i2, j2] = right_column_sums[j2, 1], and for every j1 < j2, update totals[i1, j1, i2, j2] = totals[i1, j1 + 1, i2, j2] + right_column_sums[j1, j2 - j1 + 1]. The process for words going down is analogous, but with the rows and columns switched, and starting our iteration on columns instead of rows. As totals[] is finalized for words going both right and down, keep track of the best fun size and how many times it occurs. It is also possible to not store the entirety of totals[] in the Large dataset solution and have a space complexity of O((R + C)3) by solving for words going both right and down in the same loop, but doing so requires a slightly different precomputation step.
We still need to analyze the time complexity of the Large dataset solution. Creating word_lookup[] takes O(W) time. Creating right[] or down[] takes O(R × C × W) time. Creating all right_column_sums[] takes O(R2C) time. Populating totals[] still has a longer runtime than any of our previously mentioned steps, resulting in our solution taking O(R2C2) time.