454 - Anagrams

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Sun Apr 29, 2012 10:54 am

Don't convert copy to lowercase.
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 454 Anagrams WA

Post by mathgirl » Sun Apr 29, 2012 11:13 am

Damn ! I am really stupid. Thanks a ton Brian !

skyhigh_
New poster
Posts: 4
Joined: Fri May 25, 2012 7:43 am

454 Anagrams .... Why WA ??? please help me

Post by skyhigh_ » Fri May 25, 2012 7:54 am

:roll: :roll: :evil: :evil: :oops: :oops: :o :-? :-?

#include<algorithm>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<deque>
#define pi 2*acos(0.0)
using namespace std;

int main()
{

int t,i,j,k,n;
bool f;
scanf("%d%*c%*c",&t); // testcases

while( t-- )
{
string s[105],str[105];
string tem;
map<string,bool>m;
m.clear();

n=0;
// input

while( getline(cin,tem) )
{
if(!tem.empty())
{
if(m.find(tem)==m.end())
{
s[n++] = tem;
m[tem] =1;
}
}
else break;
}

sort(s,s+n);

// copying string without spaces

for(i=0; i<n; i++)
{
int len = s.length();

for(j=0; j<len; j++)
{
if(isalnum(s[j]))
str.push_back(s[j]);
}
}

for(i=0; i<n; i++) sort(str.begin(),str.end()); // sorting characters

// output

if(t) cout << endl;

for(i=0; i<n; i++)
for(j=i+1; j<n; j++)
{
if(str==str[j])
cout << s <<" = " << s[j] << endl;
}

}
return 0;
}


/*
input:
1

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

output :
carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut
*/

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams .... Why WA ??? please help me

Post by brianfry713 » Fri Jun 01, 2012 12:32 am

Two consecutive output for two consecutive input is separated by a single blank line.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 454 Anagrams WA

Post by Mukit Chowdhury » Fri Oct 12, 2012 6:55 am

I've found WA many times in this problem... but why ?? my code gives same output given above(except the last one,though I think my one is also right,as problem statement says , "Each anagram pair should be printed exactly once") ... please check this code someone... :(

Code: Select all

Accepted............. :)
Last edited by Mukit Chowdhury on Thu Nov 08, 2012 10:41 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Fri Oct 12, 2012 10:07 pm

I tested 4 versions of your code and none of them match the I/O I posted above from my AC code.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 454 Anagrams WA

Post by Mukit Chowdhury » Sat Oct 13, 2012 4:12 am

Code: Select all

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut


abc = cba
doesn't my code return this output ??? my compiler shows me this output... or is it wrong ??? :O

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Sat Oct 13, 2012 6:59 am

That is not the same output for the last case.
Check input and AC output for thousands of problems on uDebug!

Angry Bird
New poster
Posts: 21
Joined: Mon Apr 08, 2013 8:38 am

Re: 454 Anagrams WA

Post by Angry Bird » Sun Sep 15, 2013 7:47 am

What is the problem of my code?? Getting WA again and again...
Plzzz check it...

Code: Select all

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

int func(string a,string s)
{
    int l=a.size(),i;
    vector<char>c,c2;

    for(i=0; i<l; i++)
    {
        if(isalpha(a[i]))
        {
            c.push_back(a[i]);
        }
    }
    sort(c.begin(),c.end());

    int l2=s.size();

    for(i=0; i<l2; i++)
    {
        if(isalpha(s[i]))
        {
            c2.push_back(s[i]);
        }
    }
    sort(c2.begin(),c2.end());

    if(c==c2)
    {
        return 1;
    }

    else
    {
        return 0;
    }
}

