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

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

Re: 195 - Anagram

Post by @ce » Thu Jun 14, 2012 4:45 pm

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 » Thu Jun 14, 2012 10:20 pm

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

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

Re: 195 - Anagram

Post by @ce » Fri Jun 15, 2012 2:02 pm

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 » Fri Jun 15, 2012 8:59 pm

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!

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

Re: 195 - Anagram

Post by @ce » Fri Jun 15, 2012 9:43 pm

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 » Sat Jul 14, 2012 11:31 am

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

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

Re: Anagram

Post by @ce » Sat Dec 29, 2012 4:03 pm

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 » Tue Feb 12, 2013 9:55 pm

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 » Tue Feb 12, 2013 11:13 pm

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 » Wed Feb 13, 2013 12:06 am

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 » Thu Feb 14, 2013 10:52 pm

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 » Fri Feb 15, 2013 12:46 am

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 » Mon Aug 12, 2013 3:05 am

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 » Wed Aug 14, 2013 9:53 pm

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 » Fri Aug 30, 2013 7:03 pm

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)”