# Google Kick Start Archive — Round E 2020 problems

## Overview

Thank you for participating in Kick Start 2020 Round E.

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:

• Longest Arithmetic: Swapnil Gupta
• High Buildings: Swapnil Gupta
• Toys: Vikash Dubey

## A. Longest Arithmetic

### Problem

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 Ai. 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.

### Input

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 Ai.

### Output

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.

### Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
0 ≤ Ai ≤ 109.

2 ≤ N ≤ 2000.

#### Test Set 2

2 ≤ N ≤ 2 × 105 for at most 10 test cases.
For the remaining cases, 2 ≤ N ≤ 2000.

### Sample

Sample Input
```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
```
Sample Output
```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.

## B. High Buildings

### Problem

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).

### Input

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.

### Output

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.

### Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ CN.
CAN.
CBN.

1 ≤ N ≤ 5.

1 ≤ N ≤ 100.

### Sample

Sample Input
```3
4 1 3 1
4 4 4 3
5 3 3 2
```
Sample Output
```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 CN 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.

## C. Toys

### Problem

Little Axel has N toys numbered from 1 to N. Each toy has two properties:

• Eienjoyment, which is the number of minutes Axel can play with toy number i without getting bored with it;
• Riremembrance, which is the number of minutes it takes Axel to forget toy number i after having played with it.

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 Ei minutes and then immediately moves to the next one (clockwise).

If he reaches a toy that he has not forgotten yet (if less than Ri 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 Ei 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:

• Axel has never played with these toys before;
• he cannot be left without toys;
• he always starts with the toy that has the smallest number;
• after finishing playing with the toy that has the largest number, he will move to the toy that has the smallest number.

### Input

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: Ei and Ri. The i-th line is describing the toy number i.

### Output

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;

### Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Ei ≤ 109.
1 ≤ Ri ≤ 109.

1 ≤ N ≤ 12.

1 ≤ N ≤ 105.

### Sample

Sample Input
```4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
```
Sample Output
```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.

## D. Golden Stone

### Problem

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 (a1, a2, ..., ak) -> b for some k ≥ 1. If Leopold has gathered k stones of types a1, a2, ..., and ak 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 1012, print `-1` instead.

### Input

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 Ui and Vi 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 Ci available in i-th junction followed by Ci 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 Ki required for the i-th recipe followed by Ki 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.

### Output

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 1012, print `-1` instead.

### Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Ui, ViN, UiVi
0 ≤ Ci < S.
1 ≤ Ki ≤ 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.

### Sample

Sample Input
```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
```
Sample Output
```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.

## Analysis — A. Longest Arithmetic

Consider a subarray of length K which is an arithmetic subarray, and let the elements of arithmetic subarray be B1, B2, B3, ....., BK. We can say that B2 - B1 = Bi+1 - Bi 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 Ax+1 - AxAi+1-Ai. 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 Ax+1 - AxAi+1-Ai.

### Test Set 1

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(N2).

##### Sample Code (C++)
``````
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;
}
``````

### Test Set 2

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 Ai+1 - Ai = D. We can say that Ay+1 - Ay = D for all i ≤ y < x. We have 2 cases now.

• Case 1: x = N,
In this case, subarray(i, N) is an arithmetic subarray. All subarrays(p, N) such that i < p ≤ N, will have shorter length than subarray(i, N). Hence, we can discard all subarrays starting with index p.
• Case 2: x ≠ N,
Ax+1 - Ax ≠ D. We have already proved that we need not consider j > x for index i as those subarrays will not be arithmetic using Claim 1. Now consider subarrays (k, x + 1) such that ( i+1 ≤ k < x). All these subarrays are not arithmetic because Ax+1 - Ax ≠ D whereas Ak+1 - Ak = D. Hence, we can discard all the subarray starting with index k. So, we can now shift the starting index to x.

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).

##### Sample Code (C++)
``````
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;
}
``````
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — B. High Buildings

