-
Notifications
You must be signed in to change notification settings - Fork 13
/
seafood.py
82 lines (76 loc) · 3.71 KB
/
seafood.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
82
# Copyright (c) 2019 kamyu. All rights reserved.
#
# Facebook Hacker Cup 2019 Round 2 - Seafood
# https://www.facebook.com/hackercup/problem/404425766835121/
#
# Time: O(NlogN)
# Space: O(N)
#
from bisect import bisect_right
def seafood():
N = input()
G = [[None for _ in xrange(N)] for _ in xrange(2)]
for i in xrange(2):
G[i][0], G[i][1], A, rightmost_harder_R, C, D = map(int, raw_input().strip().split())
for j in xrange(2, N):
G[i][j] = (A*G[i][j-2] + rightmost_harder_R*G[i][j-1] + C) % D + 1
O = raw_input().strip()
P = sorted((G[0][i], O[i], G[1][i]) for i in xrange(N)) # ordered positions
C = [] # idx of ordered positions with clam
for i in xrange(N):
if P[i][1] == 'C':
C.append(i)
ascending_R_H_before_rightmost_C_from_right = []
for i in reversed(xrange(C[-1])):
if (P[i][1] == 'R') and \
(not ascending_R_H_before_rightmost_C_from_right or (ascending_R_H_before_rightmost_C_from_right[-1][0] < P[i][2])):
ascending_R_H_before_rightmost_C_from_right.append((P[i][2], P[i][0]))
rightmost_harder_R = [-1]*len(C) # rightmost_harder_R[i] = j:
# rightmost rock j s.t.
# ascending_R_H_before_rightmost_C_from_right[j] > P[C[i]][2]
for i in xrange(len(C)):
j = bisect_right(ascending_R_H_before_rightmost_C_from_right, (P[C[i]][2], float("inf")))
if j == len(ascending_R_H_before_rightmost_C_from_right):
break
rightmost_harder_R[i] = ascending_R_H_before_rightmost_C_from_right[j][1]
suffix_min_R = [float("inf")]*(len(C)+1)
suffix_max_H = [float("-inf")]*(len(C)+1)
for i in reversed(xrange(len(C))):
suffix_min_R[i] = min(suffix_min_R[i+1], rightmost_harder_R[i])
suffix_max_H[i] = max(suffix_max_H[i+1], P[C[i]][2])
ascending_R_H_after_rightmost_C = []
for i in xrange(C[-1]+1, N):
if not ascending_R_H_after_rightmost_C or \
ascending_R_H_after_rightmost_C[-1][0] < P[i][2]:
ascending_R_H_after_rightmost_C.append((P[i][2], P[i][0]))
result = float("inf")
descending_stk = []
for i in xrange(len(C)):
if not i:
d = 0
else:
p = P[C[i-1]][0]
while len(descending_stk) > 1: # keep potential idxs
# earlier idxs can eventually become more optimal than later ones
a = descending_stk[-1][1]
b = min(a, descending_stk[-2][1])
if descending_stk[-2][0] + 2*max(0, p-b) > \
descending_stk[-1][0] + 2*max(0, p-a):
break
descending_stk[-2][1] = b # update optimal idx with new rock pos harder than both clams
descending_stk.pop() # pop the topmost because it’s no longer more optimal
d = descending_stk[-1][0] + 2*max(0, p-descending_stk[-1][1])
descending_stk.append([d, rightmost_harder_R[i]])
rightmost_p = P[C[-1]][0]
if suffix_min_R[i] >= 0:
# from last clam position to the nearest left rock harder than i..len(C)-1 clams
result = min(result, d+max(0, rightmost_p-suffix_min_R[i]))
j = bisect_right(ascending_R_H_after_rightmost_C, (suffix_max_H[i], float("inf")))
if j != len(ascending_R_H_after_rightmost_C):
# from last clam position to the nearest right harder rock
result = min(result, d+(ascending_R_H_after_rightmost_C[j][1]-rightmost_p))
if rightmost_harder_R[i] == -1: # no harder rocker or the last clam
break
return -1 if result == float("inf") else result + P[C[-1]][0]
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, seafood())