642 - Word Amalgamation

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

Moderator: Board moderators

Post Reply
novice
New poster
Posts: 3
Joined: Tue Jan 07, 2003 10:51 pm

642 - Word Amalgamation

Post by novice » Sun Feb 16, 2003 2:26 am

I keep getting WA, but I think I have the right concept, can someone give me some input/output?

here is my code in C.pls some1 chk



/* @BEGIN_OF_SOURCE_CODE */
/* @JUDGE_ID: 25021WT 642 C */


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

int sort (char * , char * );


void main()
{
char s[105][8],t[105][8] ,c[8],st[8];
int i,j, print,k,l,len;

// freopen("amalgama.in","r",stdin);
// freopen("amalgama.out","w",stdout);


for(k=0;;k++)
{
scanf("%s",&s[k]);
if(strcmp(s[k],"XXXXXX")==0)
break;
}

for(l=0;;l++)
{
scanf("%s",&t[l]);
if(strcmp(t[l],"XXXXXX")==0)
break;
}


for(j=0;j<l;j++)
{
print = 0;
strcpy(st,t[j]);
len = strlen(st);
qsort(st,len,sizeof(char),
(int (*)(const void *,const void *))sort);


for(i=0;i<k;i++)
if(len == strlen(s))
{
strcpy(c,s);
len = strlen(c)
qsort(c,len,sizeof(char),
(int (*)(const void *,const void *))sort);



if(strcmp(st,c)==0)
{
printf("%s\n",s);
print++;
}
}

if(!print)
printf("NOT A VALID WORD\n");

printf("******\n");

}

fclose(stdin);
fclose(stdout);


}


int sort (char *a , char *b )
{
if(*a > *b)
return 1;
else if( *a < *b)
return -1;
return 0;
}


/* @END_OF_SOURCE_CODE */

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

infinite loop

Post by sohel » Sat Mar 29, 2003 12:12 pm

First consider this loop:

