Sense of java

[newbie]

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?

[Adrian_Kosowski]

Hello,

I don't think that it is not possible to solve hmro in java...

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

i wanted to suggest - maybe more time for programs in java? or just don't count the time spent for i/o operations?

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.

[Kawigi]

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

[MaxSU_sof]

you can use this generator for the problem from the post (posted by plucho)
spoj.sphere.pl/forum/viewtopic.php?t=203

goodluck

[Kawigi]

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.

[Kawigi]

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

[SmartMalk]

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

[system]

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!