195 - Anagram

[lighted]

Every time wrong answer because of bugs in our codes and we don't want to believe in it.

Code: Select all

M['m']=25;
M['m']=26;

Please remove your codes after getting accepted. (If you have some respect to uva board where you receive help when have problems)

[masterzemo]

I'm getting output limit, what is wrong with my code?

Code: Select all

Removed after AC

[Lim.YuDe]

Not sure what is wrong with my code. (Please see below for the code)
I keep getting Wrong Answer even though it seems to work fine even on long strings with duplicate characters.
Also, I have tested my output with the given sample input:

3
aAb
abc
acba

and achieved the sample output:

Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

Code: Select all

Removed after AC

[lighted]

Try to check input in this thread before posting.

Input:

Code: Select all

1
AaBb

AC output:

Code: Select all

AaBb
AabB
ABab
ABba
AbaB
AbBa
aABb
aAbB
aBAb
aBbA
abAB
abBA
BAab
BAba
BaAb
BabA
BbAa
BbaA
bAaB
bABa
baAB
baBA
bBAa
bBaA

[Lim.YuDe]

lighted, thank you.

I did go through the first 2 pages but it seemed like most people were having a problem different from mine, but sorry for making the newbie move of posting too quickly! I will be careful to check the input in the thread more thoroughly in the future!

[gautamzero]

why WA??
i have not found any problem....

Code: Select all

AC

[brianfry713]

Input:

Code: Select all

1
aAbBcC

AC output:

Code: Select all

