-
Notifications
You must be signed in to change notification settings - Fork 22
/
mountain_tour.py
81 lines (73 loc) · 3.29 KB
/
mountain_tour.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# Copyright (c) 2020 kamyu. All rights reserved.
#
# Google Code Jam 2017 Round 3 - Problem C. Mountain Tour
# https://codingcompetitions.withgoogle.com/codejam/round/0000000000201902/0000000000201877
#
# Time: O(C * log*(C))
# Space: O(C)
#
# Template:
# https://github.com/kamyu104/FacebookHackerCup-2019/blob/master/Final%20Round/temporal_revision.py
class UnionFind(object): # Time: (N * log*(N)), Space: O(N)
def __init__(self, n):
self.set = range(n)
def get_id(self):
self.set.append(len(self.set))
return len(self.set)-1
def find_set(self, x):
stk = []
while self.set[x] != x: # path compression.
stk.append(x)
x = self.set[x]
while stk:
self.set[stk.pop()] = x
return x
def union_set(self, x, y):
x_root, y_root = map(self.find_set, (x, y))
if x_root == y_root:
return False
self.set[min(x_root, y_root)] = max(x_root, y_root)
return True
def time_to_arrive(a, b):
return (a+b)%24
def time_to_leave(a, b):
return (b-a)%24
def mountain_tour():
C = input()
tours = map(lambda x: (x[0]-1, x[1], x[2]), [map(int, raw_input().strip().split()) for _ in xrange(2*C)])
prev_camps = [[] for _ in xrange(C)]
for i, (E, _, _) in enumerate(tours):
prev_camps[E].append(i)
result = sum(D for _, _, D in tours)
next_camps, costs = [0]*(2*C), [0]*C
for i, (prev_a, prev_b) in enumerate(prev_camps):
if not i:
ta = min(time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i][1]) + tours[2*i+1][1],
time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i+1][1]) + tours[2*i][1])
tb = min(time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i+1][1]) + tours[2*i][1],
time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i][1]) + tours[2*i+1][1])
else:
ta = time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i][1]) + \
time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i+1][1])
tb = time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i+1][1]) + \
time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i][1])
assert(abs(ta-tb) in (0, 24))
if ta < tb:
result += ta
next_camps[prev_a], next_camps[prev_b] = 2*i, 2*i+1
costs[i] = tb-ta
else:
result += tb
next_camps[prev_a], next_camps[prev_b] = 2*i+1, 2*i
costs[i] = ta-tb
union_find = UnionFind(2*C)
for i in xrange(2*C):
union_find.union_set(i, next_camps[i])
for i, c in enumerate(costs):
if not c: # firstly, union tours with 0 hr
union_find.union_set(2*i, 2*i+1)
# secondly, union tours of camp1 if they are in disjoint cycles, which has the smallest union costs in the rest of disjoint cycles
# finally, union the rest of tours in disjoint cycles, which all have the same cost 24 hrs
return result + sum(c for i, c in enumerate(costs) if union_find.union_set(2*i, 2*i+1))
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, mountain_tour())