Let the heights of buildings be H1, H2, H3, ... ,HN. If we look from the left side, it is possible to view a building i, iff Hi ≥ Hj for all 1 ≤ j ≤ i. Similarly, if we look from the right side, it is possible to view a building i, iff Hi ≥ Hj for all i ≤ j ≤ N. It is possible to view a building i from both the sides if Hi ≥ Hj for all i ≤ j ≤ N and Hi ≥ Hk for all 1 ≤ k ≤ i. This means that Hi ≥ Hj 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 - CN.

### Test Set 1

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 NN 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(Hj) 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 NN different combinations. Thus the overall complexity of the solution is O(NN × N), which runs under the time limit for N ≤ 5.

### Test Set 2

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:

• Case 1: Let us first assume that C > 1.
Consider any 2 values P and Q such that 1 ≤ P < Q ≤ N. In this case, we can put A - C buildings with height P on the left and B - C buildings with height P on the right and C buildings in the middle with height Q. Now, we have satisfied the constraint of A, B and C. We have N - A - B + C buildings remaining which should not be visible from either side. This can be done by assigning them height P and hiding them between the buildings with height Q.
• Case 2: C = 1. In this case, we cannot hide buildings between buildings with the maximum height since there is only one of them. We would have to look for some cases here:
• A + B - C = N,
In this case, we have no buildings to hide, thus we can assign the buildings similar to Case 1 when C > 1 with heights P and Q.
• Either A > 1 or B > 1. In this case, A + B - C < N. A + B is at least 3 and C = 1. Thus, we can say that N > 2 holds. Consider any 3 values P, Q and R such that 1 ≤ P < Q < R ≤ N. In this case, we can put A - 1 buildings with height Q on the left, B - 1 buildings with height Q on the right side and a building with height R in the middle. Now, we have satisfied the constraint of A, B and C. We have N - A - B + C buildings remaining which should not be visible from either side. Let the height of remaining buildings be P. We have already placed at least 2 buildings, and all the buildings that we placed so far are higher than the buildings that we want to hide, so we can hide remaining buildings anywhere in between the already placed buildings.
• A = 1 and B = 1
This means that the building with maximum height is both on the leftmost point and rightmost point and it is not possible for N > 1. So, the answer is `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).

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — C. Toys

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:

1. Axel can play with each toy at least once, in round 1.
2. If Axel cannot play indefinitely, in round 2 he will get stuck at some toy and start crying.
3. If Axel can play with a toy more than twice (i.e. reaches round 3), he can keep playing indefinitely.

### Test Set 1

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 2N and for each subset, time spent by Axel is calculated in linear time, total complexity of the solution will be O(N × 2N).

### Test Set 2

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, RiSUM - Ei Or Ri + EiSUM.

If Axel cannot play with these K toys indefinitely, we can try removing all the toys violating the condition Ri + EiSUM, 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 Ri + Ei 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 Ri + EiSUM.

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 Ri + EiSUM. If so, we will remove the toy violating the condition that has the largest Ri + Ei. 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 Ri + Ei efficiently, we can use Priority Queue to store toys in decreasing order of their Ri + Ei. 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).

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — D. Golden Stone

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 Costj, c. Then the solution would be the minimum of Costjunction, golden over all the junctions.

### Test set 1

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 Costjunction, 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:

• For each edge {v, u} in the input graph, and stone type c, try to reduce the Costu,c by carrying one type c stone from v to u.
• Try to apply each recipe at the junction u to see if we can improve the Costu, c where c is the stone produced by the recipe.

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 × S2).

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(N2 × S × R).

So, the total complexity of this approach is O(N × S × ((M × S) + (N × R))).

### Test set 2

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:

• For each edge {u, v}, try to reduce the Costv, c by carrying one type c stone from u to v.
• Try to reduce the Costu, stone_type by applying recipes where c is an ingredient.

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.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.