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| \\{x | a \le x \le b, x \in \mathcal{R}\\} \cap \\{x | c \le x \le d, x \in \mathcal{R}\\} | > C for any constant C.

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: \mathcal{O}(1)

Bonus: How would you solve this problem if there were N 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 S as the total number of slices. Right off the bat, we can see that if S is not divisible by N, it is Impossible. If it is divisible, we know that each person has to have \dfrac{S}{N} 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 \dfrac{\sum^N_{i=1} |A[i]-\dfrac{S}{N}|}{2}.

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
        n = read nline
        xs = map read $ words olines
        tot = sum xs
        each = tot `div` n
main = interact $ solve . lines

Time Complexity: \mathcal{O}(N)

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 20 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())

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 u and v implies a bond between v and u.

Time Complexity: \mathcal{O}(N^7).

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 \le Q\_i 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" \mathcal{O}(N^2) 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: \mathcal{O}(N^2+Q \log N)

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 0. The naive \mathcal{O}((N+M) \times 2^{N+M}) 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 2 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 S in the second half, we look for the number of occurences of -S in the cached results. This can be done by using either binary search or a map.

Time Complexity: \mathcal{O}(\dfrac{N+M}{2} \times \sqrt{2^{N+M}})

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: \mathcal{O}((K+N) \times N)


  • 1
     commented on Dec. 9, 2015
    P4 - Contagion

    Why using dijkstra with priority queue gives TLE?

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

      • 1
         commented on Dec. 9, 2015

        Thank you!