195 - Anagram

[@ce]

Now, getting the cases right but getting TLE

Code: Select all

Code removed after AC

[brianfry713]

Doesn't match the sample I/O.

[@ce]

I think it does..

[brianfry713]

http://ideone.com/YIZBW

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

[@ce]

I am sorry, I had made a stupid mistake.
Thanx brianfry...i got AC

[raji_27]

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

[@ce]

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

[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;
}

[lbv]

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]

Doesn't match the sample I/O.

[mgavin2]

• 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 :\

[lbv]

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.

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]

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]

cosmin79, see http://uva.onlinejudge.org/index.php?op ... 1&Itemid=1

[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;
}