thanos_infinity_stones

Custom Problem Set - Thanos Inifinity Stones

• Problem link: problem.pdf in same folder
• Dataset links
  • input1.txt, output1.txt
  • input2.txt, output2.txt
  • input3.txt, output3.txt
  • input4.txt, output4.txt
  • input5.txt, output5.txt
  • input6.txt, output6.txt
  • input7.txt, output7.txt
  • input8.txt, output8.txt
  • input9.txt, output9.txt
  • input10.txt, output10.txt

Solution

• Key Idea
  • Solution is Maximum Spanning Tree of the graph of planets where edge weights are time taken to travel b/w planets
  • Use prims algorithm to compute Maximum Spanning Tree [At every step, instead of computing next minimum edge in cut, fetch next maximum edge in cut]

Reference: Prims Minimum Spanning Tree

Algorithm

• Maintain a parent array to store MST, key array to store incoming edge with maximum weight to a node and mstSet array to store if a node has been added to MST or not
• While mstSet doesn’t include all vertices
  • Pick a vertex u which is not there in mstSet and has minimum key value
  • Include u to mstSet
  • Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v
• The idea of using key values is to pick the maximum weight edge from cut. The key values are used only for vertices which are not yet included in MST, the key value for these vertices indicate the maximum weight edges connecting them to the set of vertices included in MST

Complexity

• V - Number of planets (Number of vertices in graph)
• E - Possible routes that allows Thanos to reach any other planet from the planet that he is currently in (Number of edges in graph)

Space Complexity

• parent: O(V)

• key: O(V)

• mstSet: O(V)

• adjacencyList: O(V + E)

• Total: O(4V + E)

Run Complexity

• Find next min/max edge in cut: O(V^2)

• Update key value of non-MST tree neighbours: O(V + E)

• Total: O(V + E + V^2) = O(V^2)

Testcases

Once you download all the above testcases into a testcases folder like below

Source code folder

➜  help_alice ls -ltrh
total 112
-rw-r--r--@  1 srinivas  staff    19K Apr 15 12:45 problem.pdf
-rw-r--r--@  1 srinivas  staff   2.6K Apr 15 13:01 main.cpp
-rwxr-xr-x   1 srinivas  staff    27K Apr 16 11:00 a.out
-rw-r--r--@  1 srinivas  staff   1.4K Apr 16 12:21 README.md
drwxr-xr-x  17 srinivas  staff   544B Apr 16 12:44 testcases/

Testcases folder

➜  help_alice ls -ltrh testcases
total 200
-rw-r--r--@ 1 srinivas  staff    45B Apr 15 12:46 input1.txt
-rw-r--r--@ 1 srinivas  staff   189B Apr 15 12:46 input2.txt
-rw-r--r--@ 1 srinivas  staff    23B Apr 15 12:46 output2.txt
-rw-r--r--@ 1 srinivas  staff   185B Apr 15 12:46 input3.txt
-rw-r--r--@ 1 srinivas  staff    30B Apr 15 12:47 output3.txt
-rw-r--r--@ 1 srinivas  staff    54B Apr 15 12:47 input4.txt
-rw-r--r--@ 1 srinivas  staff     7B Apr 15 12:47 output4.txt
-rw-r--r--@ 1 srinivas  staff    35K Apr 15 12:47 input5.txt
-rw-r--r--@ 1 srinivas  staff   5.5K Apr 16 10:59 output5.txt
-rw-r--r--@ 1 srinivas  staff     7B Apr 16 12:45 output1.txt
...

Run the following command to test all testcases:

ls -1 testcases | grep input | perl -nle 'if($_ =~ /input(\d+)/) { print $1; }' | xargs -I % bash -c 'time ./a.out < testcases/input%.txt > testcases/myoutput%.txt; diff -w testcases/output%.txt testcases/myoutput%.txt' > testcases/log

Inspect the log to check the diff b/w your solution and correct solution [Empty log file "testcases/log" denotes success]