main()
{
while(1)//-----------------------Never ends , condition always true
{
time=0;
while(gets(dic[time])&&strcmp(dic[time],"XXXXXX"))
{
time++;
}
while(gets(nus)&&strcmp(nus,"XXXXXX"))
{
.
.
.
.
.
your program never ends.


and another hint.
you have to sort the words lexicographically if there are multiple outputs for a particular case.

Hope this helps.

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:

Post by ayaw » Mon May 26, 2003 1:38 pm

mine got WA

Code: Select all

#include <stdio.h>
#include <string.h>
int N=0;
char DIC[101][7];

int compare(char *a, char *b) {
	int i;
	for(i=0;a[i];i++) {
		if(a[i]>b[i]) return 1;
		if(b[i]>a[i]) return -1;
	}
	if(b[i]==0) return 0;
	else return -1;
}

void sort(void) {
	char temp[7];
	int i,j,tv;
	for (i=0;i<N-1;i++) {
		for(j=0;j<N-1;j++) {
			if( compare(DIC[j],DIC[j+1]) == 1) {
				strcpy(temp,DIC[j]);
				strcpy(DIC[j],DIC[j+1]);
				strcpy(DIC[j+1],temp);
	}	}	}
}

valid(char *a, char *b) {
	int i,j;
	char temp[7];
	if(strlen(a)!=strlen(b)) return 0;
	strcpy(temp,a);
	for(i=0;b[i];i++)
		for(j=0;temp[j];j++)
			if(b[i]==temp[j]) temp[j]='X';
	for(i=0;temp[i];i++)
		if(temp[i]!='X') return 0;
	return 1;
}

amalgamation(char *a) {
	int i,flag=0;
	for(i=0;i<N;i++)
		if(valid(DIC[i],a)) {
			printf("%s\n",DIC[i]);
			flag = 1;
		}
	return flag;
}

main() {
	char buffer[7];
	while(1) {
		gets(buffer);
		if(strcmp(buffer,"XXXXXX")==0) break;
		strcpy(DIC[N],buffer);
		N++;
	}
	sort();
	while(1) {
		gets(buffer);
		if(strcmp(buffer,"XXXXXX")==0) break;
		if(!amalgamation(buffer)) printf("NOT A VALID WORD\n");
		printf("******\n");
	}
	return 0;
}
peace...

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 642 - Word Amalgamation

Post by plamplam » Thu Jul 07, 2011 7:49 pm

This is a very simple problem, just make sure you are doing the sorting correctly. A simple letter frequency is enough to solve this. And you should really not get Wrong Answer if you manage to pass the sample input. If you do get Wrong Answer, then it is most probably because of your sorting function :P
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 642 - Word Amalgamation

Post by sith » Wed Jun 27, 2012 8:58 pm

Hello.
I've got AC but my Ranking too small.
My solution has been written in Java.
I believe that my solution is pretty optimal but why I've got so low rate?
Here is my solution:

Code: Select all

import java.io.*;
import java.util.*;

class Main {

    private static final String STARS = "******\n";
    private static final String DELIMITER = "XXXXXX";

    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024);

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String line;
        try {
            Map<String, Set<String>> vocabulary = new HashMap<String, Set<String>>();
            while ((line = reader.readLine()) != null) {
                if (line.equals(DELIMITER)) {
                    break;
                }

                String sortedWord = getSortedWord(line);
                Set<String> words = vocabulary.get(sortedWord);

                if (words == null) {
                    words = new HashSet<String>();
                    vocabulary.put(sortedWord, words);
                }

                words.add(line);


            }

            while ((line = reader.readLine()) != null) {
                if (line.equals(DELIMITER)) {
                    break;
                }
                String sortedWord = getSortedWord(line);
                Set<String> words = vocabulary.get(sortedWord);
                if (words == null) {
                    writer.write("NOT A VALID WORD\n");
                    writer.write(STARS);
                } else {
                    String[] sortedWords = words.toArray(new String[words.size()]);
                    Arrays.sort(sortedWords);
                    for (String word : sortedWords) {
                        writer.write(word + "\n");
                    }
                    writer.write(STARS);
                }
            }
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
        }
    }

    private static String getSortedWord(String line) {
        char[] chars = line.toCharArray();
        Arrays.sort(chars);

        return String.valueOf(chars);
    }

}

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

Re: 642 - Word Amalgamation

Post by brianfry713 » Wed Jun 27, 2012 10:10 pm

C is faster than JAVA.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 642 - Word Amalgamation

Post by sith » Wed Jun 27, 2012 11:53 pm

I know it :)
But I look at statistics and there are
JAVA (379) solved submits
1988 - total succefull submits
my ranking is 1958
So I can be 1988 - 379 = 1609 ranking at least
But I believe that all Java solutions are very similar so how can I get 1609 position?

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

Re: 642 - Word Amalgamation

Post by brianfry713 » Fri Jun 29, 2012 12:29 am

Those are the total JAVA submissions, not unique number of user's JAVA AC submissions. Add up the different languages and they equal the number of submissions, so you can't judge how your JAVA code runtime compares based just on that.
Check input and AC output for thousands of problems on uDebug!

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

Re: 642 - Word Amalgamation

Post by uDebug » Wed Mar 26, 2014 8:31 am

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Xoros
New poster
Posts: 3
Joined: Fri Jan 16, 2015 2:31 pm

Re: 642 - Word Amalgamation

Post by Xoros » Tue May 26, 2015 8:31 am

Can someone help me on why I keep getting run time errors?
Thanks :3
here is my code:

Code: Select all


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main{
	public static void main (String[] args) {
		Scanner s = new Scanner(System.in);
		
		ArrayList <String> dicList = new ArrayList <String> ();
		String word;
		while(!(word = s.nextLine()).equals("XXXXXX")){
			dicList.add(word);
		}
		Collections.sort(dicList);
		while(!(word = s.nextLine()).equals("XXXXXX")){
			boolean hasFoundOne = false;
			for(String checker: dicList){
				StringBuilder sb = new StringBuilder();
				sb.append(checker);
				
				int x;
				for(x = 0; x < word.length(); x++){
					if(checker.length() == word.length() && checker.indexOf(Character.toString(word.charAt(x))) != -1){
						sb.deleteCharAt(sb.indexOf(Character.toString(word.charAt(x))));
					}
					else
						break;
				}
				
					if(x == word.length() && sb.toString().equals("")){
						System.out.println(checker);
						hasFoundOne = true;
					}
			
			}
			
			if(!hasFoundOne){
				System.out.println("NOT A VALID WORD");
			}
				
			System.out.println("******");
		}
		
	}
}

Post Reply

Return to “Volume 6 (600-699)”