Page 14 of 17

Re: 195 - Anagram

Posted: Thu Jun 14, 2012 4:45 pm
by @ce
Now, getting the cases right but getting TLE :(

Code: Select all

Code removed after AC

Re: 195 - Anagram

Posted: Thu Jun 14, 2012 10:20 pm
by brianfry713
Doesn't match the sample I/O.

Re: 195 - Anagram

Posted: Fri Jun 15, 2012 2:02 pm
by @ce
I think it does..

Re: 195 - Anagram

Posted: Fri Jun 15, 2012 8:59 pm
by brianfry713
http://ideone.com/YIZBW

Your output has 36 lines, the sample output has 24 lines.

Re: 195 - Anagram

Posted: Fri Jun 15, 2012 9:43 pm
by @ce
I am sorry, I had made a stupid mistake.
Thanx brianfry...i got AC :)

Anagram

Posted: Sat Jul 14, 2012 11:31 am
by raji_27
I am getting wa in this problem. Plz help!!!
thnx

Re: Anagram

Posted: Sat Dec 29, 2012 4:03 pm
by @ce
post your code...how can someone help without knowing the problem

Re: 195 - Anagram

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

Re: 195 - Anagram

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

Re: 195 - Anagram

Posted: Wed Feb 13, 2013 12:06 am
by brianfry713
Doesn't match the sample I/O.

Re: 195 - Anagram

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

Re: 195 - Anagram

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

Re: 195 - Anagram

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

Re: 195 - Anagram

Posted: Wed Aug 14, 2013 9:53 pm
by brianfry713

195 - Anagram(WA)

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