195 - Anagram

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

Moderator: Board moderators

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 195 - Anagram

Post by @ce »

Now, getting the cases right but getting TLE :(

Code: Select all

Code removed after AC
Last edited by @ce on Mon Jun 25, 2012 10:01 am, edited 1 time in total.
-@ce

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

Re: 195 - Anagram

Post by brianfry713 »

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

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 195 - Anagram

Post by @ce »

I think it does..
-@ce

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

Re: 195 - Anagram

Post by brianfry713 »

http://ideone.com/YIZBW

Your output has 36 lines, the sample output has 24 lines.
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 195 - Anagram

Post by @ce »

I am sorry, I had made a stupid mistake.
Thanx brianfry...i got AC :)
-@ce

raji_27
New poster
Posts: 1
Joined: Sat Jul 14, 2012 11:26 am

Anagram

Post by raji_27 »

I am getting wa in this problem. Plz help!!!
thnx

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: Anagram

Post by @ce »

post your code...how can someone help without knowing the problem
-@ce

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 195 - Anagram

Post by mgavin2 »

WA ... I'm not sure anymore with the hacks I've tried to work around :\

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cctype>
#include <set>

using namespace std;

//#define DEBUG
//#undef DEBUG //uncomment this line to pull out print statements
#ifdef DEBUG
#define TAB '\t'
#define debug(a, end) cout << #a << ": " << a << end
#else
#define debug(a, end)
#endif

typedef pair<int, int> point;
typedef long long int64; //for clarity
typedef vector<int> vi; //?
typedef vector<point> vp; //?
template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //change min
template<class T> void chmax(T &t, T f) { if (t < f) t = f; } //change max

#define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())   
#define SORT(c) sort((c).begin(),(c).end())   
#define FOR(i,a,b) for (int  i=(a); i < (b); i++)    
#define REP(i,n) FOR(i,0,n)    
#define CL(a,b) memset(a,b,sizeof(a))
#define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)

/*global variables*/
struct compare
{
    bool operator() (const string& a, const string& b)
    {
        bool t = false;
        for (size_t i = 0; i < a.length() && i < b.length(); ++i)
            if (toupper(a[i]) < toupper(b[i]))
                return true;
            else if (toupper(a[i]) > toupper(b[i]))
                return false;
            else if (toupper(a[i]) == toupper(b[i]))
                if ( a[i] < b[i] )
                    return true;
        /*t = a[i] < b[i] ? true : false;

          return t;*/

    }
};

struct comp
{
    bool operator() (const char& a, const char& b)
    {
        debug(a, TAB); debug(b, TAB); debug((isupper(a) ? a < b : b > a), endl);
        return (isupper(a) ? a < b : b > a);
    }
};
string word;
/*global variables*/

void dump()
{
    //dump data
}

bool getInput()
{
    //get input
    cin >> word;
    
    return true;
}

void process()
{
    //process input
    set<string, compare> words;
    //SORT(word);
    do
    {
        words.insert(word);
        debug(word, endl);
    }
    while (next_permutation(word.begin(), word.end(), comp()));

    //quick hack.
    do
    {
        words.insert(word);
        debug(word, endl);
    }
    while (next_permutation(word.begin(), word.end()));
    

    //sort(words.begin(), words.end(), compare());
    //SORT(words);
    for (set<string>::iterator it = words.begin(); it != words.end(); ++it)
        printf("%s\n", it->c_str());

    debug(words.size(), endl);
}

int main()
{
    int nc;
    scanf("%d", &nc);
    while (nc-- > 0)
    {
        getInput();
        process();

        /*CLEAR GLOBAL VARIABLES!*/
        /*CLEAR GLOBAL VARIABLES!*/
    }

    return 0;
}
all that matters is AC

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 195 - Anagram

Post by lbv »

