## DMOPC '15 December Solutions

Special thanks go out to nullptr for allowing us to use his Haskell solutions as samples.

#### P1 - Quality Scenes

by FatalEagle

Knowledge required: simple logic

This problem asks whether two given video clips overlap. In other words, it cares if for any constant .

solve :: [Integer] -> String
solve [a,b,c,d] | a > c = solve [c,d,a,b]
solve [a,b,c,d] | b > c = "YES"
solve [a,b,c,d] = "NO"
main = interact $solve . (map read) . lines  Time Complexity: Bonus: How would you solve this problem if there were video clips? #### P2 - Cheesecake Distribution by cheesecake Knowledge required: array processing, basic math This was slightly trickier than the usual P2. Notice that we're only concerned with the final state, not the steps we take to get there. Let's denote as the total number of slices. Right off the bat, we can see that if is not divisible by , it is Impossible. If it is divisible, we know that each person has to have slices at the end. The observation is that each turn, no matter who's giving to whom, we're moving two steps closer to the end state. The answer is therefore . import Data.Int solve :: [String] -> String solve [nline, olines] = if tot mod n /= 0 then "Impossible" else show$ (div 2) $sum$ map (abs . (each -)) $xs where n = read nline xs = map read$ words olines
tot = sum xs
each = tot div n
main = interact $solve . lines  Time Complexity: #### P3 - Dimethylbenzene by Xyene Knowledge required: DFS or for loops This problem involves a graph of a molecule — however, this does not mean it requires any knowledge of graph theory to solve! Since the bounds are small (up to atoms and bonds), one does not have to implement a functional graph traversal: seven nested for loops work. Author's Python 2 solution: from collections import defaultdict N, M = map(int, raw_input().split()) adj = defaultdict(list) for _ in xrange(M): a, b = map(int, raw_input().split()) adj[a].append(b) adj[b].append(a) for a in xrange(1, N + 1): potential = False for b in adj[a]: if b == a: continue for c in adj[b]: if c in [a, b]: continue for d in adj[c]: if d in [a, b, c]: continue for e in adj[d]: if e in [a, b, c, d]: continue for f in adj[e]: if f in [a, b, c, d, e]: continue for j in adj[f]: if j == a and j not in [b, c, d, e, f]: print "YES" raise SystemExit print 'NO'  Remember that a bond between and implies a bond between and . Time Complexity: . #### P4 - Contagion by cheesecake Knowledge required: Dijkstra's algorithm, binary search. The given graph is a complete graph, where the countries are the vertices and the infection times are the edges. The number of countries infected at a given hour is the number of vertices with a shortest path from the source. Note that on a complete graph, both priority queue Dijkstra's and SPFA will time out at their worst case complexities. The correct solution uses "classical" Dijkstra's to find the shortest path to every country. After sorting the array containing the shortest paths, we can binary search to find the answer to each query. Time Complexity: Bonus: What is the worst case complexity of priority queue Dijkstra's and SPFA on a complete graph? Why? #### P5 - Total Annihilation by cheesecake Knowledge required: meet-in-the-middle Anyone with knowledge of the subset sum problem probably recognized this problem immediately. For anyone who does not know, the subset sum problem is one of the most famous NP-complete problems, you can learn more about it here. If we add all samples to one array, with the antimatter samples being negative, the problem is reduced to finding the number of subsets that sum to . The naive solution involves iterating over all possible subsets using bitmasks. For full points, we use a technique called meet-in-the-middle. Similar to divide and conquer, we divide the array into equally sized arrays. In the first half, we use the same naive technique to find all subset sums and cache them. For each subset sum in the second half, we look for the number of occurences of in the cached results. This can be done by using either binary search or a map. Time Complexity: Bonus: Can you solve this problem using meet-in-the-middle? #### P6 - Gala by k_53P The author has provided a detailed explanation here. Time Complexity: ## Comments • mpsbotelho commented on Dec. 9, 2015 P4 - Contagion Why using dijkstra with priority queue gives TLE? • jeffreyxiao commented on Dec. 9, 2015 Using a binary heap, the time complexity of Dijkstra's is$O(E\ log\ V)$. Since the graph can be a complete graph, the worst case of Dijkstra's is$O(V^2\ log\ V)\$

• mpsbotelho
commented on Dec. 9, 2015

Thank you!