Here is the mashup link (the problems are from Codeforces' problem set).
A. Minimizing Travel Distance
To solve this problem you need to understand that friends must meet in the middle point of the given points, so friends who live in the leftmost and in the rightmost points must go to the middle point. Because of that the answer equals to $$$max(x_1, x_2, x_3) - min(x_1, x_2, x_3)$$$.
Total complexity: $$$O(n)$$$
import sys
a,b, c = map(int, sys.stdin.readline().strip().split())
print(max(a,b,c) - min(a, b, c))
B. Meat Cost
Idea is a simple greedy, buy needed meat for i - th day when it's cheapest among days 1, 2, ..., n..
import sys
n = int(sys.stdin.readline().strip())
mi = float("inf")
ans= 0
for _ in range(n):
a, b = map(int, sys.stdin.readline().strip().split())
mi = min(mi, b)
ans += (a*mi)
print(ans)
C. Maximum Erasable Elements
Since $$$1≤a_i≤10^3$$$ for all $$$i$$$, let set $$$a_0=0$$$ and $$$a_n+1=1001$$$. For every $$$i$$$,$$$j$$$ such that $$$0≤i<j≤n+1$$$, if $$$a_j−j=a_i−i$$$ then we can erase all the elements between $$$i$$$ and $$$j$$$ (not inclusive). \
import sys
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
nums = [0] + nums + [1001]
ans = 0
left = 0
for i in range(1, n + 2):
if nums[i] - nums[i - 1]> 1:
left = i
ans = max(ans, i - left - 1)
print(ans)
D. Hamming Distance Reduction
The first observation is that the new Hamming distance may not be less than the old one minus two, since we change only two characters. So the task is to actually determine, if we can attain decrease by two, one or can’t attain decrease at all.
The decrease by two is possible if there are two positions with the same two letters in two strings but that appear in different order (like “double” <-> “bundle”).
If there are no such positions, then we just need to check that we may decrease the distance. This can be done by just “fixing” the character that stands on the wrong position, like in “permanent” <-> “pergament” (here n stands in wrong pair with m, and there is also unmatched m, so we may fix this position).
Otherwise, the answer is to keep everything as it is. Implementation can be done by keeping for each pair (x, y) of symbols position where such pair appears in S and T and then by carefully checking the conditions above.
from sys import stdin
def input(): return stdin.readline().strip()
N = int(input())
s = input()
t = input()
humming = 0
mismatches = {}
t_mismatches = {}
s_mismatches = {}
two = None
one = None
for i in range(N):
if s[i] != t[i]:
if not two:
if (t[i], s[i]) in mismatches:
two = (mismatches[(t[i], s[i])], i)
elif not one:
if s[i] in s_mismatches:
one = (s_mismatches[s[i]], i)
elif t[i] in t_mismatches:
one = (t_mismatches[t[i]], i)
t_mismatches[s[i]] = i
s_mismatches[t[i]] = i
mismatches[(s[i], t[i])] = i
humming += 1
if two:
print(humming - 2)
print(two[0] + 1, two[1] + 1)
elif one:
print(humming - 1)
print(one[0] + 1, one[1] + 1)
else:
print(humming)
print(-1, -1)
E. Bracket Sequence Quest
First, let's find the longest regular bracket Substring using a stack. To do that, Let's introduce a variable to store the index of the last unregular substring and let's iterate through the string. If the character is "$$$($$$", we will append its index to the stack. If the character is "$$$)$$$", we have three cases:
- If the stack is empty, it means the substring up to this point is not regular, and we will update our 'last unregular' variable to this index.
- After popping the last value from the stack, if the stack is empty, we know the substring that starts from the last unregular $$$index + 1$$$ to this position is regular.
- After popping the last value from the stack, if there is still a value on the stack, it means the substring that starts from the $$$index$$$ (that is on the top of the stack) $$$+ 1$$$ to this position is regular. So, every time we find a regular sequence, we will take the maximum. The next step is to count how many regular substrings there are with this maximum value, using the same approach again
s = input()
longest = 0
stack = []
last = -1
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
if stack:
stack.pop()
if stack:
longest = max(longest, i - stack[-1])
else:
longest = max(longest, i - last)
else:
last = i
res= 0
last = -1
stack = []
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
if stack:
stack.pop()
if stack:
if (i - stack[-1]) == longest:
res += 1
else:
if i - last == longest:
res += 1
else:
last = i
if longest == 0:
print(0, 1)
else:
print(longest, res)