Results 1 to 2 of 2
  1. #1
    Cin123 is offline Member
    Join Date
    Mar 2012
    Posts
    1
    Rep Power
    0

    Default 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;
    }
    
    public void add(String imie)
    {
    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{ 
    		this.next.add(imie);}
    	}
    }
    }
    
    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(" ");
    		list.first.add(temp2[2]);
    		
    		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;
    }
    
    public void add(String imie)
    {
    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{ 
    		this.next.add(imie);}
    	}
    }
    }
    
    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(" ");
    		list.first.add(temp2[2]);
    		
    		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.BufferedReader scan = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    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");
    }
    
    static String readName() throws java.lang.Exception
    {
    int intChar;
    java.lang.StringBuffer tempChar = new java.lang.StringBuffer();
    int spaceCount = 0;
    while(spaceCount != 2)
    {
    intChar = scan.read();
    if(intChar == 32) //spacja
            ++spaceCount;
    }
    intChar = scan.read();
    while(intChar > 64 && intChar < 123){
    tempChar.append((char)intChar);
    intChar = scan.read();
    }
    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
        {
         
        //scan = new java.io.BufferedReader(new java.io.InputStreamReader(FIO()));    
        //long start = java.lang.System.nanoTime();
            java.util.ArrayList<String> lis = new java.util.ArrayList();
                    while(scan.ready())
                    {
                    lis.add(readName());
                    }
            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);
                    arrImie.add(b);
                    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.BufferedReader scan = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    static java.io.BufferedWriter write = new java.io.BufferedWriter(new java.io.OutputStreamWriter(System.out));
    static String tabKeys[];
    static int tabValues[];
    
    static String readName() throws java.lang.Exception
    {
        int intChar;
        java.lang.StringBuffer tempChar = new java.lang.StringBuffer();
        int spaceCount = 0;
        while(spaceCount != 2)
        {
                intChar = scan.read();
                if(intChar == 32) //spacja
                ++spaceCount;
        }
        
        intChar = scan.read();
        while(intChar > 64 && intChar < 123){
            tempChar.append((char)intChar);
            intChar = scan.read();
        }
        
        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
        {  
        //scan = new java.io.BufferedReader(new java.io.FileReader("c:\\blueJ.txt")); 
        //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;
        while(scan.ready())
        {
            imie = readName();
            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.

    Thanks in advance! :)

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,880
    Rep Power
    25

    Default 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.

Similar Threads

  1. efficiency problem with homework
    By marcosol in forum New To Java
    Replies: 15
    Last Post: 09-19-2012, 07:56 PM
  2. Letter counter homework problem
    By Djgnl in forum New To Java
    Replies: 15
    Last Post: 09-24-2011, 03:37 AM
  3. Help with Homework Problem
    By Holy_Zombies in forum New To Java
    Replies: 6
    Last Post: 10-05-2010, 07:26 AM
  4. Problem using thread +rmi in my homework
    By IbrahimAbbas in forum Threads and Synchronization
    Replies: 10
    Last Post: 04-14-2008, 10:24 PM
  5. Homework PREREQUISITE Problem
    By ChrisC in forum New To Java
    Replies: 7
    Last Post: 11-27-2007, 06:36 AM

Posting Permissions

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