DMOPC '15 December Solutions
Special thanks go out to nullptr for allowing us to use his Haskell solutions as samples.
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
Bonus: How would you solve this problem if there were video clips?
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
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
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: .
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.
Bonus: What is the worst case complexity of priority queue Dijkstra's and SPFA on a complete graph? Why?
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.
Bonus: Can you solve this problem using meet-in-the-middle?
The author has provided a detailed explanation here.