You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFBR - Editorial

1
1

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

DP

PROBLEM:

You are given a sequence S of length at most 100 consisting of integers which represents brackets. A negative integer -x is an opening bracket of type x while x is a closing bracket of type x.

A balanced sequence of brackets is defined as usual (see the full problem statement for clarity).

We call a subsequence s of S valid if and only if s is a balanced sequence of brackets. Your task is to count the number of valid subsequences of S modulo 10^9 + 7.

QUICK EXPLANATION:

Define a dp[i][j] table where dp[i][j] := number of valid subsequence of S[i..j]. Notice that you can compute dp[i][j] if you know dp[i + 1][j] and positions of a closing bracket of type x in range from i + 1 to j if S[i] is an opening bracket of type x.

EXPLANATION:

Since input numbers can be quite large (up to 10^9) we want to compress them at the beginning in order to use them as array indices or use a hash table with O(1) lookup and insert time to do this.

Let pos[i][j][x] := list of positions of occurences of closing bracket of type x in S[i..j]

We can compute pos table in O(n^3) time using simple iteration over all 3 dimensions of it.

Let dp[i][j] := number of valid subsequences of S[i..j]

For simplicity, let's set dp[i][j] := 1 for i > j.

Let's assume that we have dp[i + 1][j] already computed. We want to extend it to dp[i][j]. There are two cases:

  1. We don't take a bracket at the i-th position, so dp[i][j] += dp[i + 1][j]
  2. If the bracket at the i-th position is an opening bracket of type x, we can try to take it to our subsequence.

While the first case is clear, the second one requires an explanation. If there are k closing brackets of type x in S[i + 1..j] we have k different possibilities to extend shorter subsequences, i.e. dp[i][j] += dp[i + 1][b - 1] * dp[b + 1][j] where b is a single position of a closing bracket of type x in S[i + 1..j]. Since we have pos table computed, we can get values for b using a quick lookup.

Time Complexity:

The time complexity is O(N^3) because computing pos and dp tables takes this much time and any other computation step doesn't have greater complexity.

AUTHOR'S AND TESTER'S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

This question is marked "community wiki".

asked 15 Dec '14, 19:29

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 15 Dec '14, 19:39


It seems that the test cases were changed and solutions were not rejudged. My submission http://www.codechef.com/viewsolution/5495967 got 90 points, missing task #0 and if I resubmit it, it gets 100 points.

I believe such test case changes should be warned by e-mail or don't make it default but let us choose to get an e-mail for such cases.

link

answered 16 Dec '14, 08:55

mogers's gravatar image

5★mogers
659716
accept rate: 25%

Can someone please explain it, I thought it was something related to Catalan numbers. and please explain the sample testcase also.

link

answered 17 Dec '14, 19:38

vidhyabhushan's gravatar image

2★vidhyabhushan
111
accept rate: 0%

-1 -2 9 2 -3 -4 3 4 8 8 1

there are to possibilities for |1| brackets - use it or not

-1 -2 9 2 -3 -4 3 4 8 8 1

(strong are used, but not very visible)

Very similar with |2| => 2 * 2

-1 -2 9 2 -3 -4 3 4 8 8 1

For 9 there is just one possibility - not to use it...

-1 -2 9 2 -3 -4 3 4 8 8 1

for |3| again use or do not use it - if you use it, there re no paired brackets, if you decide not to use it you can use |4| or not, so for the

-3 -4 3 4 8 8

there are 3 possibilities => 2 * 2 * 3 = 12. Clear?

(17 Dec '14, 19:47) betlista ♦♦3★
(17 Dec '14, 20:24) damn_me3★

check this out ! this editorial was super simple ! http://discuss.codechef.com/questions/58625/cannot-understand-chef-and-brackets

link

answered 19 Dec '14, 11:32

bicepjai's gravatar image

2★bicepjai
11
accept rate: 0%

if(a[i] < 0 && a[j] > 0 && a[i] + a[j] == 0) {
  dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1;
} else {
  dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
}
for(k = i + 1; k < j; k++) {
  if(a[k] < 0 && a[j] > 0 && a[k] + a[j] == 0) {
    break;
  } 
}
dp[i][j] = dp[i][j] + (dp[i][k-1] - dp[i+1][k-1]) * (dp[k][j] - dp[k][j-1]);

Using the same definition for dp[i][j] mentioned above. I'm weak at dp, but solving this question boosted me a lot :D
link

answered 17 Dec '14, 15:37

codejagger's gravatar image

2★codejagger
12
accept rate: 0%

edited 17 Dec '14, 15:39

A very nice editorial. Liked it as well as "power of dp" very much.

link

answered 18 Dec '14, 22:48

bhavesh_munot's gravatar image

3★bhavesh_munot
1981513
accept rate: 0%

Similar question http://www.spoj.com/problems/MREPLBRC/ . BTW can somebody tell how can I edit the editorial to add this link?

link

answered 31 Dec '14, 20:17

charizard's gravatar image

4★charizard
1601110
accept rate: 0%

edited 31 Dec '14, 20:17

The editorial is marked as community wiki and thus you can edit it. In the right side (middle) of the the place where the tags are written in the end, there's an option to edit it. See carefully.. "Related problems : to be updated soon" is written

(31 Dec '14, 23:48) damn_me3★

@damn_me Are you talking about "edited 15 Dec '14, 19:39" option?

(01 Jan '15, 00:50) charizard4★

Just above it, there's a line written as "Feel free to edit it" with a link.

(01 Jan '15, 13:00) damn_me3★

I do not understand why DP[i][j] is directly obtained from DP[i+1][j] (excluding i th bracket). I haave severe instict telling me to take DP[i][j-1] too i.e. the bracket was added on the last of the sequence i to j-1

link

answered 10 Jun '15, 10:51

xlee's gravatar image

2★xlee
131
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×3,746
×2,167
×228

question asked: 15 Dec '14, 19:29

question was seen: 6,607 times

last updated: 10 Jun '15, 10:51