[Competitive Programming Review] Google Kick Start Round E problem 4 — Golden Stone

if you want to see my solution for Problem 2 [High Buildings] → https://medium.com/@eunpyolee0420/competitive-programming-review-note-google-kickstart-round-e-problem-2-94d45b80eecb

if you want to see my solution for Problem 2 [High Buildings] → https://medium.com/@eunpyolee0420/competitive-programming-review-note-google-kickstart-round-e-problem-2-94d45b80eecb

Note that I didn’t write a review on the first problem because it was a simple and straightforward sliding window problem (But I truly believe the first problem can help you improve your sliding window concept!)

I should have post this review on the same day that I posted the reviews for the other two problems, but it was already 4:00 a.m (KST) and I had a remote class. (+ I’m pretty busy with my iOS side project called GipTalk — hope I can make a blog post about it by the end of this year)

Anyway, the last and hardest (according to the stats) problem of the Round E — Golden Stone.

And the problem statement is following:

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 per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ui, Vi ≤ N, Ui ≠ Vi
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.

Test Set 1

2 ≤ N ≤ 50.
1 ≤ M ≤ 80.
2 ≤ S ≤ 50.
1 ≤ R ≤ 50.

Test Set 2

2 ≤ N ≤ 300.
1 ≤ M ≤ 500.
2 ≤ S ≤ 300.
1 ≤ R ≤ 300.

Sample

Input

Output

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

Comments

Personally, this problem felt harder than other because it is giving us multiple entities where creates the more cases and possibilities such as recipes and the number of junctions. But, sometimes “thinking simple” is a great way to start thinking of possible approaches or define some steps in our algorithms.

Since we want to minimize the use of energy (or traveling distance with holding a stone), this sounds very similar to finding the shortest distance from one to others. And, my old CS data structure class taught me a good algorithm for this case — Dijkstra.

But unlike the plain Dijkstra case, here we only concerns about the distance we travel with the stone. Therefore, we will just need to figure out what kind of stones are available at Junction i and how much energy we have to use to carry each type of stone at Junction I to other Junctions.

And the recipe — this will give us how much energy will be needed to create the result stone at Junction i and we will use this information in our Dijkstra algorithm as well

For the data structures, we will need the map information, how much energy we need to get stone j at junction i and min_heap which will put the junction and stone type information whose energy use is the smallest for the core Dijkstra. Additionally, we will need data structures for recipe information such as mapping relationship between materials to the recipe and recipe to the result stone.

Since the “street” is bi-directional, we need to create a bi-directional mapping between those junctions connected by the street.

It is currently reading the input about the street and creating a bi-directional graph between those connected junctions

We also initialize the information of the stones given by the input and its supplier junctions’s energy cost (which is 0 because it is the supplier)

While reading the stone type and the supplier junction input, update the energy use info and push those to our Dijkstra-use priority_queue since supplier junctions are good places to begin as their energy required for the stone is 0.

Also initialize the recipe informations (materials to recipe, recipe to materials, recipe to the result) while reading inputs about recipes

Now, we got the all of initial/base condition to start off the Dijkstra, which will not only update the stone profile but also the minimum energy use for the profile of each junction.

The key structure of each step is: (1) if the candidate information is staled, don’t waste your time. (2) Based on this candidate stone and its improved energy use, update the energy portfolio of all of the junctions connected by this junction. (3) Investigate all of those recipes using this improved candidate stone; if any recipe created stones gives you improved energy use, update and put it into the Dijkstra-use Priority Queue as a candidate.

After all of above steps, all of the junctions will have stone portfolio (all stone types including the gold stone) and the minimum amount of energy it needs to create the portfolio. Now, we just need to find the minimum among those energy uses, and just need to check whether the value is ≥ limit or not.
(limit here is 1e12 as the requirement says)

The entire code for this:

[Retro]

It is true that even if you successfully defined the all of data structure you will need, it does not always let you have a smooth algorithm part. Here, we uses many data structures and there exists some complex relationship between those, which is adding a complexity to build our core algorithm which is the Dijkstra. It is so prone to make a mistake during the coding part under such conditions, but defining high-level interfaces that can be used as a guideline can prevent us from making those mistakes.