PO2 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM

PREREQUISITES:

Greedy, DSU

PROBLEM:

Given an array P of size N. For each k\ (1\le k \le \lceil N/2 \rceil), determine the maximum possible value of \sum_{1}^{k} 2^{P_{a_i}} where:

  • 1\le a_i\le N, and
  • at most one of x and x+1 is in set a.

EXPLANATION:

Hint 1

Solve for when there are no duplicates in P, that is, P_i \ne P_j.

Solution

A greedy strategy can be employed to solve this.

Iteratively choose a selectable bag with the greatest number of gems in it (a bag is considered selectable if neither it or its adjacent bags have been picked before).
The optimality of this approach can be proven using the fact that the gems in each bag are powers of 2, and is left to the reader as an exercise.

The same method can also be used to solve when there are duplicates, but are not adjacent. That is, P_i \ne P_{i+1} for all i. Why won’t it work when this constraint is lifted?

Hint 2

We are left to solve for the case where there are consecutive duplicates.
In other words, when x is the maximum value of P_i over all selectable bags i and there exists a segment [l,r] such that P_l=P_{l+1}=\dots=P_r=x, there are multiple ways to select the bags (not all optimal).

By greedy intuition, we wish to maximise the number of bags selected from this range. When the length of the range n=r-l+1 is odd, we take \lceil n/2 \rceil bags and continue. How would you proceed when n is even?

Solution

There are two ways to select the maximum number of bags from the range when n is even - either bags \{l, l+2, \dots, r-1\} or bags \{l+1, l+3, \dots, r\}.
Regardless of how you choose it, the total sum of gems remains the same, so we can simply add n/2 bags to our set of selected bags.

However, selecting in one of the above ways causes either of bag l-1 or bag r+1 to become unselectable, respectively. Note that we cannot acertain which of the two bags should be made unselectable for an optimal solution.

But, observe that this restriction is equivalent to deleting the segment [l, r] from P and merging the remaining parts together; the constraint of not selecting both of bags l-1 and r+1 is preserved (as the bags are now adjacent).

Therefore, we can delete the segment [l, r] and continue with our iteration.

We are now left with managing the set of all selectable/adjacent bags, which can be tackled efficiently using sorted sets and DSU (used to query for the bags adjacent to a particular bag). Refer the below attached code for details.

Thus, given the sequence of bags we select to achieve maximum sum, we must output the sum of the first k bags for all valid k.

Test cases for debugging 
5
10
0 5 5 5 8 8 5 3 5 1
10
7 7 7 7 5 5 4 10 10 2
8
1 2 3 3 2 2 3 3
10
6 6 6 6 2 2 2 2 5 5
10
1 1 1 1 4 4 1 1 1 1

TIME COMPLEXITY:

Maintaining and updating the selectable bags (using sorted sets) takes O(N\log N) time. The DSU structure takes O(N\log N) overall.
Therefore, the total time complexity is

\approx O(N\log N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here
Author’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2 Likes