SNCOUP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY -
Easy - Medium

PROBLEM -
Given a grid of size 2 * n, where in some cells are marked SPECIAL. You have to put minimum line segments (walls) of any length you want such that each component made by the walls contains at most one cell which is marked SPECIAL.

EXPLANATION -

The solution is greedy and constructive in approach. There are 3 cases possible -

Case 1 - Both the rows has at least one snake.
Here we will firstly prove that putting an entire horizontal line segment is better than not putting one.

PROOF -
Use of NO horizontal line is only possible when there are no two snakes one below the other, so that means that each column has at most one snake, therefore the answer would be no. of snakes - 1 in case we do not use horizontal line. But, if we use the horizontal line we can see that the first snake in row 0 and the first snake in row 1 would be satisfied by only vertical line segment whereas earlier(with NO horizontal line segment) they required 2. This statement is false for the corner case when the row 0 has only 1 snake and also row 1 has only 1 snake. So this can be considered as a corner case, but apart from this in all the other cases, we can see that we have actually saved using one vertical line by introducing the horizontal line. Meaning that this horizontal line compensates for the vertical line that we saved. So the introduction of this horizontal line segment is equivalent to us for the first 2 snakes, but we can see that for the remaining snakes, we have a similar configuration to the previous case (when we did NOT use the horizontal line segment) BUT this time there is a horizontal line segment which is obviously more beneficial and ensures that the answer would either remain same or improve.

After the entire horizontal line segment between row 0 (0 - based indexing) and row 1 is made sound proof (add 1 to the answer for this line segment), a greedy solution is implemented. Notice here that because both the rows have snakes therefore there needs to be a horizontal segment and since we are free to make it of more length without increasing the cost, therefore the horizontal segment is made from one side of the grid to the opposite. Now we can greedily position the vertical segments, we will move from left to right and count the no. of snakes in the current compartment of row 0 and row 1, we will place the vertical line segment whenever we observe that the count of snakes in either row becomes greater than 1 and by placing the line segment, we now have opened a new compartment whose count of both the snakes would be 0 and updated accordingly.

Case 2 - Only a single row has all the snakes, then the no. of vertical line segments required is no. of snakes - 1.

Case 3 - No snake is there in the grid, then the answer is 0.

Below is the C++ implementation of the above mentioned logic -

#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;

int cnt[2];
string s[2];

void solve(){
	int n;
	cin>>n;
	cin>>s[0]>>s[1];

	cnt[0] = cnt[1] = 0;

	for(int i = 0; i < 2; i++){
		for(int j = 0; j < n; j++){
			if(s[i][j] == '*')	cnt[i]++;
		}
	}

	int ans = 0;

	if(cnt[0] > 0 and cnt[1] > 0){	//Case 1
		ans = 1;
		
		cnt[0] = cnt[1] = 0;
		for(int i = 0; i < n; i++){
			if(s[0][i] == '*')	cnt[0]++;
			if(s[1][i] == '*')	cnt[1]++;
			if(cnt[0] > 1 or cnt[1] > 1){
				ans++;
				cnt[0] = cnt[1] = 0;
				i--;
			}
		}
	}
	else if((cnt[0] == 0 and cnt[1] > 0) or (cnt[1] == 0 and cnt[0] > 0)){	//Case 2
		ans = max(cnt[0], cnt[1]) - 1;
	}
	else{	//Case 3
		ans = 0;
	}
	cout<<ans<<endl;
}

int main(){
	int t;
	cin>>t;
	while(t--)	solve();
}

Time Complexity - O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

2 Likes

Got the answer at the last moment and i forgot to comment out a debugging print statement and missed out qualifying for the next round, ahhhh i hate this :frowning:

Please attach the Practice link to problem

Can somebody explain case 1 more clearly?

#include<bits/stdc++.h>
using namespace std;

