REC20B Editorial

PROBLEM LINK:

Contest
Practice

SETTER: Ashutosh Shaw
TESTER: Prasann Kumar Gupta
Editorialist: Ashutosh Shaw

DIFFICULTY:

Easy-Medium

PREREQUISITE:

greedy

PROBLEM:

In the problem is given a string containing, ‘c’ or ‘+’. A Complete String is a non-empty string that consists of consecutive occurrences of “c++”, any number of times.

You can form a Complete String (if possible) by removing some of the characters from the string (possibly 0). Your task is to remove minimum number of the characters from the string (possibly 0), such that no Complete String can be formed from the resulting string.

EXPLANATION:

We need to eliminate all the possibility of subsequences having consecutive occurrences of “c++”. This implies that there should not be more than one ‘+’ after any ‘c’; there should be zero occurrences of ‘c’ before any two '+'s. Hence what we can do is, for every ith position, we can delete all the 'c’s from 1^{st} to (i-1)^{th} position and all the '+'s (except 1) from the i^{th} to the last position in the string (only if there are more than one ‘+’). Then, take the minimum of all the positions.

TIME COMPLEXITY:

O(n)

SOLUTIONS:

Setter's Solution

Solution: 53892731 | CodeChef

Tester's Solution

Solution: 53892768 | CodeChef

Feel free to share your approach. Suggestions are welcomed as always.

3 Likes

There’s also a straightforward dp solution. If i consider the string “c++” (1-indexed,lets call this string t) then dp[i][j] means the minimum no. of letters of remove from the pos [i , n] in the given string (call it string s) so that it doesn’t contain any subsequence of the part of word “c++” from pos [j, 3].

Simple transitions:
if( t[j] == s[i] ) => dp[i][j] = min( 1 + dp[i+1][j] (if i choose to delete letter s[i]) , dp[i+1][j+1] (If i choose not to delete letter s[i] ) )

Otherwise
dp[i][j] = dp[i+1][j] (No need to delete the letter s[i]).

Checkout my solution: Solution: 53883043 | CodeChef (Tho in my solution j is replaced with j+1 everywhere)

3 Likes

Thats pretty straightforward !

 for every ith position, we can delete all the 'c’s from 1st
 to (i-1)th position

I guess here we can delete the minimum of '+' or 'c' ? Am I correct ?
@ashvertex

can u provide any proof or intuition? its hard to think why this is always optimal.

@wargang (in case it doesn’t reach you).
The required type of string is of the following format:
\underbrace{++....+}_{\lt i} \underbrace{ccc...cc}_{\geq i}.
The section where the index is \geq i can also have at most one occurrence of +.
From here you can see that you’ll remove all occurences of c before i (@anshu23_1999 ) and all occurrences except one of + on and after i.