AaBbCc
AaBbcC
AaBCbc
AaBCcb
AaBcbC
AaBcCb
AabBCc
AabBcC
AabCBc
AabCcB
AabcBC
AabcCB
AaCBbc
AaCBcb
AaCbBc
AaCbcB
AaCcBb
AaCcbB
AacBbC
AacBCb
AacbBC
AacbCB
AacCBb
AacCbB
ABabCc
ABabcC
ABaCbc
ABaCcb
ABacbC
ABacCb
ABbaCc
ABbacC
ABbCac
ABbCca
ABbcaC
ABbcCa
ABCabc
ABCacb
ABCbac
ABCbca
ABCcab
ABCcba
ABcabC
ABcaCb
ABcbaC
ABcbCa
ABcCab
ABcCba
AbaBCc
AbaBcC
AbaCBc
AbaCcB
AbacBC
AbacCB
AbBaCc
AbBacC
AbBCac
AbBCca
AbBcaC
AbBcCa
AbCaBc
AbCacB
AbCBac
AbCBca
AbCcaB
AbCcBa
AbcaBC
AbcaCB
AbcBaC
AbcBCa
AbcCaB
AbcCBa
ACaBbc
ACaBcb
ACabBc
ACabcB
ACacBb
ACacbB
ACBabc
ACBacb
ACBbac
ACBbca
ACBcab
ACBcba
ACbaBc
ACbacB
ACbBac
ACbBca
ACbcaB
ACbcBa
ACcaBb
ACcabB
ACcBab
ACcBba
ACcbaB
ACcbBa
AcaBbC
AcaBCb
AcabBC
AcabCB
AcaCBb
AcaCbB
AcBabC
AcBaCb
AcBbaC
AcBbCa
AcBCab
AcBCba
AcbaBC
AcbaCB
AcbBaC
AcbBCa
AcbCaB
AcbCBa
AcCaBb
AcCabB
AcCBab
AcCBba
AcCbaB
AcCbBa
aABbCc
aABbcC
aABCbc
aABCcb
aABcbC
aABcCb
aAbBCc
aAbBcC
aAbCBc
aAbCcB
aAbcBC
aAbcCB
aACBbc
aACBcb
aACbBc
aACbcB
aACcBb
aACcbB
aAcBbC
aAcBCb
aAcbBC
aAcbCB
aAcCBb
aAcCbB
aBAbCc
aBAbcC
aBACbc
aBACcb
aBAcbC
aBAcCb
aBbACc
aBbAcC
aBbCAc
aBbCcA
aBbcAC
aBbcCA
aBCAbc
aBCAcb
aBCbAc
aBCbcA
aBCcAb
aBCcbA
aBcAbC
aBcACb
aBcbAC
aBcbCA
aBcCAb
aBcCbA
abABCc
abABcC
abACBc
abACcB
abAcBC
abAcCB
abBACc
abBAcC
abBCAc
abBCcA
abBcAC
abBcCA
abCABc
abCAcB
abCBAc
abCBcA
abCcAB
abCcBA
abcABC
abcACB
abcBAC
abcBCA
abcCAB
abcCBA
aCABbc
aCABcb
aCAbBc
aCAbcB
aCAcBb
aCAcbB
aCBAbc
aCBAcb
aCBbAc
aCBbcA
aCBcAb
aCBcbA
aCbABc
aCbAcB
aCbBAc
aCbBcA
aCbcAB
aCbcBA
aCcABb
aCcAbB
aCcBAb
aCcBbA
aCcbAB
aCcbBA
acABbC
acABCb
acAbBC
acAbCB
acACBb
acACbB
acBAbC
acBACb
acBbAC
acBbCA
acBCAb
acBCbA
acbABC
acbACB
acbBAC
acbBCA
acbCAB
acbCBA
acCABb
acCAbB
acCBAb
acCBbA
acCbAB
acCbBA
BAabCc
BAabcC
BAaCbc
BAaCcb
BAacbC
BAacCb
BAbaCc
BAbacC
BAbCac
BAbCca
BAbcaC
BAbcCa
BACabc
BACacb
BACbac
BACbca
BACcab
BACcba
BAcabC
BAcaCb
BAcbaC
BAcbCa
BAcCab
BAcCba
BaAbCc
BaAbcC
BaACbc
BaACcb
BaAcbC
BaAcCb
BabACc
BabAcC
BabCAc
BabCcA
BabcAC
BabcCA
BaCAbc
BaCAcb
BaCbAc
BaCbcA
BaCcAb
BaCcbA
BacAbC
BacACb
BacbAC
BacbCA
BacCAb
BacCbA
BbAaCc
BbAacC
BbACac
BbACca
BbAcaC
BbAcCa
BbaACc
BbaAcC
BbaCAc
BbaCcA
BbacAC
BbacCA
BbCAac
BbCAca
BbCaAc
BbCacA
BbCcAa
BbCcaA
BbcAaC
BbcACa
BbcaAC
BbcaCA
BbcCAa
BbcCaA
BCAabc
BCAacb
BCAbac
BCAbca
BCAcab
BCAcba
BCaAbc
BCaAcb
BCabAc
BCabcA
BCacAb
BCacbA
BCbAac
BCbAca
BCbaAc
BCbacA
BCbcAa
BCbcaA
BCcAab
BCcAba
BCcaAb
BCcabA
BCcbAa
BCcbaA
BcAabC
BcAaCb
BcAbaC
BcAbCa
BcACab
BcACba
BcaAbC
BcaACb
BcabAC
BcabCA
BcaCAb
BcaCbA
BcbAaC
BcbACa
BcbaAC
BcbaCA
BcbCAa
BcbCaA
BcCAab
BcCAba
BcCaAb
BcCabA
BcCbAa
BcCbaA
bAaBCc
bAaBcC
bAaCBc
bAaCcB
bAacBC
bAacCB
bABaCc
bABacC
bABCac
bABCca
bABcaC
bABcCa
bACaBc
bACacB
bACBac
bACBca
bACcaB
bACcBa
bAcaBC
bAcaCB
bAcBaC
bAcBCa
bAcCaB
bAcCBa
baABCc
baABcC
baACBc
baACcB
baAcBC
baAcCB
baBACc
baBAcC
baBCAc
baBCcA
baBcAC
baBcCA
baCABc
baCAcB
baCBAc
baCBcA
baCcAB
baCcBA
bacABC
bacACB
bacBAC
bacBCA
bacCAB
bacCBA
bBAaCc
bBAacC
bBACac
bBACca
bBAcaC
bBAcCa
bBaACc
bBaAcC
bBaCAc
bBaCcA
bBacAC
bBacCA
bBCAac
bBCAca
bBCaAc
bBCacA
bBCcAa
bBCcaA
bBcAaC
bBcACa
bBcaAC
bBcaCA
bBcCAa
bBcCaA
bCAaBc
bCAacB
bCABac
bCABca
bCAcaB
bCAcBa
bCaABc
bCaAcB
bCaBAc
bCaBcA
bCacAB
bCacBA
bCBAac
bCBAca
bCBaAc
bCBacA
bCBcAa
bCBcaA
bCcAaB
bCcABa
bCcaAB
bCcaBA
bCcBAa
bCcBaA
bcAaBC
bcAaCB
bcABaC
bcABCa
bcACaB
bcACBa
bcaABC
bcaACB
bcaBAC
bcaBCA
bcaCAB
bcaCBA
bcBAaC
bcBACa
bcBaAC
bcBaCA
bcBCAa
bcBCaA
bcCAaB
bcCABa
bcCaAB
bcCaBA
bcCBAa
bcCBaA
CAaBbc
CAaBcb
CAabBc
CAabcB
CAacBb
CAacbB
CABabc
CABacb
CABbac
CABbca
CABcab
CABcba
CAbaBc
CAbacB
CAbBac
CAbBca
CAbcaB
CAbcBa
CAcaBb
CAcabB
CAcBab
CAcBba
CAcbaB
CAcbBa
CaABbc
CaABcb
CaAbBc
CaAbcB
CaAcBb
CaAcbB
CaBAbc
CaBAcb
CaBbAc
CaBbcA
CaBcAb
CaBcbA
CabABc
CabAcB
CabBAc
CabBcA
CabcAB
CabcBA
CacABb
CacAbB
CacBAb
CacBbA
CacbAB
CacbBA
CBAabc
CBAacb
CBAbac
CBAbca
CBAcab
CBAcba
CBaAbc
CBaAcb
CBabAc
CBabcA
CBacAb
CBacbA
CBbAac
CBbAca
CBbaAc
CBbacA
CBbcAa
CBbcaA
CBcAab
CBcAba
CBcaAb
CBcabA
CBcbAa
CBcbaA
CbAaBc
CbAacB
CbABac
CbABca
CbAcaB
CbAcBa
CbaABc
CbaAcB
CbaBAc
CbaBcA
CbacAB
CbacBA
CbBAac
CbBAca
CbBaAc
CbBacA
CbBcAa
CbBcaA
CbcAaB
CbcABa
CbcaAB
CbcaBA
CbcBAa
CbcBaA
CcAaBb
CcAabB
CcABab
CcABba
CcAbaB
CcAbBa
CcaABb
CcaAbB
CcaBAb
CcaBbA
CcabAB
CcabBA
CcBAab
CcBAba
CcBaAb
CcBabA
CcBbAa
CcBbaA
CcbAaB
CcbABa
CcbaAB
CcbaBA
CcbBAa
CcbBaA
cAaBbC
cAaBCb
cAabBC
cAabCB
cAaCBb
cAaCbB
cABabC
cABaCb
cABbaC
cABbCa
cABCab
cABCba
cAbaBC
cAbaCB
cAbBaC
cAbBCa
cAbCaB
cAbCBa
cACaBb
cACabB
cACBab
cACBba
cACbaB
cACbBa
caABbC
caABCb
caAbBC
caAbCB
caACBb
caACbB
caBAbC
caBACb
caBbAC
caBbCA
caBCAb
caBCbA
cabABC
cabACB
cabBAC
cabBCA
cabCAB
cabCBA
caCABb
caCAbB
caCBAb
caCBbA
caCbAB
caCbBA
cBAabC
cBAaCb
cBAbaC
cBAbCa
cBACab
cBACba
cBaAbC
cBaACb
cBabAC
cBabCA
cBaCAb
cBaCbA
cBbAaC
cBbACa
cBbaAC
cBbaCA
cBbCAa
cBbCaA
cBCAab
cBCAba
cBCaAb
cBCabA
cBCbAa
cBCbaA
cbAaBC
cbAaCB
cbABaC
cbABCa
cbACaB
cbACBa
cbaABC
cbaACB
cbaBAC
cbaBCA
cbaCAB
cbaCBA
cbBAaC
cbBACa
cbBaAC
cbBaCA
cbBCAa
cbBCaA
cbCAaB
cbCABa
cbCaAB
cbCaBA
cbCBAa
cbCBaA
cCAaBb
cCAabB
cCABab
cCABba
cCAbaB
cCAbBa
cCaABb
cCaAbB
cCaBAb
cCaBbA
cCabAB
cCabBA
cCBAab
cCBAba
cCBaAb
cCBabA
cCBbAa
cCBbaA
cCbAaB
cCbABa
cCbaAB
cCbaBA
cCbBAa
cCbBaA

