Oct 2004
8 / 8
Aug 2010
Aug 2010
newbie
Oct '04

hi

i've just sent few programs in java to solve hmro...
i am loosing my nerves and begin wondering what is the sense of solving sthk in java when it has the same time constraints as C or other...
It's known that i/o operations are slower... even after using the class pointed by Adrian Kosowski..

I don't think that it is not possible to solve hmro in java...
i wanted to suggest - maybe more time for programs in java? or just don't count the time spent for i/o operations?

  • created

    Oct '04

  • last reply

    Aug '10
  • 7

    replies

  • 333

    views

  • 6

    users

  • 1

    link

Adrian_Kosowski
Oct '04

Hello,

This may be the case, especially if your java code is not very well optimised.

There has really been a lot of discussion on this in the forum (eg. see the functional language forums). The answer that was given is simple: when adding problems, we should, whenever possible try to provide test data which would rule out slow algorithms, but not slow languages. If we suspect that a problem cannot be solved in some languages, a "warning large i/o... " message is clearly printed in bold type at the bottom of a problem description.

1 month later
Kawigi
Dec '04

I'm not yet consigned that hmro is impossible in java, but I will say it's near so - my code on that one is looking less and less like normal Java and more like a java implementation of memmap.

Of course, the real beef I have is problems with a one-second time limit. Now, Java is probably not the slowest language we have available here, but there is some start-up overhead - half the second available is probably used up by the time our code starts executing.

Today I put in the first 3 time-out solutions to PIR, and the first correct java solution. It's not like I was using an inefficient algorithm, it's just a math problem. However, with possibly half of my second gone to loading the JVM (and a good part of the rest taken up by strictfp calculations probably), I apparently needed to increase the buffer size (on my already buffered I/O) and take out the StringTokenizers I was using to parse out the numbers (and do it the manual pain-in-the-butt way I would have done it in C). The algorithm was constant-time. This isn't any kind of optimization problem by intent, as far as I can tell.

Some competitions (e.g. TopCoder) get around this overhead by having the JVM already loaded on the test machine before testing starts. Since you pretty much need to start a new process to test the problem, this is more than a small change. There's a chance that running java with -server would help, but my understanding is that this matters less than it used to.

As a side, would it be possible to get the test input for HMRO? I'd like to do some profiling and such that doesn't involve repeatedly submitting partial solutions to see how long it takes before the wrong answer comes up :-p

Kawigi
Dec '04

Thanks. Another thing is that these problems go away somewhat when I measure user time rather than real time - I was beating some code up against SBANK today, and I generated a file with 5 tests each with 100000 accounts each. I tried it with sorted and reverse-sorted lists and even with longer strings. On my computer (which should be at best 6 or 7 times as fast as the one it's tested on), it takes 4.5 - 5 seconds of real time but less than 1/5 of a second of user time to execute. If you're already measuring user time, I'm skeptical that it's really taking more than 17 seconds on your side, and if you're using real time, there could be too much variation (even though you're careful not to test two problems at the same time). These tests were done redirecting the input from a file and the output to a file.

29 days later
Kawigi
Jan '05

Well, a month later, I came back and actually did it.

Good news: SBank is officially possible in Java.

Bad news: My implementation basically includes a java version of memmap and memcmp, which could be optimized based on some "coincidences" I noticed in the input format.

As Always: Java people - feel free to contact me if you're beating your head against problems like these.

And, yes, I used the sort from the java libraries smile

1 month later
SmartMalk
Feb '05

well it may be slow and everything but lets face it... it's much better than other judges (if u know what i mean!!!!) in java support, at least this judge let you use the standard input among others!!!!!!!!!!!

SmartMalk

5 years later
system
Aug '10

hi! this is my code in java! i have used o(n) counting sort. can u please point out the reason for the code timing out?

import java.util.Arrays;
public class SBANK {
    static int arr[];
    static StringBuilder acno[];
    static StringBuilder aux[];
    public static void main(String args[]) throws Exception
    {
        int T=0,dig;
        while((dig=System.in.read())!=10 && dig!=-1)
        {
            T=T*10+(dig-48);
        }
        for(int t=0;t<T;t++)
        {
            int n=0;
            while((dig=System.in.read())!=10 && dig!=-1)
            {
                n=n*10+(dig-48);
            }
//            System.out.println("n: "+n);
            acno=new StringBuilder[n];
//            System.out.println("enter ac nos!");
            for(int ac=0;ac<n;ac++)
            {
                acno[ac]=new StringBuilder("");
                while((dig=System.in.read())!=10 && dig!=-1)
                {
                    acno[ac]=acno[ac].append((char)dig);
                }
            }
//            System.out.println("got ac nos!");
//            for(int i=0;i<acno.length;i++)
//            {
//                System.out.println(acno[i]);
//            }
            for(int pos=30;pos>=0;pos--)
        {
            if(!(pos==2 || pos==11 || pos==16 || pos==21 || pos==26 || pos==31))
            {
                arr=new int[n];//
                for(int i=0;i<n;i++)
                {
                    arr[i]=acno[i].charAt(pos)-48;//char becomes ascii code of the char in an operation
                }
                
                counting(arr);
//                    System.out.println("acno after sorting position"+pos+" is:");
//                    for(int i=0;i<acno.length;i++)
//                    {
//                        System.out.println(acno[i]);
//                    }
                }
            }
            System.out.print(acno[0]);
        int cnt=1;
        for(int i=1;i<acno.length;i++)
        {
            boolean same=true;
            for(int j=0;j<acno[0].length();j++)
            {
                if(acno[i].charAt(j)!=acno[i-1].charAt(j))
                {
                    same=false;
                    break;
                }
            }
            if(same)
            {
                cnt++;
            }
            else
            {
                System.out.println(cnt);
                System.out.print(acno[i]);
                cnt=1;
            }
        }
        System.out.println(cnt);
        if(t!=T-1)
            System.in.read();
//            System.out.println("got blank line!");
            System.out.println();
        }
    }
    private static void counting(int[] arr) {
    int b[]=new int[arr.length];
    int k=10;//no element of arr will be more than 9.
    int c[]=new int[k];//aux array
    Arrays.fill(b, -1);
    Arrays.fill(c, 0);
    for(int i=0;i<arr.length;i++)
    {
        c[arr[i]]++;
    }
    for(int i=1;i<=c.length-1;i++)
    {
        c[i]+=c[i-1];
    }
    aux=new StringBuilder[arr.length];
    for(int i=arr.length-1;i>=0;i--)
    {
        b[c[arr[i]]-1]=arr[i];
        aux[c[arr[i]]-1]=acno[i];
        c[arr[i]]--;
    }
    acno=aux;
}
}

even the IO methods i've used r the best known to me!! Pls. help!

Suggested Topics

Want to read more? Browse other topics in JAVA based languages or view latest topics.