Cast
Longest Arithmetic: Written by Jonathan Irvin Gunawan and prepared by Jonathan Irvin Gunawan.
High Buildings: Written by Jonathan Irvin Gunawan and prepared by Jonathan Irvin Gunawan.
Toys: Written by Artem Iglikov and prepared by Anson Ho.
Golden Stone: Written by Krists Boitmanis and prepared by Frederick Chyan.
Solutions, other problem preparation, reviews and contest monitoring by Anushi Maheshwari, Artem Iglikov, Bohdan Pryshchenko, Changyu Zhu, Devanshu Agarwal, Diksha Saxena, Frederick Chyan, Gregory Yap, Jared Gillespie, Jonathan Irvin Gunawan, Kashish Bansal, Kevin Tran, Lalit Kundu, Lizzie Sapiro, Mengru Huang, Nikhil Hassija, Preet Shah, Sanyam Garg, Sergio Vieri, Swapnil Gupta, Ruoyu Zhang, and Vipin Singh
Analysis authors:
An arithmetic array is an array that contains at least two integers and the differences between consecutive integers are equal. For example, [9, 10], [3, 3, 3], and [9, 7, 5, 3] are arithmetic arrays, while [1, 3, 3, 7], [2, 1, 2], and [1, 2, 4] are not arithmetic arrays.
Sarasvati has an array of N non-negative integers. The i-th integer of the array is A_{i}. She wants to choose a contiguous arithmetic subarray from her array that has the maximum length. Please help her to determine the length of the longest contiguous arithmetic subarray.
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 the integer N. The second line contains N integers. The i-th integer is A_{i}.
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 longest contiguous
arithmetic subarray.
Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
0 ≤ A_{i} ≤ 10^{9}.
2 ≤ N ≤ 2000.
2 ≤ N ≤ 2 × 10^{5} for at most 10 test cases.
For the remaining cases, 2 ≤ N ≤ 2000.
4 7 10 7 4 6 8 10 11 4 9 7 5 3 9 5 5 4 5 5 5 4 5 6 10 5 4 3 2 1 2 3 4 5 6
Case #1: 4 Case #2: 4 Case #3: 3 Case #4: 6
In Sample Case #1, the integers inside the bracket in the following represent the longest contiguous arithmetic subarray: 10 7 [4 6 8 10] 11
In Sample Case #2, the whole array is an arithmetic array, thus the longest contiguous arithmetic subarray is the whole array.
In Sample Case #3, the longest contiguous arithmetic subarray is either [5, 5, 5] (a subarray from the fourth integer to the sixth integer) or [4, 5, 6] (a subarray from the seventh integer to the ninth integer).
In Sample Case #4, the longest contiguous arithmetic subarray is the last six integers.
In an unspecified country, Google has an office campus consisting of N office buildings in a line, numbered from 1 to N from left to right. When represented in meters, the height of each building is an integer between 1 to N, inclusive.
Andre and Sule are two Google employees working in this campus. On their lunch break, they wanted to see the skyline of the campus they are working in. Therefore, Andre went to the leftmost point of the campus (to the left of building 1), looking towards the rightmost point of the campus (to the right of building N). Similarly, Sule went to the rightmost point of the campus, looking towards the leftmost point of the campus.
To Andre, a building x is visible if and only if there is no building to the left of building x that is strictly higher than building x. Similarly, to Sule, a building x is visible if and only if there is no building to the right of building x that is strictly higher than building x.
Andre learned that there are A buildings that are visible to him, while Sule learned that there are B buildings that are visible to him. After they regrouped and exchanged information, they also learned that there are C buildings that are visible to both of them.
They are wondering about the height of each building. They are giving you the value of N, A, B, and C for your information. As their friend, you would like to construct a possible height for each building such that the information learned on the previous paragraph is correct, or indicate that there is no possible height construction that matches the information learned (thus at least one of them must have been mistaken).
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of a single line with four integers N, A, B, and C: the information given by Andre and Sule.
For each test case, output one line containing Case #x: y
, where x
is
the test case number (starting from 1) and y
is IMPOSSIBLE
if there is
no possible height for each building according to the above information, or N
space-separated integers otherwise. The i-th integer in y
must be the height of the
i-th building (in meters) between 1 to N.
Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ C ≤ N.
C ≤ A ≤ N.
C ≤ B ≤ N.
1 ≤ N ≤ 5.
1 ≤ N ≤ 100.
3 4 1 3 1 4 4 4 3 5 3 3 2
Case #1: 4 1 3 2 Case #2: IMPOSSIBLE Case #3: 2 1 5 5 3
In Sample Case #1, the sample output sets the height of each building such that only the first
building is visible to Andre, while the first, third, and fourth buildings are visible to Sule.
Therefore, only the first building is visible to both Andre and Sule. Note that there exist other
correct solutions, such as 4 3 1 2
.
In Sample Case #2, all N = 4 buildings are visible to Andre and Sule. Therefore, it is impossible to have C ≠ N in this case.
In Sample Case #3, the sample output sets the height of each building such that the first, third, and fourth buildings are visible to Andre, while the third, fourth, and fifth buildings are visible to Sule. Therefore, the third and fourth buildings are visible to both Andre and Sule. Note that there exist other correct solutions.
Little Axel has N toys numbered from 1 to N. Each toy has two properties:
The toys are arranged in a circle, from 1 to N clockwise. Axel plays with them one by one.
When Axel reaches toy i which he has not played with yet, or which he has already forgotten about, he plays with it for E_{i} minutes and then immediately moves to the next one (clockwise).
If he reaches a toy that he has not forgotten yet (if less than R_{i} minutes have passed since the last time he finished playing with it), he will stop and cry.
We can define the time Axel spent playing as the sum of E_{i} of every toy Axel played with before stopping. If Axel played with a toy several times, it should be counted that many times.
Given the description of the toys, remove the smallest possible number of them in order to make Axel play either an indefinitely long time, or (if that is not possible) as long as possible before he stops.
Note:
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 the integer N. Next N lines contain 2 integers each: E_{i} and R_{i}. The i-th line is describing the toy number i.
For each test case, output one line containing Case #x: y z
, where:
x
is the test case number (starting from 1);
y
is the longest time Axel will play in minutes or "INDEFINITELY" (without quotes)
if he will play indefinitely long time.
z
is the minimal number of toys to remove so that Axel could play with the rest of
them either indefinitely or as long as possible;
Time limit: 30 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ E_{i} ≤ 10^{9}.
1 ≤ R_{i} ≤ 10^{9}.
1 ≤ N ≤ 12.
1 ≤ N ≤ 10^{5}.
4 1 5 1 2 5 10 10 3 3 30 17 5 10 10 3 3 5 10 5 10 5 11
Case #1: 5 0 Case #2: INDEFINITELY 0 Case #3: INDEFINITELY 1 Case #4: 25 0
In Sample Case #1 there is only one toy, so Axel will play with it and will get bored in 5 minutes.
In Sample Case #2, after playing with the toy number 1 for 5 minutes, he will need to not play with it for 10 minutes, which he will spend playing with the toy number 2. After that he will return to the toy number 1 and play with it for 5 minutes, during which he will forget the toy number 2, and so on. Thus he will play for an indefinitely long time.
In Sample Case #3, although Axel can play with the toy number 1 for 30 minutes, if we remove it he will be able to play with the others indefinitely. So we remove it, and keep the other two.
In Sample Case #4, Axel will play with the toys in the following order: 1, 2, 3, 1, 2, and then he will stop and cry as he still remembers the toy number 3. So, in total he will play for 25 minutes.
Leopold's friend Kate likes stones, so he decided to give her a golden stone as a gift. There are S types of stones numbered from 1 to S, 1 being the golden stone. Some types of stones are available free of charge in various parts of the city. The city consists of N junctions numbered from 1 to N and M two-way streets between pairs of distinct junctions. At each junction, zero or more types of stones are available in unlimited supply.
Unfortunately, the golden stone is not available anywhere. Luckily, Leopold is a bit of a magician and knows how to combine a group of stones and turn them into another stone. For example, one of his recipes could produce a golden stone out of one silver stone and two marble stones. He could collect those stones in some of the junctions if they are available, or he could use some of his many other recipes to produce any of those stones. Formally, Leopold has R recipes, where a recipe is in the form (a_{1}, a_{2}, ..., a_{k}) -> b for some k ≥ 1. If Leopold has gathered k stones of types a_{1}, a_{2}, ..., and a_{k} at a certain junction, he can choose to apply the recipe and turn these stones into one stone of type b.
Leopold likes puzzles much more than physical activity, therefore, he does not want to carry stones around the city unnecessarily. Carrying a stone along a street costs him one unit of energy. Leopold can carry no more than one stone at a time, however, he can drop off a stone at any junction and pick it up later at any time.
What is the minimum amount of energy Leopold must spend to produce one golden stone?
Leopold is very scared of large numbers. If the answer is greater than or equal to
10^{12}, print -1
instead.
The first line of the input gives the number of test cases T. T test cases follow. The first line of each test case consists of four integers N, M, S, and R giving the number of junctions, streets, stone types, and recipes, respectively. The following M lines describe the map of the city. The i-th of these lines contains two distinct integers U_{i} and V_{i} denoting the pair of junctions connected by the i-th street.
The subsequent N lines describe the types of stones available in each junction. The i-th of these lines starts with the number of stone types C_{i} available in i-th junction followed by C_{i} distinct integers in the range [2, S] enumerating the stone types. The golden stone is always numbered 1 and is not available.
The last R lines of each test case describe Leopold's magic recipes. The i-th of these
lines starts with the number of ingredient stones K_{i} required for the i-th
recipe followed by K_{i} not necessarily distinct integers in the range
[2, S] enumerating the types of necessary ingredients. The i-th line ends with an integer
in the range [1, S], which is the type of the resulting stone after applying the i-th
recipe. For example 3 6 5 6 3
denotes a recipe that requires two stones of type 6,
one stone of type 5, and produces a stone of type 3.
It is guaranteed that it is possible to produce a golden stone in each of the test cases.
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 for the test case
x
, namely, the minimum amount of energy Leopold must spend to produce one golden
stone.
If the answer is greater than or equal to 10^{12}, print -1
instead.
Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ U_{i}, V_{i} ≤ N, U_{i} ≠
V_{i}
0 ≤ C_{i} < S.
1 ≤ K_{i} ≤ 3.
Each pair of junctions is connected by at most one street.
It is possible to get from any junction to any other junction by following a sequence of streets.
It is possible to create a golden stone.
2 ≤ N ≤ 50.
1 ≤ M ≤ 80.
2 ≤ S ≤ 50.
1 ≤ R ≤ 50.
2 ≤ N ≤ 300.
1 ≤ M ≤ 500.
2 ≤ S ≤ 300.
1 ≤ R ≤ 300.
3 4 3 4 1 1 2 1 3 1 4 0 1 2 1 3 1 4 3 2 3 4 1 4 3 4 1 1 2 1 3 1 4 0 2 2 3 1 3 1 4 3 2 3 4 1 2 1 4 2 1 2 2 2 3 1 4 3 2 3 4 1 2 2 3 4
Case #1: 3 Case #2: 2 Case #3: 0
In the first test case, the minimum amount of energy is achieved if Leopold collects the stones 2, 3, and 4 at the junctions 2, 3, and 4, respectively, carries the stones to the junction 1, and uses his only recipe to transform the three stones into a golden stone. This way, three stones are carried along one street each, therefore, the total amount of energy spent is 3.
The only difference between the first two test cases is that the stone 3 is now available at the junction 2 as well. This time it is optimal to carry one stone of type 4 from junction 4 to junction 2 spending 2 units of energy, and then collect the missing stones of types 2 and 3 there to produce a golden stone using the only recipe.
In the third test case, Leopold can produce a golden stone without ever leaving junction 1. First, he should collect stones of types 2 and 3 to produce a stone of type 4 using the second recipe. In a second step, he should collect the stones 2 and 3 again and combine them with the stone 4 to produce a golden stone using the first recipe.
Consider a subarray of length K which is an arithmetic subarray, and let the elements of arithmetic subarray be B_{1}, B_{2}, B_{3}, ....., B_{K}. We can say that B_{2} - B_{1} = B_{i+1} - B_{i} for 1 ≤ i < K, because consecutive elements of arithmetic sequence should have a common difference.
Claim 1: In the given array, consider a subarray starting at index i and ending at index j. Now if this subarray is not arithmetic, there exists some index x such that i ≤ x < j and A_{x+1} - A_{x} ≠ A_{i+1}-A_{i}. All subarrays starting at index i and ending at index y such that x < y ≤ N, are not arithmetic because all such subarrays would contain index x such that A_{x+1} - A_{x} ≠ A_{i+1}-A_{i}.
For each element i such that (1 ≤ i < N), we consider each subarray starting at index i. Consider subarray(i,j) and start with j = i. Increment j while subarray(i,j) is an arithmetic subarray. For a fixed index i, we do not need to increment j after we find the first index such that subarray(i,j) is not an arithmetic subarray. None of the subarrays with i as a starting point and ending point after the index j will be arithmetic subarrays according to Claim 1. Let the maximum j for index i such that subarray(i,j) is an arithmetic subarray be max_j. We can conclude our approach as follows. Initialise the answer as 0. For each index i, find max_j. Update the answer if max_j - i + 1 is greater than the answer. For each index i, we would traverse O(N) elements. Hence, the overall complexity of the solution is O(N^{2}).
int maxArithmeticSubarray(vector<int> array) {
int maxLen = 0;
for(int i = 0; i < array.size() - 1; i++) {
int j = i;
int common_difference = array[i+1] - array[i];
while(j < array.size() - 1 && (array[j + 1] - array[j] == common_difference))
j++;
int max_j = j;
maxLen = max(maxLen, max_j - i + 1);
}
return maxLen;
}
Consider an index i. Now consider all the subarrays (i,j) starting at index i and ending at index j. Start with j = i. Let the maximum index j where the subarray(i,j) is an arithmetic subarray be j = x. Let A_{i+1} - A_{i} = D. We can say that A_{y+1} - A_{y} = D for all i ≤ y < x. We have 2 cases now.
We can conclude our approach as follows. Initialise the answer as 0. We maintain two pointers, left pointer i and right pointer j. For an index i, we try to find the longest arithmetic subarray starting at index i by incrementing j. Let the maximum j for index i such that subarray(i,j) is an arithmetic subarray be max_j. Update answer if max_j - i + 1 is greater than current answer. And then we shift our left pointer i to the current max_j. We can see that both the pointers visit each element at most once. Hence, the complexity of the solution is O(N).
int maxArithmeticSubarray(vector<int> array) {
int maxLen = 0;
for(int i = 0; i < array.size() - 1;) {
int j = i;
int common_difference = array[i+1] - array[i];
while(j < array.size() - 1 && (array[j + 1] - array[j] == common_difference))
j++;
int max_j = j;
maxLen = max(maxLen, max_j - i + 1);
i = max(i + 1, j);
}
return maxLen;
}
Let the heights of buildings be H_{1}, H_{2}, H_{3}, ... ,H_{N}. If we look from the left side, it is possible to view a building i, iff H_{i} ≥ H_{j} for all 1 ≤ j ≤ i. Similarly, if we look from the right side, it is possible to view a building i, iff H_{i} ≥ H_{j} for all i ≤ j ≤ N. It is possible to view a building i from both the sides if H_{i} ≥ H_{j} for all i ≤ j ≤ N and H_{i} ≥ H_{k} for all 1 ≤ k ≤ i. This means that H_{i} ≥ H_{j} for all 1 ≤ j ≤ N. Hence, only the buildings which have the maximum height would be visible from both sides.
The answer for N = 1 case is trivial. Consider the case where A + B - C > N. A buildings are seen from the left side, B buildings
are visible from the right side and C buildings are visible from both sides. This means that A + B - C buildings will be
visible from at least one of the sides. Hence, there are more than N buildings which are visible from at least one side, which is not
possible. Thus, answer is IMPOSSIBLE
in case A + B - C > N. The rest of the analysis assumes N > 1 and
A + B - C ≤ N.
The height of each building is an integer between 1 to N, inclusive. Thus, each building can have at most N distinct values. So, if we consider all possible heights of the given buildings, we get N^{N} different combinations. Now, we need to check if a possible set of heights satisfy the given condition of A, B and C.
To check how many buildings are visible from the left side, we start iterating from the left, and maintain a prefix_max variable that indicates what is the maximum height of a building which are on the left side of the current building. Formally, for building i, prefix_max would indicate maximum(H_{j}) for 1 ≤ j < i. And then we update the prefix_max variable when we move onto the next index. This can be done in O(N). Similarly, we can find how many buildings are visible from the right side by iterating from the right side, and maintaining a suffix maximum variable. This can be done in O(N). To count the number of buildings, which are visible from both sides, we need to find the maximum height and count the number of buildings with such maximum height. This can be done in O(N) too. If for a given set of heights, we get buildings visible from left side equal to A, buildings visible from right side equal to B and buildings visible from both the sides equal to C, we have found our answer. If there is no such set of heights that satisfy this condition, then we say that it is not possible.
A given set of height can be checked in O(N) time. There are N^{N} different combinations. Thus the overall complexity of the solution is O(N^{N} × N), which runs under the time limit for N ≤ 5.
In this test set, we cannot generate all possible set of heights as we have N ≤ 100. This can be solved by splitting into some cases:
IMPOSSIBLE
in this case.
Checking which case our solution falls under takes constant time. We can then just assign the heights to the buildings in linear time. Hence, the complexity of the solution is O(N).
Let us say Axel can play with the toys in multiple rounds (starting from 1), where each round starts with the toy that has the smallest number and finishes with the toy that has the largest number. There are a few observations:
For this test set, we can generate all subsets of the toys in order. For each subset, we can loop over the toys in the subset and calculate the maximum time Axel can play. This maximum time will be either INDEFINITELY (if Axel can play more than twice as in Observation 3), or sum of the enjoyments of the toys played until Axel gets stuck as in Observation 2. We can keep track of the maximum time for each subset and if two subsets have the same maximum time, we will consider the one with minimum toys removed (maximum subset size). As number of subsets will be 2^{N} and for each subset, time spent by Axel is calculated in linear time, total complexity of the solution will be O(N × 2^{N}).
Let us say we have K toys. If Axel can play indefinitely with these toys, for each toy, its remembrance should be less than or equal to the sum of enjoyment of all other toys except this one. If SUM is total sum of enjoyments of all the toys that Axel can play with, we can say, for each i = 1 to K, R_{i} ≤ SUM - E_{i} Or R_{i} + E_{i} ≤ SUM.
If Axel cannot play with these K toys indefinitely, we can try removing all the toys violating the condition R_{i} + E_{i} ≤ SUM, so that we can get a list of toys with no violation and Axel can play indefinitely. Here, we can remove the toys violating the condition in any order. But for simplicity, we will first remove a toy for which R_{i} + E_{i} is the largest. The reason being, if we remove some other toy, it will only decrease the SUM by enjoyment of the other toy and this toy would still be violating the condition R_{i} + E_{i} ≤ SUM.
In this test set, we can keep a list of the toys such that Axel can play with them indefinitely. Also, we will have a track of total time played till now (let us say cur_time), maximum possible time that Axel can spend playing (let us say max_time) and count of toys removed. Initially, cur_time will be total time taken in round 1 i.e. SUM as per Observation 1. Now, we will simulate the round 2 and have an empty list initially. We will keep adding toys 1 to N one by one to this list. After adding a toy to the list, we will check if we have some toy in the list violating the condition R_{i} + E_{i} ≤ SUM. If so, we will remove the toy violating the condition that has the largest R_{i} + E_{i}. Once we add a toy to the list, we will add its enjoyment to cur_time and while removing a toy from the list, we will remove its corresponding time (i.e. twice the enjoyment time for this toy) from cur_time, and remove it's enjoyment time from the SUM. After each toy is added and toys violating the condition are removed, we will update max_time if cur_time is optimal. Also, we will keep track of total toys removed from the list and update that as well while updating max_time. Finally, when all the toys have been added to the list and processed, if the list is not empty, Axel can play with the toys indefinitely. Else, we have max_time and corresponding toys removed as our answer.
To maintain the list of toys and remove a toy with the largest R_{i} + E_{i} efficiently, we can use Priority Queue to store toys in decreasing order of their R_{i} + E_{i}. As we are processing each toy twice, once for calculating initial SUM, and other for processing second round where in priority queue each toy can be added/removed maximum one time, total complexity of solution will be O(N log N).
The given set of junctions and streets can be considered as an undirected graph. The problem statement guarantees that the graph is connected.
We can consider all possible combinations of junctions and stones, and try to figure out the optimal cost of making that stone at that junction. Let's define the cost of gathering stone c at junction j as Cost_{j,} _{c}. Then the solution would be the minimum of Cost_{junction,} _{golden} over all the junctions.
We can consider a new graph, where each {junction, stone type} combination is a vertex, and for each street {u,v} in the given input, there will be S new edges {(u,c), (v,c)}, one for each stone type c. Then we can run a variation of Bellman-Ford algorithm on this graph to fill the two dimensional cost table as mentioned above.
Firstly, for all the stone types that are directly available at some junctions (as given in the input), the Cost_{junction,} _{stone_type} would be 0. All other combinations of junction and stone type will have initial cost set to infinity.
Then we can try to relax the cost as in the classic Bellman-Ford algorithm, with some modification, that, in addition to relaxing edges, we also try to reduce cost by applying recipes on the stones that are available at the same junction at some point.
For each junction u, we can relax the cost table as follows:
We must repeat the relaxation steps mentioned above for each junction as long as there are any improvements made to the cost values. It can be proved that no more than N × S iterations are required.
For the first type of relaxation, each {edge, stone type} combination is considered only once, and then the whole process is repeated O(N × S). So, ther overall complexity is O(N × M × S^{2}).
For the second type of relaxation, the process takes O(R) time per junction, and the whole relaxation process will repeat O(N × S) times per junction. So the complexity is O(N^{2} × S × R).
So, the total complexity of this approach is O(N × S × ((M × S) + (N × R))).
Filling up the cost table can also be achieved with Dijkstra's algorithm. The cost table can be initialized in the same approach used in test set 1. Then the vertices with cost 0 are put into a minimum priority queue with the calculated cost as the key.
At each step of trying to reduce cost for a vertex {u, c} from the queue, we can do the following:
In this approach, there are N × S vertices. For each edge in the input graph there will be corresponding S edges, so in total M × S edges.
The relaxation of the first type follows classic Dijkstra's algorithm's style, so the complexity is O((N × S + M × S) × log(N × S)).
For the relaxation of the second type for each vertex {u, c}, we need to try only the recipes where c is an ingredient. So in total, for each junction, a recipe will be applied once for each of its ingredients. Each recipe has at most 3 ingredients. Which gives us additional O(R × N × log(N × S)) complexity. So the total time complexity of this approach is O((N × S + M × S + R × N) × log(N × S)) which is sufficient for test set 2.