[gautamzero]

silly mistake
thnx....
it should be 2n and 2n+1;

[garbage]

Code: Select all

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;

map<string, int>myMap;

int permutation(string prefix, string ch)
{
    int n = ch.length();
    for(int i=0;i<n;i++)
    {
        char tmp = ch[0];
        ch[0] = ch[i];
        ch[i] = tmp;
        
        if(n==1)
        {
            if(myMap[prefix+ch]==0)
            {
                cout<<prefix+ch<<endl;
                myMap[prefix+ch]=1;
            }
            return 0;
        }
        
        permutation(prefix+ch.substr(0, 1), ch.substr(1, n-1));
    }
}

int main()
{
    long T;
    string ch, str;
    map<int, int>charMap;

    scanf("%ld", &T);
    
    for(int i=1;i<=T;i++)
    {
        cin>>ch;
        
        for(int j='A', k='a'; j<='Z';j++, k++)
            charMap[j] = charMap[k] = 0;
        
        int len = ch.length();
        for(int j=0;j<len;j++)
            charMap[ch[j]]++;
        
        str = "";
        for(int j=0;j<26;j++)
        {
            for(int k=1;k<=charMap['A'+j];k++)
                str.push_back('A'+j);
                
            for(int k=1;k<=charMap['a'+j];k++)
                str.push_back('a'+j);
        }
        
        permutation("", str);
        myMap.clear();
    }
    
    return 0;
}

