PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Sorting
PROBLEM:
There are N points on a circle, each with a value and a color (red/blue).
You must make two cuts along the circle to split the points into two contiguous arcs. The endpoints of one arc must be red, and the endpoints of the other must be blue.
The score of a group of points is its maximum value.
Find the maximum possible sum of scores of two groups, across all ways of forming the groups.
EXPLANATION:
We deal with cyclic indices in this explanation; so saying index i-1 means N when i = 1 and so on.
Observe that if we have S_i = S_{i+1}, then points i and i+1 will always belong to the same group, no matter how we cut since we cannot cut between them as per the given constraints.
So, for each 1 \le i \le N such that S_i = S_{i+1}, we can join these two indices together into a larger ‘block’.
This will give us several blocks of elements, and these blocks will alternate in color as we move clockwise.
Note that within each block, only the maximum element matters; since all elements of a block will always be together anyway.
So, suppose there are k blocks, and let their maximums be m_1, \ldots, m_k.
Observe that no matter how we form the groups, the largest element of each group will be one of the m_i values.
Since our objective is to maximize the sum of maximums of the groups, clearly the absolute best we can hope for is to attain the sum of two largest m_i’s.
It’s not hard to see that it is in fact possible to turn the largest two m_i’s into the scores of the groups.
The simplest way is to just isolate the block with maximum m_i into its own group by cutting at its endpoints; then the other group consists of everything else and its maximum is the second-largest m_i.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
s = input()
maxs = []
curmx = a[0]
for i in range(1, n):
if s[i] == s[i-1]:
curmx = max(curmx, a[i])
else:
maxs.append(curmx)
curmx = a[i]
if s[0] == s[-1]: maxs[0] = max(maxs[0], curmx)
else: maxs.append(curmx)
maxs.sort(reverse=True)
print(maxs[0] + maxs[1])