JAVA-Difficulties We Face

[pepak]

Never mind, looking at the runtime sources it seems that read(Byte[]) is just using read() repeatedly so it is useless for optimalization purposes. Still, I wonder... Is it moral to cheat against a cheater?

[Darko]

Is it moral to cheat against a cheater?

What do you mean by that? More precisely - who do you think is cheating?

[Darko]

Here is one more:
WA

Code: Select all

people[i] = new Person(parseInt(st.nextToken()),parseInt(st.nextToken()));

AC

Code: Select all

int x = parseInt(st.nextToken());
int y = parseInt(st.nextToken());
people[i] = new Person(x, y);

This is confusing...

[chunyi81]

Here is one more:
WA

Code: Select all

people[i] = new Person(parseInt(st.nextToken()),parseInt(st.nextToken()));

AC

Code: Select all

int x = parseInt(st.nextToken());
int y = parseInt(st.nextToken());
people[i] = new Person(x, y);

This is confusing...

Wait a minute... I think this code will not even compile. It should be Integer.parseInt yes? I always use the parseInt method in Integer class this way.

[Darko]

Sorry, should've mentioned that parseInt() is my own. I ended up writing a bunch of standard library methods for one reason or another.

I still submit in Java, you know (unlike some! )

[Darko]

...and another one:
AC

Code: Select all

st = new StringTokenizer(readLine());
			String s = st.nextToken();
			int val = parseInt(st.nextToken());
			list.put(s, new Integer(val));

WA

Code: Select all

st = new StringTokenizer(readLine());
			list.put(st.nextToken(), new Integer(parseInt(st.nextToken())));

It's not even a case of multiple dereferencing, I have no idea why the latter one fails.

[chunyi81]

...and another one:
AC

Code: Select all

st = new StringTokenizer(readLine());
			String s = st.nextToken();
			int val = parseInt(st.nextToken());
			list.put(s, new Integer(val));

WA

Code: Select all

st = new StringTokenizer(readLine());
			list.put(st.nextToken(), new Integer(parseInt(st.nextToken())));

It's not even a case of multiple dereferencing, I have no idea why the latter one fails.

With regards to the code you posted, UVA's Java compiler gcj will compile Java to C. And for parameters passed to C functions, they are passed from right to left (__cdecl keyword, default) usually unless it is specified using __stdcall keyword (the Pascal way of passing parameters to functions, left to right)

So therefore the first token might have been passed to the parseInt function because of the behaviour of parameter passing to C functions, instead of what you intended - as the first parameter to the put function.

Correct me if I am wrong.

[Darko]

Oh, man, that makes perfect sense - I just hope they are getting rid of this gcj nonsense with the new Judge.

[Darko]

Well, I guess it will take a while until we see "normal" Java, so I will share what I just found out about the I/O:

You don't have to read input byte by byte - you can use a (sort of a) buffered input with System.in.read(byte[],int,int).

Recently there were some problems in which I couldn't even read the input within time limit. So I played around with some I/O and found out that read(byte[],int,int) for some reason doesn't work for lengths > 2048.

So this is how I read those types of inputs.
Note 1: input file must be small enough so you don't get MLE - but it should be ok up to ~27MB. Pick powers of two - 8388608 is better than 7800000, for instance.
Note 2: This code deals with ints only and it will fail to read -2^31 - if you need something like that, change to longs or something. I haven't used it to read Strings... I will eventually. It is best to use it for inputs containing ints in which you are given the number of test cases (so you don't look for the end of input)
Note 3: It can be modified to read lines - take that code from nextInt() and fiddle with it...

Code: Select all

import java.io.IOException;

class MainReadAll {

	int inputIndex;

	int inputSize;

	byte[] input;

	void work() {

		readAll(65536); // pick estimated size of input - powers of two work the
		                       // best
		int n;
		while((n=nextInt())!= Integer.MIN_VALUE){
			// do stuff
		}
	}

	private void readAll(int bufSize) {
		input = new byte[bufSize];
		int start = 0;
		inputSize = 0;
		while (true) {
			try {
				int read = System.in.read(input, start, 2048);
				inputSize += read;
				if (read < 2048)
					break;
				start += 2048;
			} catch (IOException e) {
			}
		}
		inputIndex = 0;
	}

	private int nextInt() {
		// find first digit
		while (input[inputIndex] < '-') {
			if (inputIndex == inputSize)
				return Integer.MIN_VALUE;
			inputIndex++;
		}
		int k = 0;
		int sign = 1;
		if (input[inputIndex] == '-') {
			inputIndex++;
			sign = -1;
		} else
			k = input[inputIndex++] - 48;
		// read the number
		while (input[inputIndex] >= '0' && input[inputIndex] <= '9') {
			k *= 10;
			k += (input[inputIndex++] - 48);
		}
		return k * sign;
	}

	public static void main(String args[]) {
		MainReadAll myWork = new MainReadAll();
		myWork.work();
	}
}

Please try modifying it to suit your needs or particular problem's I/O, this code is a problem specific one - meaning, please don't complain that it doesn't work for problem #12345 or something

[MAK]

It's sad to see that even after so much time Java support at this OJ is still pathetic. I don't know why the people running this judge have to cripple java in such a way.

[jan_holmes]

Is BigInteger class provided here ?

[MAK]

Is BigInteger class provided here ?

Nope. You have to make your own BigInteger class. I think there is an implementation posted somewhere in these forum Java pages.

[MAK]

I just saw something very interesting at the Bug Fixes forum. Someone (probably one of the system admins) says that

1. Java uses 190+ MB of RAM just for a single System.out.println

2. Java is 'unsecure'. Java classes may illegally access system data or files.

I'm quite sure that the second statement is false.
I have a similar feeling about the first one too, but I've never tried measuring the amount of memory taken up any of my Java programs, so I wouldn't know for sure. Can someone shed some light on this?

[Darko]

No, I don't think that the first statement was made by an admin. I think someone saw the memory usage on SPOJ, which allocates 192MB, but that doesn't mean it uses that much.

There is probably a better way (especially with Java 1.6, from what I understand), but you can try how much memory your program uses by limiting the heap memory with -Xmx switch, e.g.:
java -Xmx16m Main.java < in

Play with the number and soon you'll find out how much memory you need. Now, that being said, I ran into couple of problems that, although they run with 16MB heap on my PC they run out of memory on UVa, and it is limited to 32MB.

Why these things happen? No idea, but it probably has something to do with the fact that UVa uses gcj, who knows how that thing compiles Java code to binary (it is compatible with Java 1.1, that's why Java is very limited here).

That probably explains why "Java" is able to access restricted functions, if they were running a bytecode within a JVM, it wouldn't be a problem.

[MaVa]

I code only java, shure it is a pain in the ... sometimes.
but in real competitions it is a good choice.

Java is not that much slower on input and output, but you must take care!!

1. using System.out.print*() will make the stream flush, which takes time, by using System.out.write() you can save time, and gain work.
(try on 10189)

2. readLn() metods given as examle on the page is slow, because when you make an array such as byte[] java must make shure all bytes are decleared to right initial value, as opposed to C. Using a small array speed thing up.

3. Integer.parseInt() is not optimized either, to many checks for invalid arguments. On this site you can rely on input-format!!
(if it says positive numbers, dont check for minus signs)

I dont know how to best test the difference in input speed, but even on problems with lots of input I think it is possible to make fast java programs.
There is indeed some difference in I/O-speed.

Good Luck
MaVa