iamSourav's blog

By iamSourav, history, 8 years ago, In English

I got wrong answer in this problem, but i don't understand where's the problem ?

problem link :(https://www.codechef.com/SNCKPB17/problems/SNELECT)

my code given below:

#include<bits/stdc++.h>
#define pi                  acos(-1)
#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)
#define INF                 1000000000000000000
#define dist(ax,ay,bx,by)   sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
#define M                   1000000
#define gcd(a,b)            __gcd(a,b)
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define m_p(a,b)            make_pair(a,b)
#define pb                  push_back
#define pf                  printf
#define sf                  scanf

using namespace std;
typedef unsigned long long llu;
typedef long long lli;
typedef long double ld;

using namespace std;
int main()
{


    string a;

    stack<char>s;
    stack<char>s1;

    lli p,i;
    cin>>p;
    bool mark=true;
    while(p--)
    {
cin>>a;
        mark=true;

        for(i=0; i<a.size(); i++)
        {

            if(a[i]=='m'&&a[i+1]=='s'&&mark)
            {
                mark=false;
                swap(a[i],a[i+1]);
            }

            if(a[i]=='s')
            {
           s.push('s');


            }
            else
            {
                mark=true;

                if(!s.empty()&&a[i-1]=='s') s.pop();
                s1.push('m');

            }



        }



        if(s.size()>s1.size()) cout<<"snakes";
        else  if(s.size()<s1.size()) cout<<"mongooses";
        else cout<<"tie";
        cout<<endl;
        while(!s.empty())
            s.pop();
        while(!s1.empty())
            s1.pop();

}

}

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I ain't understanding your algorithm. But, I have found a BUG in your code.

for(i=0; i<a.size(); i++)
        {
            if(a[i]=='m'&&a[i+1]=='s'&&mark)
            {
                mark=false;
                swap(a[i],a[i+1]);
            }
        }

Your loop is going till the end of the string. A string's last index is a.size() — 1 . But when i is equal to a.size() — 1 then you are checking both a[i] & a[i+1] which I think is causing the problem.

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Your algorithm seems unnecessarily complex.

Input:

1
ssmsm

Your output is "tie" (you kill only one snake), but the correct output is "mongooses" (kill two snakes).

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    thanks...u are brilliant yes i know it was a simple problem but i want to learn use of stack so i use this process