[brianfry713]

First I mapped A to 0, a to 1, B to 2, etc.
Then sort.
Finally I solved it using next_permutation from the STL.

[garbage]

thnx brianfry713
finally got AC...

[uvagambler]

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100

int compare(const void *a, const void *b)
{
  char x = *(char *)a,
       y = *(char *)b;

  if(tolower(x) == tolower(y))
    return x > y;

  return tolower(x) > tolower(y);
}

int strremove(char *string, int length_of_string, int index, char *new_string)
{
  int length = 0;
  int i;

  for(i = 0; i < length_of_string; i++){
    if(i == index)
      continue;

    new_string[length++] = string[i];
  }
  new_string[length] = '\0';

  return length;
}

void dfs(char *selected, int length_of_selected, char *remaining, int length_of_remaining)
{
  if(length_of_remaining == 0){
    printf("%s\n", selected);
    return;
  }

  char *new_remaining = malloc(sizeof(char) * (length_of_remaining+100));
  int i, j;

  for(i = 0; i < length_of_remaining; i++){
    if(remaining[i] == selected[length_of_selected])
      continue;

    selected[length_of_selected] = remaining[i];
    selected[length_of_selected+1] = '\0';
    strremove(remaining, length_of_remaining, i, new_remaining);

    dfs(selected, length_of_selected+1, new_remaining, length_of_remaining-1);
  }

  free(new_remaining);
}

int main(void)
{
  int num;
  char word[MAX], temp[MAX];

  scanf("%d", &num);
  while(num--){
    scanf("%s", word);
    qsort(word, strlen(word), sizeof(char), compare);
    dfs(temp, 0, word, strlen(word));
  }

  return 0;
}

Plz, I have been stuck in this problem for a long time.
However, I still can't figure out the mistakes.
I checked the words in ascending order and A < a < B < b < ...
Everything seems good, but the online judge always gives me WA.

[brianfry713]

First I mapped A to 0, a to 1, B to 2, etc.
Then sort.
Finally I solved it using next_permutation from the STL.

[uvagambler]

Hmm....

Actually, I have passed the online judge.
However, I didn't modify the above code to pass.
I used another method and rewrote entire code.

The problem is that I can't figure out where the mistakes are.
I hope some one can help me and point it out.

[98989898]

Hi, got a TLE, any suggestions on how to get AC on java, my code is here:

Code: Select all

import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;

class Main {
	static ArrayList<String> permutations;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		String line = br.readLine();
		int testcases = Integer.parseInt(line);
		for (int kz = 0 ; kz < testcases ; kz++) {
			line = br.readLine();
			permutations = new ArrayList<String>();
			ArrayList<Character> left = new ArrayList<Character>();
			for (int i = 0 ; i < line.length() ; i++) {
				left.add(new Character(line.charAt(i)));
			}
			Collections.sort(left);
			permutate(left,"");
			Collections.sort(permutations,new MyComparator());
			String last = "";
			if (permutations.size()>0) {
				last = permutations.get(0);
				pr.println(last);
			}
			for (int k = 1 ; k < permutations.size(); k++) {
				String curr = permutations.get(k);
				if (!last.equals(curr)) {
					last = curr;
					pr.println(curr);
				}
			}
		}
		
		pr.close();
	}
	public static void permutate(ArrayList<Character> line, String curr){
		if (line.size()==0) {
			permutations.add(curr);
		}
		for (int i = 0 ; i < line.size() ; i++) {
			ArrayList<Character> clone = (ArrayList<Character>)line.clone();
			clone.remove(i);
			permutate(clone, curr+line.get(i));
			
		}
	}
}
class MyComparator implements Comparator<String>{
	char[] index = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
	public int compare(String a, String b){
		for (int j = 0 ; j < a.length() ; j++) {
			char aa = a.charAt(j);
			char bb = b.charAt(j);
			int aaa = 0;
			int bbb = 0;
			for (int i = 0 ; i<52; i++) {
				if (index[i]==aa) {
					aaa = i ;
					break;
				}
			}
			for (int i = 0 ; i<52; i++) {
				if (index[i]==bb) {
					bbb = i;
					break;
				}
			}
			if (aaa>bbb) {
				return 1;
			}
			if (bbb>aaa) {
				return -1;
			}
		}
		return 0;
	}
}