int main()
{
    int t,i,j,k,g;
    string s;

    cin>>t;
    getchar();


    for(i=1; i<=t; i++)
    {
        vector<string>a,ko;
        string t1,t2,t3;

        while(getline(cin,s))
        {
            if(s=="")
            {
                break;
            }
            a.push_back(s);
        }

        for(j=0; j<a.size(); j++)
        {
            for(k=j+1; k<a.size(); k++)
            {
                g=func(a[j],a[k]);

                if(g==1)
                {
                    t1=a[j];
                    t2=a[k];

                    if(t1>t2)
                    {
                        t3=t1;
                        t1=t2;
                        t2=t3;
                    }
                    ko.push_back(t1 + " = "+t2);
                }
            }
        }

        sort(ko.begin(),ko.end());

        for(int b=0; b<ko.size(); b++)
        {
            cout<<ko[b]<<endl;
        }
        cout<<endl;
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Tue Sep 17, 2013 12:07 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

Angry Bird
New poster
Posts: 21
Joined: Mon Apr 08, 2013 8:38 am

Re: 454 Anagrams WA

Post by Angry Bird » Thu Sep 26, 2013 9:32 pm

Really i'm confused about your ans... Pls give me more I/O.

Code: Select all

    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <cstdio>
    #include <algorithm>

    using namespace std;

    int func(string a,string s)
    {
        int l=a.size(),i;
        vector<char>c,c2;

        for(i=0; i<l; i++)
        {
            if(isalpha(a[i]))
            {
                c.push_back(a[i]);
            }
        }
        sort(c.begin(),c.end());

        int l2=s.size();

        for(i=0; i<l2; i++)
        {
            if(isalpha(s[i]))
            {
                c2.push_back(s[i]);
            }
        }
        sort(c2.begin(),c2.end());

        if(c==c2)
        {
            return 1;
        }

        else
        {
            return 0;
        }
    }

    int main()
    {
        int t,i,j,k,g;
        string s;

        cin>>t;
        getchar();
        cout<<endl;

        for(i=1; i<=t; i++)
        {
            vector<string>a,ko;
            string t1,t2,t3;

            while(getline(cin,s))
            {
                if(s=="")
                {
                    break;
                }
                a.push_back(s);
            }

            for(j=0; j<a.size(); j++)
            {
                for(k=j+1; k<a.size(); k++)
                {
                    g=func(a[j],a[k]);

                    if(g==1)
                    {
                        t1=a[j];
                        t2=a[k];

                        if(t1>t2)
                        {
                            t3=t1;
                            t1=t2;
                            t2=t3;
                        }
                        ko.push_back(t1 + " = "+t2);
                    }
                }
            }

            sort(ko.begin(),ko.end());

            for(int b=0; b<ko.size(); b++)
            {
                cout<<ko[b]<<endl;
            }
            cout<<endl;
        }
        return 0;
    }



brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Fri Sep 27, 2013 11:16 pm

When I run your code on the sample input it's not printing anything.
http://ideone.com/ux3owo
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 454 Anagrams WA

Post by uDebug » Tue Mar 25, 2014 1:20 pm

In addition to the excellent test case shared by brianfry713, I'd like to add one that helped me catch my bug.

If this isn't already clear to you, please understand that the output has to be lexicographic not only between pairs of words but also in the order of phrases printed. So, in the output, starting from the top, observe that each pair of phrases is lexicographically ordered - and that the entire list of phrases is lexicographically ordered as well.

Input:

Code: Select all

2

carthorse
horse
horse cart
orchestra
orchestra
orchestra
i do not know u
ok i now donut

zaaaahari is here
si hari ere h aaaaz
i like tunes
tunes i like
AC Output:

Code: Select all

carthorse = horse cart
carthorse = orchestra
carthorse = orchestra
carthorse = orchestra
horse cart = orchestra
horse cart = orchestra
horse cart = orchestra
i do not know u = ok i now donut
orchestra = orchestra
orchestra = orchestra
orchestra = orchestra

i like tunes = tunes i like
si hari ere h aaaaz = zaaaahari is here
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 454 - Anagrams

Post by uDebug » Tue Mar 25, 2014 1:21 pm

If you're stuck on this problem, please be sure to check out this thread as well.

http://acm.uva.es/board/viewtopic.php?f ... 0c6721aefc
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 454 Anagrams WA

Post by uDebug » Tue Mar 25, 2014 1:35 pm

Angry Bird wrote:Really i'm confused about your ans... Pls give me more I/O.
I think you might be nearly there.

Couple points:

Point #1
In the future do not do this

Code: Select all

cin>>t; getchar();
and count on the "getchar()" to catch the newline. Chances are it won't.

Point #2
The problem states
Two consecutive output for two consecutive input is separated by a single blank line.
But you're printing a newline after each case - including the last one.

For Point #1, I did the following

Code: Select all

/* Read in the number of test cases */
scanf("%d\n",&t);
and for Point #2 I added this in the main for loop

Code: Select all

if(i != 1) {
    cout<<endl;
}
and your code passed all the test cases on this thread. So, it appears to be AC code.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 4 (400-499)”