int main()
{
int a,b,a_i,b_i,a_t,t,co,h1,h2,l,fence,n,f,s,fence2;
cin>>t;
for(a_t=1;a_t<=t;a_t++)
{
string str1,str2;
cin>>n>>str1>>str2;
l=n;
h1=0;h2=0;fence=0;
for(a_i=0;a_i<l;a_i++)
{
if(str1.at(a_i)==’’)
h1++;
if(str2.at(a_i)==’
’)
h2++;
}

    if((h1+h2)<=1)
    {
        cout<<0<<endl;
        continue;
    }

   else if((h1+h2)==2)
    {
        cout<<1<<endl;
        continue;
    }
    //

   else if(h1==0)
    {
        cout<<(h2-1)<<endl;
        continue;
    }
    else if(h2==0)
    {
        cout<<(h1-1)<<endl;
        continue;
    }
    //
        fence=1;f=0;s=0;
        /*for(a_i=0;a_i<l;a_i++)
        {
            if(str1.at(a_i)=='*'&&str2.at(a_i)=='*')
            {
                fence2=1;
                break;
            }
        }*/
        for(a_i=0;a_i<l;a_i++)
        {

            if(str1.at(a_i)=='*')
            {
                f++;
                //h1--;
            }
            if(str2.at(a_i)=='*')
            {
                s++;
                //h2--;
            }
            if(f==2&&s!=2)
            {
                fence++;
                f=1;
                //s=s;
            }
            if(s==2&&f!=2)
            {
                fence++;
                s=1;
                //f=0;
            }
            if(s==2&&f==2)
            {
                fence++;
                s=1;
                f=1;
            }
    }
    cout<<fence<<endl;

}

}
in which case it’s not correct? what’s wrong with it??

in which case it is wrong??
can anyone explain??

