454 - Anagrams

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 454 Anagrams WA

Post by vsha041 » Wed Apr 09, 2014 10:47 pm

But you're printing a newline after each case - including the last one.
True. But sometimes we get away with it and get AC and at other times it gives WA instead of PE which can be frustating. I realized there are two ways this is mentioned in the problems.

1. Print a new line between every testcase or two consecutive test cases. This is the one mentioned by you.
2. Print a new line after every test case. For these ones we need a blank line after last test case as well.

Need to very careful as these don't give presentation errors.

MEGADEEN
New poster
Posts: 5
Joined: Sun Jun 15, 2014 9:26 am

Re: 454 Anagrams WA

Post by MEGADEEN » Thu Jun 26, 2014 11:14 am

After 3 attempts and 1 rewrite, my program still get WA. Help me please.

Code: Select all

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;

struct word{
    string wrd;
    string stripped;
    void strip() {
        stripped = "";
        for (int i = 0; i < wrd.length(); ++i) {
            if (isspace((int)wrd[i])) continue;
            stripped += wrd[i];
        }
        sort(stripped.begin(), stripped.end());
    }
};

int n;
word words[101];

bool cmp (word a, word b) {
    if (a.stripped.compare(b.stripped) < 0) return true;
    if (a.stripped.compare(b.stripped) == 0) {
        if (a.wrd.compare(b.wrd) <= 0) return true;
    }
    return false;
}

int main() {
    cin >> n;
    cin.ignore(256,'\n');
    cin.ignore(256,'\n');

    while (n--) {
        int i = 0;
        while (getline(cin, words[i].wrd) && words[i].wrd[0] != '\n' && words[i].wrd[0] != NULL) {
            words[i++].strip();
            //cout << words[i - 1].wrd << endl;
        }
        sort(words, words + i, cmp);
        for (int j = 0; j < i; ++j) {
            for (int k = j + 1; k < i; ++k) {
                if (words[j].stripped.compare(words[k].stripped) == 0) {
                    cout << words[j].wrd << " = " << words[k].wrd << endl;
                } else break;
            }
        }
        if (n) cout << endl;

    }

    return 0;
}


User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 454 Anagrams WA

Post by uDebug » Thu Jun 26, 2014 1:07 pm

MEGADEEN wrote:After 3 attempts and 1 rewrite, my program still get WA. Help me please.
This thread has some excellent test cases. Have you tried running your program on those to see if it produces the right output? That might be a good place to start.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

MEGADEEN
New poster
Posts: 5
Joined: Sun Jun 15, 2014 9:26 am

Re: 454 Anagrams WA

Post by MEGADEEN » Fri Jun 27, 2014 5:03 pm

I spotted my mistake after analyzing several test cases. The reason is that I was grouping together anagrams which is not correct.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 454 Anagrams WA

Post by uDebug » Sat Jun 28, 2014 6:42 am

MEGADEEN wrote:I spotted my mistake after analyzing several test cases.
Congratulations! Well done!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

lichtgestalt01
New poster
Posts: 4
Joined: Sun Jun 22, 2014 6:00 am

