## 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

Why using dijkstra with priority queue gives TLE?

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

Thank you!