#include<iostream>
    using namespace std;
    //int iequ(int m,int n,int a[m][n]);
    int main(){
    	int t;
    	scanf("%d", &t);
    	for(int i=0;i<t;i++){
    		int n;
    		scanf("%d",&n);
    		char a[2][n];
    		int b1[n],b2[n];
    		int ind1=-1,ind2=-1;
    		for(int j=0;j<2;j++){
    		for(int k=0;k<n;k++){
    		//scanf("%c",&a[j][k]);
    		cin>>a[j][k];
    		}
    		}
    		int hflag=0,count=0;
    		for(int p=0;p<n;p++){
    			if(a[0][p]=='*'){
    			//	if(a[1][p]=='*' || a[1][p+1]=='*'){
    				for(int u=p;u<n;u++){
    					if(a[1][u]=='*'){
    								hflag=1;
    								count++;
    								u=n;
    								p=n;
    							}
    							}
    			}
    		}
    		int rw;
    		if(hflag==1){
    			//cout<<"hi"<<endl;
    			for(int x=0;x<n;x++){
    				for(int y=0;y<2;y++){
    					if(a[y][x]=='*'){
    						for(int z=x+1;z<n;z++){
    							if(a[y][z]=='*'){
    								if(y==0){
    								rw=1;
    								}
    								else{
    								 rw=0;
    								}
    								int fff=0;
    								for(int l=x;l<=z;l++){
    									if(a[rw][l]=='*'){
    										fff=1;
    									int ff=0;
    										for(int o=l+1;o<=z;o++){
    											if(a[rw][o]=='*'){
    												count++;
    												ff=1;
    												y=rw-1;
    												x=o;
    												o=z+1;
    											}
    										}
    										if(ff==0){
    											count++;
    											x=z;
    											y=y-1;
    										}
    										l=z+1;
    									}
    								}
    								if(fff==0){
    									count++;
    									y=y-1;
    									x=z;
    								}
    								z=n+1;
    							}
    						}
    					}
    				}
    			}
    		}
    		else{
    			for(int x=0;x<n;x++){
    				for(int y=0;y<2;y++){
    					if(a[y][x]=='*'){
    						for(int z=x+1;z<n;z++){
    							for(int i1=0;i1<2;i1++){
    								if(a[i1][z]=='*'){
    									count++;
    									y=i1-1;
    									x=z;
    									i1=2;
    									z=n;
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    		cout<<count<<endl;
    	}
    }

This problem seemed really easy to me, as I deducted pretty much exactly what the editorial says in the first hour of the contest. But I got about 12 WA’s. Why? I have no clue what test case could possibly fail.

https://www.codechef.com/viewsolution/13971955

Please tell the input where it fails
https://www.codechef.com/viewsolution/13960603

What is wrong with my this code, it is working fine for all tests which i could think.
Please can someone tell where it is failing ???
https://www.codechef.com/viewsolution/13954302

what is wrong in my code

#include<stdio.h>
int main()
{
    int T,i;
    scanf("%d",&T);
    for(i=0;i<T;i++)
     {
         int n,c=0,d=0,u=0,p=0,h=0,s=0,j,e=-1;
         scanf("%d",&n);
         char A[2][n+1];
         scanf("%s",A[0]);
         scanf("%s",A[1]);
         for(j=0;j<n;j++)
         {
            if(s==0)
             {
               if((A[0][j]=='*')&&(A[1][j]=='*'))
                {   
                    c++;
                    h=1;
                    p=1;
                    s=1;
                    u=1;
                    d=1;
                    e=c;
                }
                else if(A[0][j]=='*')
                 {
                     u=1;
                     s=1;
                     p=1;
                 }
                 else if(A[1][j]=='*')
                 {
                     d=1;
                     s=1;
                     p=1;
                 }
             }
             else
             {
            if((A[0][j-1]=='*')&&(p==1)&&(u==0)&&(e<c))
            {
                u=1;s=1;e=c;
            }
            if((A[1][j-1]=='*')&&(p==1)&&(d==0)&&(e<c))
            {
                d=1;s=1;e=c;
            }
            
                if((A[0][j]=='*')&&(A[1][j]=='*'))
                {
                    if(h==0)
                    {
                        c++;
                        h=1;
                        if((u==1)||(d==1))
                        {
                            c++;
                            u=0;
                            d=0;
                        }
                    }
                    else
                     {
                      if((u==1)||(d==1))
                      {
                          c++;
                          u=0;
                          d=0;
                      }
                     }
                }
                else if(A[0][j]=='*')
                 {
                     if(h==0)
                     {
                         if(d==1)
                         {
                            h=1;
                            c++;
                         }
                         else if(u==1)
                         {
                             c++;
                             u=0;
                             d=0;
                         }
                         
                     }
                     else
                     {
                         if(u==1)
                         {
                             c++;
                             u=0;
                             d=0;
                         }
                     }
                 }
                 else if(A[1][j]=='*')
                 {
                     if(h==0)
                     {
                         if(u==1)
                         {
                             h=1;
                             c++;
                         }
                         else if(d==1)
                         {
                             c++;
                             u=0;
                             d=0;
                         }
                     }
                     else
                      {
                          if(u==1)
                          {
                              c++;
                              u=0;
                              d=0;
                          }
                      }
                 }
                
            }
         }
         if(s==1)
         printf("%d\n",c);
         else
         printf("%d\n",0);
     }
     return 0;
}

The main logic was to find that for the test case(s) with

1010
0101

10|10
_____
01|01

The answer would be 2 (one horizontal and one vertical). Basically, you need to find every alternating snake occupied houses sub-array. Count the number of alternating snake occupied houses (say, x) and the number of walls in this sub-array would be (x-1)/2. (in this case, (4-1)/2 = 1, plus the horizontal one)

You don’t need to put a vertical wall between 2 alternating snake occupied houses if the horizontal wall already separates them.

2 Likes

Yes, I tested for that exception at the beginning.
@devilhector My code for only one line containing 's was to split on "" with a -1 modifier and subtract 2 from the resulting length. Through numerous copy and pasting, the -2’s became -1’s from an earlier submission. This is very frustrating.

I have a much simpler solution than this official solution. :slight_smile:

Please tell what is wrong with this code
@sai_rathan

@arvindpunk Thanks for the testcase :slight_smile: …I tried so hard but was not able to submit it !!!

i have done the question in exactly the same manner still i got wrong answer . I dont have enough karma to upload my solution . Is thera any way that i can get to know which case i am missing

Can any one tell me where my solution is failing…
https://www.codechef.com/viewsolution/13957070

whats wrong in This … ?

for _ in range(int(input())):
n = int(input())
s1 = str(input())
s2 = str(input())
s3 = str()
d = 0
for i in range(n):
    if s1[i] == '*' and s2[i] == '*':
        d+=1
        break
for j in range(n):
    if s1[j] == '*' or s2[j] == '*':
        s3+='*'

if d == 1 or len(s3) == 0:
    print(len(s3))
else:
    print(len(s3) - 1

I used a different approach, was getting a wrong answer but couldn’t figure a test case for which this will fail. Consider the number of ‘'s in row 1 as stars1, and the number of stars in row2 as stars2. Also, for columns where both row 1 and row 2 have a '’, count them in a variable common. So the approach is that if(common>0), add a fence(the horizontal fence). And then the number of vertical fences that will be added will be= (stars1 + stars2- common -1) .
I cant figure out why will it fail.Can someone point out a test case. Here is the code:

https://www.codechef.com/viewsolution/13960878

Can any one help me out where I went wrong
https://www.codechef.com/viewsolution/13933535
I was really working from yesterday night and could not find where it is failing.So please and please help me out