Editorial-Rotten Apples | ENCODING FEBRUARY 22

editorial
, , , , , ,
1

PROBLEM LINK :

Practice
Contest Link
Problem Link

Author: Srinjoy Pal
Tester: Abhisekh Paul ,Sayan Poddar
Editorialist: Srinjoy Pal

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dynamic Programming, Prefix- Suffix

PROBLEM:

We need to remove all the X from a string of O & X. Where for removing X from the beginning or end costs 1 unit and removing from between two elements costs 2 units.

EXPLANATION:

For each i in S[i] from left we have two options :

  • remove all the apples till S[i]. Total Cost = i +1.
  • remove only that apple from the String. Total Cost= Previously Calculated Cost + 2.

Similarly from right we have the same options.

The TotalCost calculated and stored for both the cases, now we have to find the minimum cost for each i to be removed from the string.
Two possible outcomes are there:

  • remove some from left. The TotalCost is calculated and stored in left array.
  • remove from right to i+1 . The TotalCost is calculated in right array.
    We have to find the minimum for each i and add it to the Answer.

TIME COMPLEXITY:

O(n)

SPACE COMPLEXITY:

O(n)

SOLUTION:

Setter's Solution: C++ 
#include <bits/stdc++.h>
using namespace std;
int main(){
ll t;
cin>>t;
while(t--)
{
   string s;
cin>>s;
int n = s.size();
int ans= INT_MAX;
    vector<int>l(n,0) , r(n,0);
    if(s[0]=='X')
        l[0] = 1;
    for(int i=1;i<n;i++)
    {
        if(s[i]=='X')
		           
            l[i] = min(l[i-1]+2 , i+1);
        else
            l[i] = l[i-1];
    }
    
    if(s[n-1]=='X')
        r[n-1]=1;
    for(int i=n-2;i>=0;i--)
    {
        if(s[i]=='X')
            r[i] = min(r[i+1]+2,n-i);
        else
            r[i] = r[i+1];
    }
   
    ans = min(l[n-1],r[0]);
    for(int i=0;i<=n-2;i++)
    {
        ans = min(ans , l[i] + r[i+1]);
    }
cout<<ans<<endl;
 }
return 0;
}
Tester's Solution: Python 
def solve():
s = input()
l = len(s)
p = l
c = 0
for i in range(l):
    if s[i]=='X':
        c = min(c+2,i+1)
    p = min(p,c+l-i-1)
print(p)

t = int(input())
while(t>0):
solve()
t -= 1

Tester's Solution: Java 
import java.util.*;
class Feb6
{
public static void  main (String[] args) {
    Scanner sc=new Scanner(System.in);
    int t=Integer.parseInt(sc.nextLine());
    while(t>0)
    {
        String s[]=sc.nextLine().split("");
        int l=s.length;
        int p=l;
        int c=0;
       for(int i=0;i<l;i++)
       {
           if(s[i].equals("X"))
           {
                c=Math.min(c+2,i+1);
           }
            p = Math.min(p,c+l-i-1);
       }
       System.out.println(p);
        t--;
            
    }
}
}