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

×

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
TESTER's solution: Here

This question is marked "community wiki".

asked 01 Jun '17, 18:15

sidhant007's gravatar image

6★sidhant007
179819
accept rate: 12%

edited 01 Jun '17, 21:56

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

Users are requested to provide a submission link instead of pasting the entire code.

(02 Jun '17, 12:11) vijju123 ♦♦5★

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.

link

answered 01 Jun '17, 21:48

arvindpunk's gravatar image

3★arvindpunk
632
accept rate: 7%

edited 01 Jun '17, 21:50

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 :(

link

answered 01 Jun '17, 21:10

simha's gravatar image

4★simha
1525
accept rate: 0%

Please attach the Practice link to problem

link

answered 01 Jun '17, 21:10

vivek96's gravatar image

2★vivek96
533221
accept rate: 8%

Can somebody explain case 1 more clearly?

link

answered 01 Jun '17, 21:19

hb11's gravatar image

4★hb11
1117
accept rate: 0%

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??

link

answered 01 Jun '17, 21:20

maruf_robin's gravatar image

2★maruf_robin
1
accept rate: 0%

@maruf_robin

Your code raises an error empty character constant because in this condition " if(str1.at(a_i)=='') " your are comparing a character with empty character. If I assume that your counting '*' there then your code fails for

input:

5

.*.*.

*.*.*

Your Output

4

Expected :

3

Your code also fails if I assume that char with you are comparing is'.' instead of '*' as mentioned I my previous assumption. Correct me if I'm wrong.

(01 Jun '17, 22:12) sai_rathan4★
1

Nice work @sai_rathan :)

(01 Jun '17, 23:49) vijju123 ♦♦5★

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;
        }
    }
link

answered 01 Jun '17, 21:27

karthikeya123's gravatar image

3★karthikeya123
1
accept rate: 0%

edited 01 Jun '17, 23:50

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

@karthikeya123

Your code gives a compilation error because you have used scanf function for taking test case input without including stdio.h . Correct me if I'm wrong.

(02 Jun '17, 09:05) sai_rathan4★

@sai_rathan It did work without any compilation error.

(02 Jun '17, 10:14) karthikeya1233★

@karthikeya123

I tried running your code in both Codechef ide and codeblocks both raised a compilation error. Ok I will try to find an error test case for your code.

(02 Jun '17, 12:18) sai_rathan4★

@karthikeya123

Your Code is not working for this case:

Input: 3

.**

**.

Your code's Output: 2

Expected Output: 3

(02 Jun '17, 12:26) sai_rathan4★

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

link

answered 01 Jun '17, 21:27

cheesecoffee's gravatar image

2★cheesecoffee
212
accept rate: 0%

1

@cheesecoffee Your input fails for

1 2 .. **

Output should be 1 whereas your output is 2.

(01 Jun '17, 22:00) devilhector2★

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

link

answered 01 Jun '17, 21:29

akchamp's gravatar image

4★akchamp
12419
accept rate: 20%

2

@akchamp

Your code fails for this case:

Input:

3

.**

**.

Your Output: 2

Expected Output: 3

(01 Jun '17, 22:31) sai_rathan4★

thanxx man.

(01 Jun '17, 23:18) akchamp4★

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

link

answered 01 Jun '17, 21:34

rahul26724's gravatar image

2★rahul26724
1
accept rate: 0%

edited 01 Jun '17, 21:48

I Dare you if you can tell where it will fail.

(01 Jun '17, 23:38) rahul267242★
2

The test cases already found where you were wrong so no point in dare XD.

On a side note- Request nicely and people will help :)

(01 Jun '17, 23:51) vijju123 ♦♦5★

thanks @vijju123 , I got the failure :( but late . I was tried more then 50 inputs but was not finding the failure .So i was very exited if someone reply as early as possible. Failure: .**

**.

(02 Jun '17, 23:06) rahul267242★

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;
}
link

answered 01 Jun '17, 21:37

prince367's gravatar image

2★prince367
714
accept rate: 0%

edited 01 Jun '17, 23:52

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

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.

link

answered 01 Jun '17, 22:01

cheesecoffee's gravatar image

2★cheesecoffee
212
accept rate: 0%

edited 01 Jun '17, 22:07

I have a much simpler solution than this official solution. :-)

link

answered 01 Jun '17, 22:21

saurabh0612's gravatar image

2★saurabh0612
102
accept rate: 0%

Please tell what is wrong with this code @sai_rathan http://ideone.com/Ym6D1T

link

answered 01 Jun '17, 22:28

urdarinda's gravatar image

3★urdarinda
8116
accept rate: 0%

edited 01 Jun '17, 22:29

@urdarinda

Sorry I'm unable to find any case for which your code is not working.

(01 Jun '17, 23:20) sai_rathan4★
1

thank you for trying! @sai_rathan Can anyone provide a test case for which the code does not work?

(01 Jun '17, 23:37) urdarinda3★

@urdarinda

if(arr[0][i]=='*' && arr[1][i]=='.' && arr[0][i+1]=='.' && arr[1][i+1]=='*'){
                ans--;
                i++;
            }
            else if(arr[0][i]=='.' && arr[1][i]=='*' && arr[0][i+1]=='*' && arr[1][i+1]=='.'){
                ans--;
                i++;
            }

I think in the if condition your trying to access a[0][i+1] but when you are accessing last element it will try to access its next element which is not present. I think this is causing some trouble for larger value of 'n' though I'm not sure.

(01 Jun '17, 23:44) sai_rathan4★

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

link

answered 01 Jun '17, 22:29

stillhungry's gravatar image

4★stillhungry
0
accept rate: 0%

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

link

answered 01 Jun '17, 22:40

kunal12libra's gravatar image

3★kunal12libra
1235
accept rate: 0%

1

Else you can paste your code as a answer so that other users can also take a chance to find error case

(01 Jun '17, 22:46) sai_rathan4★

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

link

answered 01 Jun '17, 22:51

amar555's gravatar image

2★amar555
1
accept rate: 0%

# 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
link

answered 01 Jun '17, 22:59

shivank98's gravatar image

2★shivank98
1
accept rate: 0%

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

link

answered 01 Jun '17, 23:30

rak_9792's gravatar image

2★rak_9792
112
accept rate: 0%

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

link

answered 02 Jun '17, 00:28

nishith365's gravatar image

2★nishith365
1
accept rate: 0%

edited 02 Jun '17, 00:55

(02 Jun '17, 03:21) thegeniushead1★

#include<bits stdc++.h="">

define S_ a[0][i]=='*' && a[1][i]=='.'

define _S a[0][i]=='.' && a[1][i]=='*'

define SS a[0][i]=='' && a[1][i]==''

define __ a[0][i]=='.' && a[1][i]=='.'

define SNAKE a[0][i+1]==''||a[1][i+1]==''

using namespace std;
int main(){
inputSection //----------------------------------------------- int firstIndex = 0; int lastIndex=0;
for(int i=0;i<n;i++) {<br=""> if(a[0][i]=='' || a[1][i]=='')
{ firstIndex = i; break; }
}
for(int i=n-1;i>=firstIndex;i--) {
if(a[0][i]=='' || a[1][i]=='') { lastIndex = i; break; }
} bool hz = false; int vt =0;
if(firstIndex==lastIndex && a[0][firstIndex]==''&&a[1][lastIndex]=='') {
hz=true; }
else if(firstIndex==lastIndex) {
hz = false; vt=0; }
for(int i = firstIndex;i<lastindex;) {<br=""> if(S_) {
if(!SNAKE) {i++;continue;}
i=i+1; if(S_)
vt++;
else if(SS){hz=true;
vt++;}
else if(S){
hz= true;
}
}
else if(_S){
if(!SNAKE)
{
i++;
continue;

}
i= i+1;
if(_S)
{
vt++;
}
else if(S
) {
hz=true; }
else if(SS){ hz= true;
vt++;
}
}
else if( SS){
if(!SNAKE)
{
i++;
continue;

}
i= i+1;
if(S)
{
vt++;
hz=true;
}
else if(S
) {
hz=true;
vt++;
}
else if(SS){ hz= true; vt++;
}
else{ hz=true; }
}
else // increment i {i++;}
}
if(hz)
cout<<vt+1<<endl;<br> else
cout<<vt<<endl;<br/> }
return 0; }
Can AnyOne help me in getting error in this code Here SOME Macros are used _-->Dot ans S-->Snake I m checking pair wise snake and next snake and then applying the opartion on vertical line and horizontal line i used a boolean for Hz line if it exists then add 1 to vertical lines...

link

answered 02 Jun '17, 00:29

banaji's gravatar image

2★banaji
1
accept rate: 0%

edited 02 Jun '17, 00:44

https://www.codechef.com/viewsolution/13933535 This is the link to mmy code.So please help me out where I went wrong

link

answered 02 Jun '17, 00:29

nishith365's gravatar image

2★nishith365
1
accept rate: 0%

If anyone want's to check out a correct code

It's quite simple

link

answered 02 Jun '17, 00:31

ak_n's gravatar image

0★ak_n
1
accept rate: 0%

Anyone who can tell me a test case ? Here is my code. Getting WA for no reason.

 #include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,t;
    char a[200010];
    char b[200010];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        scanf(" %s",a);
        scanf(" %s",b);
        int cnt=0;
        int upper=0;
        int lower=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]=='*')
                upper++;
            if(b[i]=='*')
                lower++;
            if(upper>=1 && lower>=1)
            {
                cnt=1;
                break;
            }
        }
        upper=lower=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]=='*' && b[i]=='*')
                cnt++;
            else if(a[i]=='*')
            {
                upper++;
                cnt++;
            }
            else if(b[i]=='*')
            {
                lower++;
                cnt++;
            }
            if(upper==1 && lower ==1)
            {
                cnt--;
                lower=upper=0;
            }
            if(lower>1 || upper>1)
            {
                if(a[i]=='*' && b[i]=='.')
                {
                        upper=1;
                        lower=0;
                }
                else if(b[i]=='*' && a[i]=='.')
                {
                    lower=1;
                    upper=0;
                }
                else
                    upper=lower=0;
            }
            //printf("at %d count= %d\n",i,cnt);
        }
        if(cnt)
            cnt--;
        printf("%d\n",cnt);
    }
    return 0;
}
link

answered 02 Jun '17, 00:33

floating_point's gravatar image

3★floating_point
1
accept rate: 0%

@floating_point

Your code fails for this case

Input:

3

.**

**.

Your Output: 2

Expected Output :3

(02 Jun '17, 09:17) sai_rathan4★

doing i-- in the last loop won't cause the loop to run infinitely? In c++ code given here?

link

answered 02 Jun '17, 00:47

abhilash150596's gravatar image

2★abhilash150596
1
accept rate: 0%

edited 02 Jun '17, 00:48

//ANYHELP why this code is not accepted?
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;

    int main(){

int t;
cin>>t;
for(int r=0;r<t;r++){
           int q;
          cin>>q;
      char s[2][q];
    char d;
for(int i=0;i<2;i++){
for(int j=0;j<q;j++)
 cin>>s[i][j];
 }  
 int c=0;
    for(int i=0;i<2;i++){
for(int j=0;j<q;j++)
 if(s[i][j]=='*')c++;
 }

    int count=0;
  int s1=0;
 int s2=0;
 d='a';
for(int k=0;k<q;k++){
if(s[0][k]=='*' || s[1][k]=='*') count++;
  if(s[0][k]=='*') s2=1;
if(s[1][k]=='*') s1=1;
if(s[0][k]=='*' && s[1][k]=='*') d='c';
}
int hor=s1+s2;

if(d=='c'){
if(count-1 == 1 && hor==2 && c>2){cout<<2<<endl;  }
  if(count-1 == 0 && hor==2 && c==2){cout<<1<<endl;  }
  if(count-1 == 1 && hor==2 && c==2){cout<<1<<endl;  }
if(count-1 > 1 && hor==2 ){cout<<count+hor-2<<endl;  }
if(count-1 >= 1 && hor!=2 ){cout<<count-1<<endl;  }
if(count-1 ==0 && hor!=2 ){cout<<0<<endl;  }
if(count-1 ==0 && hor!=2 && c==2){cout<<1<<endl;  }

}

else if(d!=c){
  if(count>=1)cout<<count-1<<endl; 
  else cout<<0<<endl;}


}
return 0;

}

  1. Blockquote
link

answered 02 Jun '17, 01:48

sauravsinha137's gravatar image

2★sauravsinha137
1
accept rate: 0%

edited 02 Jun '17, 12:09

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

link text anyhelp on why this code not accepted will be highly appreciated!!

link

answered 02 Jun '17, 01:55

sauravsinha137's gravatar image

2★sauravsinha137
1
accept rate: 0%

(02 Jun '17, 03:08) thegeniushead1★

Can anyone please provide a test case where my code fails?

Solution link : https://ideone.com/AVh0zv Thanks:)

link

answered 02 Jun '17, 02:49

thegeniushead's gravatar image

1★thegeniushead
1
accept rate: 0%

Anyone, please?

(02 Jun '17, 13:55) thegeniushead1★

whats wrong with my solution-

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        int n,i;
        cin>>n;
        char a[2][n];
        for (i=0;i<n;i++)
        {
            cin>>a[0][i];
        }
        for (i=0;i<n;i++)
        {
            cin>>a[1][i];
        }
        string s="";
        for (i=0;i<n;i++)
        {
            if (a[0][i]=='*'&&a[1][i]=='*')
            {
                s+="h";
            }
            else if (a[0][i]=='*'&&a[1][i]=='.')
            {
                s+="u";
            }
            else if (a[0][i]=='.'&&a[1][i]=='*')
            {
                s+="d";
            }
            else if (a[0][i]=='.'&&a[1][i]=='.')
            {
                s+="n";
            }
        }
        int fences=0;
        int x=n-1;
        for (i=0;i<(n);i++)
        {
            if (s[i]=='h'||s[i]=='u'||s[i]=='d')
            {
                x=i;
                break;
            }
        }
        for (i=x+1;i<n;i++)
        {
            if (s[i]=='h'||s[i]=='u'||s[i]=='d')
            {
                fences++;
            }
        }
        int hexist=0;
        for (i=0;i<n;i++)
        {
            if (s[i]=='h')
            {
                hexist=1;
                break;
            }
        }
        if (hexist==1)
            fences++;
        cout<<fences<<endl;
    }
    return 0;
}
link

answered 02 Jun '17, 08:36

fourarms's gravatar image

2★fourarms
1
accept rate: 0%

edited 02 Jun '17, 12:09

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

Somebody please correct me where i went wrong? Here's my logic: case 1: if the snakes are in row 1 or 2 or both but not vertically adjacent then i gave solution as total no. of snakes -1. case 2:if the snakes are in row 1 or 2 or both and least 2 snakes are vertically adjacent then i gave solution as 1 + total no. of snakes -1 - no. of vertically adjacent pairs. case 3 : if there is 0 or 1 snake in total then i gave solution as 0. https://www.codechef.com/viewsolution/13947900

link

answered 02 Jun '17, 09:03

manish7294's gravatar image

2★manish7294
1
accept rate: 0%

@manish7294

There is an error in your logic for case 1.

Now consider a test case

5

.*.*.

*.*.*

Answer according to your logic will be 4 but correct answer is 3

(02 Jun '17, 09:09) sai_rathan4★

@sai_rathan my program i also giving output as 3. As the 1st and 2nd column have vertical adjacent snakes so this is my case 2.

(02 Jun '17, 09:45) manish72942★

Can anyone pls explain why is "i" decremented in the Case 1(inside the if condition of for loop)??

link

answered 02 Jun '17, 09:28

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

please Suggest in which test case following code fails

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        string arr[2];
        cin>>arr[0]>>arr[1];
        ll ver=0,hori=0;
        ll count=0;     
        for(ll i=0;i<n;i++)
        {   
            if(arr[0][i]==arr[1][i] && arr[0][i]=='*')
                hori=1;
            if(arr[0][i]=='*' || arr[1][i]=='*')
                count++;

        }
        ll val=1,up=0,low=0;
        for (int i = 0; i < n; ++i)
        {
            if(arr[0][i]=='*')
                up++;
            if (arr[1][i]=='*')
                low++;
            if(up>1)
            {
                up=1;low=0;val++;
            }
            if(low>1)
            {
                low=1;up=0;val++;
            }
        }
        ll k=min(count-1+hori,val);
        if(k>0)
            cout<<k<<"\n";
        else 
            cout << "0\n";
    }

}
link

answered 02 Jun '17, 10:19

s_17's gravatar image

2★s_17
1
accept rate: 0%

edited 02 Jun '17, 12:08

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

@s_17

Your Code is not working for

Input:

.**

**.

Your code's Output: 2

Expected Output :3

(02 Jun '17, 12:28) sai_rathan4★

thanks @vijju123.

(03 Jun '17, 16:23) s_172★
#include <iostream>

using namespace std;

int main()
{
    int testcases ;
    cin >> testcases ;
    for (int t = 0 ; t < testcases ; t++){
        int n ;
        cin >> n ;
        char a[2][n];
        for (int i = 0 ; i < 2 ; i++){
            for (int j = 0 ; j < n ; j++){
            cin >> a[i][j];
            }
        }

        int up_snake = 0 ; // if there is snake up
        int down_snake = 0 ; // if there is snake down
        int fence = 0 ; // answer
        int start_up = 0  ; // first snake up
        int start_down = 0 ; // first snake down
        for (int i = 0 ; i < n ; i++){
            if (a[0][i] == '*'){
                up_snake = 1 ;
                start_up = i ;
                break ;
            }
        }
        for (int i = 0 ; i < n ; i++){
            if (a[1][i] == '*'){
                down_snake = 1 ;
                start_down = i ;
                break ;
            }
        }


        if (up_snake == 1 && down_snake == 1){
            fence++ ; // for between fence
        }
       // cout << "basic fence " << fence << endl ;
        int start_index = start_up ; // starting index
        int count_up = 1 ;
        int count_down = 0 ;

        if (start_up > start_down){
            count_down = 1 ;
            count_up = 0 ;
            start_index = start_down ;

        }
        if (start_up == start_down){
            count_up = 1 ;
            count_down = 1 ;
        }
        if (start_index == n-1){
            cout << 0 << endl ;
        }
        else {

            for (int i = start_index+1 ; i < n ; i++){
                if (a[0][i] == '*' && a[1][i] == '*'){
                    fence ++ ;
                    count_down = 1 ;
                    count_up = 1 ;
                }

                else if (a[0][i] == '*' && count_up == 1){
                    fence ++ ;
                    count_down = 0 ;

                }
                else if (a[0][i] == '*' && count_up == 0){
                    count_up ++ ;
                }
                else if (a[1][i] == '*' && count_down == 1){
                    fence ++ ;
                   // cout << " fence down at "  <<i << endl  ;
                   count_up = 0 ;

                }
                else if (a[1][i] == '*' && count_down == 0){
                    count_down ++ ;
                }

                }

                cout << fence << endl ;
            }

        }


    return 0;
}

can anyone tell me in what am i doing wrong ????

link

answered 02 Jun '17, 11:18

piyush_iit's gravatar image

2★piyush_iit
1
accept rate: 0%

edited 02 Jun '17, 12:10

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

@piyush_iit

Faild Case:

Input:

3

..*

..*

Expected Output:1

Your code's Output :0

(02 Jun '17, 12:37) sai_rathan4★
#include<stdio.h>
#include<string.h>
int main()
{
    int t,n,i,first,second,a,b,count;
    char arr[2][100004];
    scanf("%d",&t);
    while(t--)
    {
        first=0;
        second=0;
        count=0;
        a=0;b=0;
        scanf("%d",&n);
        scanf("%s",&arr[0]);
        scanf("%s",&arr[1]);
        for(i=0;i<n;i++)
        {
            if(arr[0][i]=='*')
                first++;
            if(arr[1][i]=='*')
                second++;
        }
        if(first+second<2)
        {
            printf("0\n");
            continue;
        }
        if(first==1&&second==1)
        {
            printf("1\n");
            continue;
        }
        if(first==0)
        {
            printf("%d\n",second-1);
            continue;
        }
        if(second==0)
        {
            printf("%d\n",first-1);
            continue;
        }
        for(i=0;i<n;i++)
        {
            if(arr[0][i]=='*')
                a++;
            if(arr[1][i]=='*')
                b++;
            if(a==2)
            {
                count++;
                a--;
                if(b>0)
                    b--;
            }
            if(b==2)
            {
                count++;
                b--;
                if(a>0)
                    a--;
            }
        }
        printf("%d\n",count+1);
    }
}

this is my code please tell where it is failing

link

answered 02 Jun '17, 11:53

kunal12libra's gravatar image

3★kunal12libra
1235
accept rate: 0%

edited 02 Jun '17, 12:03

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

i hope you guys can understand this i cant upload image due to lack of karma and on pasting the code it appears like this but there is no compilation error just tell where the logic went wrong thanks

(02 Jun '17, 11:56) kunal12libra3★

Share your submission link

(02 Jun '17, 12:00) hruday9684★

Fixed the format.

(02 Jun '17, 12:04) vijju123 ♦♦5★
1

@kunal12libra

Your code doesn't work for the test case below:

Input:

.**

**.

Your code's output: 2

Expected Output : 3

(02 Jun '17, 12:13) sai_rathan4★
link

answered 02 Jun '17, 14:46

abhisheksahaji's gravatar image

1★abhisheksahaji
1
accept rate: 0%

edited 02 Jun '17, 14:51

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/13961222

link

answered 02 Jun '17, 16:34

krishna1309's gravatar image

3★krishna1309
1
accept rate: 0%

Can anyone please tell me why I'm getting WA, here is the link to my code https://www.codechef.com/viewsolution/13962362

link

answered 02 Jun '17, 17:21

sanny_1's gravatar image

4★sanny_1
1
accept rate: 0%

Can someone please tell what is wrong with my code. If possible give the test case where it fails. Here is the link to my code: https://www.codechef.com/viewsolution/13934000

link

answered 02 Jun '17, 17:51

garima_chadha's gravatar image

4★garima_chadha
1
accept rate: 0%

please someone tell whats wrong with this program https://www.codechef.com/viewsolution/13944522

link

answered 02 Jun '17, 17:54

uditmar_24's gravatar image

3★uditmar_24
1
accept rate: 0%

what is wrong with my code i couldn't understand why i got a wrong answer... import java.util.*; class snckdwn { public static void main(String[] args) { Scanner ob = new Scanner(System.in); int t = ob.nextInt(); while(t-- > 0) { int n = ob.nextInt(); char a[][] = new char[2][n]; for(int i=0;i<2;i++) { String s = ob.next(); for(int j=0;j<n;j++) { a[i][j] = s.charAt(j); } }

        boolean upper = false;
        boolean lower = false;
        boolean hl = false;
        boolean left = false;
        boolean leftdiag = false;
        boolean rightdiag = false;
        int count = 0;
        for(int i=0;i<n;i++)
        {
            char te, te1, be, be1;
            te = a[0][i]; 
            be = a[1][i];

            if(hl==false)
            {
                if(te=='*')
                    upper = true;
                if(be=='*')
                    lower = true;
            }
            if(upper==true&&lower==true)
            {
                upper = lower = false;
                hl = true;
                count++;
            }
            if(te=='*'&&be=='.')
            {
                if(rightdiag==true)
                {
                    rightdiag = false;
                    continue;
                }
                if(leftdiag==true)
                {
                    count++;
                    continue;
                }
                leftdiag = true;
                if(left==true)
                {
                    count++;
                    continue;
                }

                left = true;
            }
            else if(te=='.'&&be=='*')
            {
                if(leftdiag==true)
                {
                    leftdiag = false;
                    continue;
                }
                if(rightdiag==true)
                {
                    count++;
                    continue;
                }
                rightdiag = true;
                if(left==true)
                {
                    count++;
                    continue;
                }

                left = true;
            }
            else if(te=='*'&&be=='*')
            {
                if(left==false)
                    left = true;
                else
                {
                    count++;
                    left = false;
                }
            }
            else
                continue;           
        }
        System.out.println(count);
    }
}

}

link

answered 02 Jun '17, 23:56

apoorv_saran's gravatar image

2★apoorv_saran
1
accept rate: 0%

plz edit ur code and format it nicely

(03 Jun '17, 16:34) jjtomar1★

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

link

answered 03 Jun '17, 00:26

devangm's gravatar image

4★devangm
1
accept rate: 0%

edited 03 Jun '17, 00:27

can any one help me in this. i am not getting what is wrong.. My_code

link

answered 03 Jun '17, 10:59

tocolor's gravatar image

3★tocolor
1
accept rate: 0%

This is absolute solution and it help me a lot thanks . programming assignment help

link

answered 03 Jun '17, 11:19

cubi's gravatar image

0★cubi
-5
accept rate: 0%

plz tell me test case for which my program produces wrong output thanks /\

link text

link

answered 03 Jun '17, 13:58

code_man's gravatar image

3★code_man
46
accept rate: 8%

(03 Jun '17, 16:25) vijju123 ♦♦5★

@code_man Ur code gives wrong output for following test cases:

4
7
*.....*
.*****.
7
.*****.
*.....*
11
...*...*...
....***....
11
....***....
...*...*...

The correct output is :

5
5
3
3

but your code gives output :

6
6
4
4
link

answered 03 Jun '17, 16:30

jjtomar's gravatar image

1★jjtomar
15910
accept rate: 4%

Could anyone help me in figuring out the test cases where my solution is failing? i tried hard but could get any.!! Link to solution is https://www.codechef.com/viewsolution/14017280 .

link

answered 03 Jun '17, 17:35

mohitgarg222's gravatar image

1★mohitgarg222
1
accept rate: 0%

can't find what's wrong in this code

include<iostream>

using namespace std;

int main(){ int t,n; cin>>t;

while(t--){
cin>>n;
char a[2][n];

for(int i=0;i<2;i++){
    for(int j=0;j<n;j++){
        cin>>a[i][j];
    }
}

int fences = 0;
char prev1='.', prev2='.', row1=false, row2=false;

for(int i=0;i<n;i++) {

    if(a[0][i]=='*'){
        row1=true;
    }
    if(a[1][i]=='*'){
        row2=true;
    }
    if((row2==row1)and(row1==true)){
        fences++;
        break;
    }
}

for(int i=0;i<n;i++){
        if(((a[0][i]=='*')and(a[1][i]=='*'))and((prev1=='*')or(prev2=='*'))) {
            fences++;
            if(prev1=='*')
                prev2='*';
            else if(prev2=='*')
                prev1='*';
            continue;
        }
        if((a[0][i]=='*') and (prev1!='*')){
            prev1='*';
        }
        else if((a[0][i]=='*') and (prev1=='*')) {
            fences++;
            prev2='.';
        }

        if((a[1][i]=='*') and (prev2!='*')){
            prev2='*';
        }
        else if((a[1][i]=='*') and (prev2=='*')){
                fences++;
                prev1='.';  
        }
    }

cout<<fences<<endl; }
}

link

answered 03 Jun '17, 19:31

shikhars387's gravatar image

2★shikhars387
11
accept rate: 0%

link

answered 03 Jun '17, 22:59

ashcode0605's gravatar image

5★ashcode0605
312
accept rate: 0%

@dpraveen, @kingofnumbers can we have the test cases now that test is over and we cannot even submit to check if our approach is correct.

link
This answer is marked "community wiki".

answered 20 Jun '17, 15:24

radee3's gravatar image

0★radee3
-1
accept rate: 0%

why my code is giving wrong answer .. plz help

include<iostream>

include<cstdlib>

using namespace std; int main() { int t,n,i,counta,countb,j,k,ans; cin>>t; while(t--) { cin>>n; char a=(char)malloc((n+1)sizeof(char)),b=(char)malloc(sizeof(char)(n+1)); cin>>a>>b; i=0;j=0;counta=0;countb=0;ans=0; for(k=0;k<n;k++) {="" if(a[k]="='*')" {="" counta++;="" i++;="" }="" if(b[k]="='*')" {="" countb++;="" j++;="" }="" if(i="">1&&j>1) { ans++; i=1;j=1; } else if(i>1 && j<2) { ans++; i=1; j=0; } else if(i<2 && j>1) { ans++; j=1;i=0; } } if(counta>0 && countb>0) ans++; cout<<ans<<endl; } return 0; }

link

answered 15 Jul '17, 10:04

be1048716's gravatar image

4★be1048716
1
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,852
×1,722
×1,024
×58
×11

question asked: 01 Jun '17, 18:15

question was seen: 3,873 times

last updated: 15 Jul '17, 10:04