1. Member
Join Date
Mar 2012
Posts
1
Rep Power
0

## Problem with homework

Hi,

For a homework I need to solve this (Sphere Online Judge (SPOJ) - Problem NAMES) problem from SPOJ and send it there to accept it. In short I have a input data for example as follows:

1. Smith Joe
2. Doe aLex
3. Jo jO
4. whale wALLy
5. Tim Joe
and I need only to read names. As output i have to do a list of most frequently names occured, but when more than one names have same number of occurence I should sort them in alphabetical order. So for this example I should get this output:

JOE 2
ALEX 1
JO 1
WALLY 1
For now I tried a few method to solve this but non of them gets accepted because of Time Limit Exceeded.
Here are so sample codes that I write to solve this problem.

#1
Java Code:
```import java.util.Scanner;

class Main
{

static class osoba
{
String imie = "";
int ilosc = 0;
static int iElementow = 0;
public osoba prev = null;
public osoba next = null;
static public osoba first = null;
static public osoba last = null;

public osoba()
{
this.next = null;
this.prev = null;
this.imie = "";
this.first = this;
this.last = this;
}

public osoba(osoba ha)
{
this.imie = ha.getImie();
this.ilosc = ha.getIlosc();
this.prev = ha.prev;
this.next = ha.next;
}

public osoba(String imie)
{
this.next = null;
this.imie = imie.toUpperCase();
this.zwieksz();
this.last = this;
}

{
imie = imie.toUpperCase();
if(this.imie.equals(""))
{
this.imie = imie;
this.zwieksz();
iElementow++;
}else{
if(this.imie.equals(imie)){
this.zwieksz();
}else{
if(this.next == null){
this.next = new osoba(imie);
this.next.prev = this;
//this.next.last = this.next;
iElementow++;
}else{
}
}
}

public void zwieksz(){ this.ilosc++;}

public String getImie() { return this.imie;}
public int getIlosc() { return this.ilosc;}

public void zamien(osoba A, osoba B)
{
String naz = A.getImie();
int ile = A.getIlosc();

A.imie = B.getImie();
A.ilosc = B.getIlosc();
B.imie = naz;
B.ilosc = ile;

}

}

public static void main (String[] args) throws java.lang.Exception
{
Scanner scan = new Scanner(System.in);
osoba list = new osoba();
int i = 0;

//String temp;
//String[] temp2 = new String[3];
while(scan.hasNext())
{

String temp = scan.nextLine();
String temp2[] = temp.split(" ");

i++;
}

{
for(int as = 0; as < list.iElementow; as++)
for(osoba b = list.first; b.next  != null; b = b.next)
{
if(b.getImie().length() == b.next.getImie().length())
{
for(int q = 0; q < b.getImie().length(); q++)
if(b.getImie().charAt(q) > b.next.getImie().charAt(q))
{
b.zamien(b,b.next);
break;
}

}else{
if(b.getIlosc() < b.next.getIlosc()) b.zamien(b,b.next);}
}
}

for(osoba b = list.first; b  != null; b = b.next)  System.out.println(b.getImie() + " " + b.getIlosc());
}
}```
#2
Java Code:
```import java.util.Scanner;

class Main
{

static class osoba
{
String imie = "";
int ilosc = 0;
static int iElementow = 0;
public osoba prev = null;
public osoba next = null;
static public osoba first = null;
static public osoba last = null;

public osoba()
{
this.next = null;
this.prev = null;
this.imie = "";
this.first = this;
this.last = this;
}

public osoba(osoba ha)
{
this.imie = ha.getImie();
this.ilosc = ha.getIlosc();
this.prev = ha.prev;
this.next = ha.next;
}

public osoba(String imie)
{
this.next = null;
this.imie = imie.toUpperCase();
this.zwieksz();
this.last = this;
}

{
imie = imie.toUpperCase();
if(this.imie.equals(""))
{
this.imie = imie;
this.zwieksz();
iElementow++;
}else{
if(this.imie.equals(imie)){
this.zwieksz();
}else{
if(this.next == null){
this.next = new osoba(imie);
this.next.prev = this;
//this.next.last = this.next;
iElementow++;
}else{
}
}
}

public void zwieksz(){ this.ilosc++;}

public String getImie() { return this.imie;}
public int getIlosc() { return this.ilosc;}

public void zamien(osoba A, osoba B)
{
String naz = A.getImie();
int ile = A.getIlosc();

A.imie = B.getImie();
A.ilosc = B.getIlosc();
B.imie = naz;
B.ilosc = ile;

}

}

public static void main (String[] args) throws java.lang.Exception
{
Scanner scan = new Scanner(System.in);
osoba list = new osoba();
int i = 0;

//String temp;
//String[] temp2 = new String[3];
while(scan.hasNext())
{

String temp = scan.nextLine();
String temp2[] = temp.split(" ");

i++;
}

{
for(int as = 0; as < list.iElementow; as++)
for(osoba b = list.first; b.next  != null; b = b.next)
{
if(b.getImie().length() == b.next.getImie().length())
{
for(int q = 0; q < b.getImie().length(); q++)
if(b.getImie().charAt(q) > b.next.getImie().charAt(q))
{
b.zamien(b,b.next);
break;
}

}else{
if(b.getIlosc() < b.next.getIlosc()) b.zamien(b,b.next);}
}
}

for(osoba b = list.first; b  != null; b = b.next)  System.out.println(b.getImie() + " " + b.getIlosc());
}
}```
#3
Java Code:
```class Main
{
static java.io.BufferedWriter write = new java.io.BufferedWriter(new java.io.OutputStreamWriter(System.out));
static java.io.FileInputStream FIO() throws java.io.FileNotFoundException
{
return new java.io.FileInputStream("c:\\blueJ.txt");
}

{
int intChar;
java.lang.StringBuffer tempChar = new java.lang.StringBuffer();
int spaceCount = 0;
while(spaceCount != 2)
{
if(intChar == 32) //spacja
++spaceCount;
}
while(intChar > 64 && intChar < 123){
tempChar.append((char)intChar);
}
return tempChar.toString().toUpperCase();
}
static class imie
{ String imie;
int liczba_wystapien;
public imie(String imie)
{
this.imie = imie;
liczba_wystapien = 0;
}
public imie(){}
public imie(String imiee, int liczba_wystapien)
{
this(imiee);
this.liczba_wystapien = liczba_wystapien;
}

void zwieksz()
{
liczba_wystapien++;
}

String getImie()
{return this.imie;}

int getLiczbe()
{return this.liczba_wystapien;}

}

static public class imieComparator implements java.util.Comparator<imie>{

@Override
public int compare(imie i1, imie i2)
{
if (i1.getLiczbe() == i2.getLiczbe())
{
return i2.getImie().compareTo(i1.getImie());
}else{
return i1.getLiczbe() > i2.getLiczbe() ? 1:-1;
}
}
}

public static void main (String[] args) throws java.lang.Exception
{

//long start = java.lang.System.nanoTime();
java.util.ArrayList<String> lis = new java.util.ArrayList();
{
}
java.util.Collections.sort(lis);

java.util.ArrayList arrImie = new java.util.ArrayList();
int lw = 1;
for(int i = 0; i < lis.size(); i++)
{
if(i < lis.size() - 1 && lis.get(i).equals(lis.get(i+1)))
{
lw++;
}else{
imie b = new imie(lis.get(i), lw);
lw = 1;
}
}
imieComparator compar = new imieComparator();
java.util.Collections.sort(arrImie, compar);
for(int i = arrImie.size()-1; i >= 0; i--){
imie a = (imie)arrImie.get(i);
write.write(a.getImie() + " " + a.getLiczbe() + "\n");
}
//write.write("Dodales: " + lis.size() + " z czego " + arrImie.size() + " jest unikalna\n");
//write.write("Wczytywanie trwało: " + (java.lang.System.nanoTime() - start));
write.flush();
}
}```
#4
Java Code:
```class Main
{
static java.io.BufferedWriter write = new java.io.BufferedWriter(new java.io.OutputStreamWriter(System.out));
static String tabKeys[];
static int tabValues[];

{
int intChar;
java.lang.StringBuffer tempChar = new java.lang.StringBuffer();
int spaceCount = 0;
while(spaceCount != 2)
{
if(intChar == 32) //spacja
++spaceCount;
}

while(intChar > 64 && intChar < 123){
tempChar.append((char)intChar);
}

return tempChar.toString().toUpperCase();
}

static class rekord
{
public String imie;
public int liczba;
public rekord(){
this.imie = null;
this.liczba = 0;
}
public rekord(String imie, int liczba){
this.imie = imie;
this.liczba = liczba;
}
}

static public class leComparator implements java.util.Comparator<rekord>{

@Override
public int compare(rekord i1, rekord i2)
{
if (i1.liczba == i2.liczba)
{
return i2.imie.compareTo(i1.imie);
}else{
return i1.liczba > i2.liczba ? 1:-1;
}
}
}

public static void main (String[] args) throws java.lang.Exception
{
//long start = java.lang.System.nanoTime();
java.util.HashMap<String, Integer> mapaImion = new java.util.HashMap<String, Integer>(100000,1.0f);

Integer tempI = new Integer(0);
String imie;
{
tempI = mapaImion.put(imie, 1);
if(tempI != null)
{
mapaImion.put(imie, tempI+1);
}
}

java.util.List listKeys = new java.util.ArrayList(mapaImion.keySet());
java.util.List<Integer> listValues = new java.util.ArrayList<Integer>(mapaImion.values());
Object[] listaK = listKeys.toArray();
Integer[] listaWa = listValues.toArray(new Integer[listValues.size()]);

tabKeys = java.util.Arrays.copyOf(listaK, listaWa.length, String[].class);
tabValues = new int[listaWa.length];
for(int i = 0; i < listaWa.length; i++) tabValues[i] = listaWa[i].intValue();

rekord a = new rekord();
a.imie = tabKeys[0];

rekord posortowanaLista[] = new rekord[tabKeys.length];
for(int i = 0; i < tabKeys.length; i++) posortowanaLista[i] = new rekord(tabKeys[i], tabValues[i]);
java.util.Arrays.sort(posortowanaLista, new leComparator());

for(int i = posortowanaLista.length-1; i>= 0; i--) write.write(posortowanaLista[i].imie + " " + posortowanaLista[i].liczba + "\n");

// write.write("\nWczytywanie trwało: " + ((java.lang.System.nanoTime() - start)/1000000));
write.flush();
}
}```
So far my codes are to slow to gets accepted and I'm actualy out of ideas of how to solve this efficient so please give me some advice of what should I do or use to solve this.

2. ## Re: Problem with homework

What areas of the code take too long?

Can you explain why you have so much code?
If you read a line and parse it to words and use the words as key to a hashtable with a value being the count of the words found and then sorted that.
Last edited by Norm; 03-16-2012 at 11:36 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•