OJ Board

Hi Little Joey.

I admit my pseudo code is a bit messy. Sorry about that :/
Here's temporarily my source code (I'll remove it as soon as somebody will answer). It might have a few out-of-bounds troubles, but nothing extremly important.

I'm surprised, because I thought one could use MAXCOST+1 ...

Good morning everybody

I've solved (AC in 1.4 sec) 562 (thanks little joey ;) ) with another algorithm, but there is one thing that I don't understand :

int MAX_SUM = 500*100
bool possible_differenceMAX_SUM+1]

possible_difference [first coin]= 1; (all other 0)

for each coin from second to last ...

Okay, I just wondered if there happened to be some number theory behind it to avoid precalc (wich gets AC quite easily, compared to what number theory could be)... Doesn't seem to be, though. Thanks

Larry wrote:Try reading up a little on de Bruijn Sequences/Graphs..

mmmm... very interesting ! Thank you Larry !

Hi everybody

Is there another solution than this too simple precalcuation ?
Could anybody help me to find a more interesting answer ? Is there one ?

Thank you !

No, it's only this judge's limitations. In regionals, you're allowed to use all this and more. (As far as I know anyhow..)
Gee ! I'm surprised ! BigInteteger is extremely powerful : it now includes primality testing (with serveral different methods), primal number generation, fast exponentiation ...

See my post on this subject :

http://online-judge.uva.es/board/viewto ... 5160#25160

Yeah, well I got screwed by the actual ACM regional competition judge.
(...)
So yeah, it's not just the UVA Judge that sucks. Always make sure to wrap your code so that it times out if there's an error or something.

Thank you for this info that I'd been looking for a while : Java in regionals ...

Hi.

Contact Marceh
http://online-judge.uva.es/board/profil ... rofile&u=4
He's the board admin.

Java has a BigInteger class, but you can't use it on the judge..
(...)
You can always download the source code to Sun's implementation of the BigInt.
Hi Larry.
How about in regional contests ? Are BigInteger supported ?
Sun's BigInt implementation is quite heavy, isn't it ? (I believe it's around ...

I don't know about the *really really* quick times, but I'm ranked 12th or so, and I used the FKM algorithm.. (without precalcing..)
Hi

I'm really stuck on this problem : I found a solution using ... hamiltonian cycle :( (edges : numbers, connected to their possible followers, ie n << 1 | 1 and ...

Thanks ! I'll try that
Btw, are Java's BigInteger class allowed in regional contests and/or in world finals ?

Hi

I tried to use the nice solution mentionned above (after having found it by myself). Nevertheless, still TLE
Is it that my BigInteger routines are *really* slow (that alas might be), or is there a hint to accelerate the calculation ?

Thank you !

yiuyuho wrote:Is there something wrong with the sample input?

it says the first line is the number of test cases, it's a 6, but only 4 pairs is followed...

Read the subject and remember what's ouroboros : you can loop.

yiuyuho wrote:Is there something wrong with the sample input?

it says the first line is the number of test cases, it's a 6, but only 4 pairs is followed...

Read the subject and remember what's ouroboros : you can loop.