454-Anagrams WA :(

Post by lichtgestalt01 » Wed Jul 30, 2014 2:03 am

i tried a lot of cases
and still give me wa
please help !!

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.ArrayList;


class Cad implements Comparable<Cad>
{
	private String w;//the original string 
	private String order;//the sorted string
	private HashSet<String> past;//a hashset containing all the pairs of one Cad 
	String number;//the number of the Cad ,0,1,2,3.... 
	public Cad(String a,String b,String i)
	{
		w=a;
		order=b;
		past=new HashSet<String>();
		past.add(i);
		number=i;
	}
	public String getW() {
		return w;
	}
	public String getOrder() {
		return order;
	}
	public void add(String a)
	{
		past.add(a);
	}
	public boolean contains(String a)
	{
		return past.contains(a);
	}
	public String getIndex()
	{
		return number;
	}
	
	@Override
	public int compareTo(Cad arg0) {
		return order.compareTo(arg0.getOrder());
	}
}
public class Anagrams
{
	static int tests=0;
	    private static void solve() throws IOException 
	    {
	    	Comparator<Cad> com=new Comparator<Cad>() {
				
				@Override
				public int compare(Cad x, Cad y) {
					return x.getW().compareTo(y.getW());
				}
			};
			tests=readInteger();
			scan.readLine();
	    	boolean flag=false;
	    	while(tests-->0)
	    	{
	    		if(flag)
	    			wr.println();
	    		flag=true;
	    		ArrayList<Cad> words=new ArrayList<Cad>();
	    		String aux="";
	    		int i=0;
	    		while(!(aux=scan.readLine()).isEmpty())
	    		{
	    			String a=aux.replaceAll(" ", "");
	    			char []au=a.toCharArray();
		    		Arrays.sort(au);
	    			words.add(new Cad(aux,new String(au),Integer.toString(i++)));
	    		}
	    		Collections.sort(words, com);
	    		task(words);
	    		words.clear();
	    	}
	    }
	    private static void task(ArrayList<Cad> words)
	    {
	    	String f="%s = %s";
	    	ArrayList<Cad> aux=new ArrayList<Cad>(words);
	    	Collections.sort(aux);
	    	ArrayList<String> ans=new ArrayList<String>();
    		for(int i=0;i<aux.size();i++)
	    	{
    			Cad current=words.get(i);
    			String currentOrder=current.getOrder();
	    		int x=(Collections.binarySearch(aux, new Cad(null,currentOrder,null)));
	    		if(x>=0)
	    		{
	    			String put=current.getW();
	    			String currentIndex=current.getIndex();
	    			int r=x;
	    			int l=x-1;
	    			while(r<aux.size())
	    			{
	    				Cad next=aux.get(r);
	    				if(!currentOrder.equals(next.getOrder()))
	    					break;
	    				if(!current.contains(next.getIndex())&&current.getIndex()!=next.getIndex())
	    				{
	    					ans.add(String.format(f,put,next.getW()));
		    				next.add(currentIndex);
		    				current.add(next.getIndex());
	    				}
	    				r++;
	    			}
	    			while(l>=0)
	    			{
	    				Cad next=aux.get(l);
	    				if(!currentOrder.equals(next.getOrder())&&current.getIndex()!=next.getIndex())
	    					break;

	    				if(!current.contains(next.getIndex())&&current.getIndex()!=next.getIndex())
		    				{
	    						ans.add(String.format(f,put,next.getW()));
	    						next.add(currentIndex);
	    						current.add(next.getIndex());
		    				}
	    				l--;
	    			}
	    		}
	    	}
    		Collections.sort(ans);
    		for(int i=0;i<ans.size();i++)
    		{
    			if(i==ans.size()-1&&tests==0)
    				wr.print(ans.get(i));
    			else
    				wr.println(ans.get(i));
    		}

	    }
	    public static void main(String[] args) 
	    {
	        run();
	    }
	    ///////// I/O things 
	    static BufferedReader scan;
	    static StringTokenizer tokenizer;
	    static PrintWriter wr;
	    public static int readInteger() throws  IOException
	    {
	    	return Integer.parseInt(read());
	    }
	    public static long readLong()throws IOException
	    {
	    	return Long.parseLong(read());
	    }
	    public static double readDouble()throws IOException
	    {
	    	return Double.parseDouble(read());
	    }
	    public static String read() throws IOException
	    {
	    	String res="";
	    	if(tokenizer.hasMoreTokens())
	    	{
	    		res=tokenizer.nextToken();
	    	}
	    	else
	    	{
	    		String aux=scan.readLine();
//	    		if(aux.isEmpty())
//	    		{
//	    			wr.close();
//	    			System.exit(0);
//	    		}
	    		tokenizer=new StringTokenizer(aux," ");
	    		
	    		res=tokenizer.nextToken();
	    	}
	    	return res;
	    }
	    
	    public static void run() 
	    {
	        try 
	        {
	            scan= new BufferedReader(new InputStreamReader(System.in));
	            tokenizer = new StringTokenizer("","");
	            wr = new PrintWriter(System.out);
	            
	            solve();
	            
	            scan.close();
	            wr.close();
	        } catch (Exception e) {
	        	e.printStackTrace();
	        	wr.close();
			System.exit(0);
	        }
	    }
	}

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

Re: 454-Anagrams WA :(

Post by brianfry713 » Wed Jul 30, 2014 7:25 pm

Use class Main
Check input and AC output for thousands of problems on uDebug!

RedGreenCode
New poster
Posts: 7
Joined: Wed May 13, 2015 3:41 am
Location: Seattle, WA, USA
Contact:

Re: 454 - Anagrams

Post by RedGreenCode » Fri Aug 21, 2015 7:38 am

Sometimes it helps to have a process that you follow for every problem. I used this problem as an example in a post I wrote about a process for programming puzzle solving: http://www.redgreencode.com/how-to-atta ... ng-puzzle/

It includes some pseudocode for UVa 454 if you're having trouble with it.
Deliberate practice techniques for software developers -- http://www.redgreencode.com/

Post Reply

Return to “Volume 4 (400-499)”