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

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 195 - Anagram

Post by lighted » Mon Nov 10, 2014 4:35 pm

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)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

masterzemo
New poster
Posts: 2
Joined: Sat Nov 29, 2014 5:57 am

Re: 195 - Anagram

Post by masterzemo » Sat Nov 29, 2014 6:21 am

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

Code: Select all

Removed after AC

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 195 - Anagram

Post by Lim.YuDe » Sat Dec 13, 2014 1:43 pm

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
Last edited by Lim.YuDe on Sat Dec 13, 2014 6:35 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 195 - Anagram

Post by lighted » Sat Dec 13, 2014 4:13 pm

Try to check input in this thread before posting.
brianfry713 wrote: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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 195 - Anagram

Post by Lim.YuDe » Sat Dec 13, 2014 6:35 pm

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
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

Re: 195 - Anagram

Post by gautamzero » Thu Dec 18, 2014 5:51 pm

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

Code: Select all

AC
Last edited by gautamzero on Fri Dec 19, 2014 5:45 pm, edited 1 time in total.
None but a fool is always right..
so don't be upset when u r wrong..

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

Re: 195 - Anagram

Post by brianfry713 » Fri Dec 19, 2014 3:47 am

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
Check input and AC output for thousands of problems on uDebug!

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

Re: 195 - Anagram

Post by gautamzero » Fri Dec 19, 2014 5:44 pm

:oops:
silly mistake :D
thnx....
it should be 2n and 2n+1; :)
None but a fool is always right..
so don't be upset when u r wrong..

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 195 - Anagram, Getting TLE, help please :(

Post by garbage » Fri Jan 23, 2015 8:03 pm

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;
}
Last edited by brianfry713 on Fri Jan 23, 2015 9:35 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: 195 - Anagram

Post by brianfry713 » Sat Jan 24, 2015 7:27 am

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.
Check input and AC output for thousands of problems on uDebug!

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 195 - Anagram

Post by garbage » Sat Jan 24, 2015 7:52 pm

thnx brianfry713
finally got AC... :)

uvagambler
New poster
Posts: 2
Joined: Wed Feb 11, 2015 4:17 pm

Re: 195 - Anagram

Post by uvagambler » Wed Feb 11, 2015 4:23 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 195 - Anagram

Post by brianfry713 » Wed Feb 11, 2015 9:53 pm

brianfry713 wrote: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.
Check input and AC output for thousands of problems on uDebug!

uvagambler
New poster
Posts: 2
Joined: Wed Feb 11, 2015 4:17 pm

Re: 195 - Anagram

Post by uvagambler » Thu Feb 12, 2015 10:01 am

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
New poster
Posts: 1
Joined: Fri Dec 11, 2015 4:01 am

Re: 195 - Anagram

Post by 98989898 » Fri Dec 11, 2015 4:09 am

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

Post Reply

Return to “Volume 1 (100-199)”