mgavin2 wrote:WA ... I'm not sure anymore with the hacks I've tried to work around :\
  • Did you check your program against the sample cases given in the problem statement?
  • Using a custom comparison method in next_permutation seems unnecessary. The order in which you generate the permutations don't have much importance if you end up placing the words in a set, which imposes its own order.
  • The functor in compare seems incomplete. You don't have a return statement at the end of that function, which means that the compiler is free to return anything if it reaches that point. Try configuring your compiler so that it shows you all warnings, which can help you catch this type of bug.
  • As you recognise, your code seems to have picked up a number of hacks along the way. That's never a good sign. I suggest you start from scratch, and try working out the problem in your head first until you're confident that you understand what the problem is asking for, and how to compute it. You'll notice that the solution doesn't require so much work and can be implemented succintly.

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

Re: 195 - Anagram

Post by brianfry713 »

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

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 195 - Anagram

Post by mgavin2 »

lbv wrote:
  • Did you check your program against the sample cases given in the problem statement?
  • Using a custom comparison method in next_permutation seems unnecessary. The order in which you generate the permutations don't have much importance if you end up placing the words in a set, which imposes its own order.
  • The functor in compare seems incomplete. You don't have a return statement at the end of that function, which means that the compiler is free to return anything if it reaches that point. Try configuring your compiler so that it shows you all warnings, which can help you catch this type of bug.
  • As you recognise, your code seems to have picked up a number of hacks along the way. That's never a good sign. I suggest you start from scratch, and try working out the problem in your head first until you're confident that you understand what the problem is asking for, and how to compute it. You'll notice that the solution doesn't require so much work and can be implemented succintly.
Yeah, I'm going to start over... thanks for the suggestions thus far..

What annoys me is if there are similar characters in next_permutation, it seems to skip them

Code: Select all

    cin >> word;
    set<string> words;
    //SORT(word);
    do
    {
        words.insert(word);
        debug(word, endl);
    }
    while (next_permutation(word.begin(), word.end()));
with

Code: Select all

1
aAb
gives me

Code: Select all

aAb
abA
bAa
baA
Maybe I should just skip next_permutation and recursively generate them by hand :\
all that matters is AC

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 195 - Anagram

Post by lbv »

mgavin2 wrote: What annoys me is if there are similar characters in next_permutation, it seems to skip them
It doesn't skip them. It's just that next_permutation works by calculating the next permutation in lexicographical order. If you initially feed it a string that is not the lexicographically lowest permutation, it will not produce all permutations; no surprises there. For more details, read its documentation.
mgavin2 wrote:Maybe I should just skip next_permutation and recursively generate them by hand :\
If you decide to do it, go ahead, it shouldn't be much harder. However, I can tell you that I solved it using only next_permutation with a custom comparator, and a simple mechanism to avoid duplicates (no set).

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

Re: 195 - Anagram

Post by cosmin79 »

Code: Select all

#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int t, n;
string A;

bool cmp(char x, char y)
{
    if (tolower(x) == tolower(y))
        return isupper(x);
        
    return tolower(x) < tolower(y);
}

int main()
{
    //freopen("input", "r", stdin);
    cin >> t;
    while (t--)
    {
        cin >> A;
        sort(A.begin(), A.end(), cmp);
        
        do 
        {
            cout << A << "\n";
        }
        while (next_permutation(A.begin(), A.end(), cmp));
    }
    return 0;
}
Could anyone help me realize what's wrong with the code above? For some reason, it keeps receiving a SubmissionErr verdict.
Thank you in advance!

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

Re: 195 - Anagram

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

195 - Anagram(WA)

Post by shikhorroy »

What's wrong with my code ? Where is the problem?

Code: Select all

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        char str[10000];
        scanf("%s",str);
        int l = strlen(str);
        sort(str,str+l);
        do
        {
            cout<<str<<endl;
        }
        while( next_permutation(str,str+l));
    }
    return 0;
}

Post Reply

Return to “Volume 1 (100-199)”