INOI 2016: Brackets

Computer Science Level 5

There are $k$ types of brackets each with its own opening bracket and closing bracket. We assume that the first pair is denoted by the numbers 1 and $k+1,$ the second by 2 and $k+2,$ and so on. Thus the opening brackets are denoted by $1, 2, \ldots, k,$ and the corresponding closing brackets are denoted by $k+1, k+2, \ldots, 2k,$ respectively.

Some sequences with elements from $1, 2, \ldots, 2k$ form well-bracketed sequences while others don't. A sequence is well-bracketed if we can match or pair up opening brackets of the same type in such a way that the following holds:

Every bracket is paired up.
In each matched pair, the opening bracket occurs before the closing bracket.
For a matched pair, any other matched pair lies either completely between them or outside them.

In this problem, you are given a sequence of brackets of length $N$ : $B[1], \ldots, B[N]$ , where each $B[i]$ is one of the brackets. You are also given an array of Values: $V[1],\ldots, V[N]$ .

Among all the subsequences in the Values array, such that the corresponding bracket subsequence in the B Array is a well-bracketed sequence, you need to find the maximum sum.

Task: Solve the above problem for this input.

Input Format

One line, which contains $(2\times N + 2)$ space separate integers. The first integer denotes $N.$ The next integer is $k.$ The next $N$ integers are $V[1],..., V[N].$ The last $N$ integers are $B[1],..., B[N].$

Constraints

$1 \leq k \leq 7$
$-10^6 \leq V[i] \leq 10^6$ , for all $i$
$1 \leq B[i] \leq 2k$ , for all $i$

Illustrated Examples

For the examples discussed here, let us assume that $k = 2$ . The sequence 1, 1, 3 is not well-bracketed as one of the two 1's cannot be paired. The sequence 3, 1, 3, 1 is not well-bracketed as there is no way to match the second 1 to a closing bracket occurring after it. The sequence 1, 2, 3, 4 is not well-bracketed as the matched pair 2, 4 is neither completely between the matched pair 1, 3 nor completely outside of it. That is, the matched pairs cannot overlap. The sequence 1, 2, 4, 3, 1, 3 is well-bracketed. We match the first 1 with the first 3, the 2 with the 4, and the second 1 with the second 3, satisfying all the 3 conditions. If you rewrite these sequences using [, {, ], } instead of 1, 2, 3, 4 respectively, this will be quite clear.
Suppose $N = 6, k = 3,$ and the values of $V$ and $B$ are as follows: Then, the brackets in positions 1, 3 form a well-bracketed sequence (1, 4) and the sum of the values in these positions is 2 (4 + (-2) =2). The brackets in positions 1, 3, 4, 5 form a well-bracketed sequence (1, 4, 2, 5) and the sum of the values in these positions is 4. Finally, the brackets in positions 2, 4, 5, 6 form a well-bracketed sequence (3, 2, 5, 6) and the sum of the values in these positions is 13. The sum of the values in positions 1, 2, 5, 6 is 16 but the brackets in these positions (1, 3, 5, 6) do not form a well-bracketed sequence. You can check the best sum from positions whose brackets form a well-bracketed sequence is 13.

The answer is 351549626.

1 solution

Agnishom Chattopadhyay
Jan 19, 2016

Here is my recursion with memoization solution to this problem:

/*31001, Agnishom Chattopadhyay, Brackets*/

#include <iostream>
#include <algorithm>

int V[701], B[701], cache[701][701], N, k;

int coolSum(int start, int end){
    //std::cout << "coolSum Call" << start << " " << end << std::endl;
    if (cache[start][end] != -123456789)
       return cache[start][end];
    if (start >= end){
        cache[start][end] = 0;
        return cache[start][end];
    }
    if ((start == 0) || (end == 0)){
        cache[start][end] = 0;
        return cache[start][end];
    }
    if (B[end] <= k){
        cache[start][end] = coolSum(start,end-1);   //An open bracket at the end contributes nothing
        return cache[start][end];
    }

    int maxTemp = -999999999;
    if (B[end] > k){
        for (int iii=start; iii < end; iii++)
           if (B[iii]==B[end]-k)
              maxTemp = std::max(maxTemp, V[iii]+V[end]+coolSum(iii+1,end-1)+coolSum(start,iii-1));
        maxTemp = std::max(maxTemp,coolSum(start, end-1));
        cache[start][end] = maxTemp;
        return maxTemp;
    }
}

int main(){

    std::cin >> N >> k;
    for (int iii=1; iii<=N; iii++)
       std::cin >> V[iii];
    for (int iii=1; iii<=N; iii++)
       std::cin >> B[iii];

    for (int iii=0; iii< 701; iii++)
       for (int jjj=0; jjj < 701; jjj++)
          cache[iii][jjj] = -123456789;

    std::cout << coolSum(1,N);


    return 0;
}

A detailed explanation can be found here

My solution in python looks similar but is shorter (take less than 30 sec computation) I don't use recursion

input = [int(x) for x in open("2_7.in.txt","r").read().split(' ')[0:-1]]

N = input[0]
k = input[1]
V = input[2:N+2]
B = input[N+2:2*N+2]

# tab_max[i][j] is the max valid subsequence sum between index i and j
tab_max = [[0] * N for i in range(0, N)]

# we assure tab_max is computed for all smaller subsequences contained in [i,j]
# by computing in assending distance for all dist = j - i
for dist in range(1, N):
    for i in range(0, N - dist):
        j = i + dist
        # is there a valid bracket surrounding the interval [i, j] ?
        m = V[i] + V[j] + tab_max[i+1][j-1] if B[i] + k == B[j] else 0
        # searching the best way to cut the interval [i, j] in two smaller optimal subsequences
        for cut in range(i, j):
            m = max(m, tab_max[i][cut] + tab_max[cut+1][j])
        tab_max[i][j] = m

print(tab_max[0][N-1])

Mathieu Guinin - 5 years, 3 months ago

I try it with these values and did not work

N = 6
k = 3
V = [4,5,-2,1,1,6]
B = [1,3,4,2,5,6]

Abdelhamid Saadi - 4 years, 4 months ago

Yeah my bad, it is obviously a typo B[i] + 7 should have been B[i] + k But I wonder if anyone care 3 years later ^^ I corrected my answer, thanks

Mathieu Guinin - 2 years, 4 months ago

INOI 2016: Brackets

The answer is 351549626.

1 solution

0 pending reports