Page 1 of 1
Reverse Problem.....can somebody give me hints.
Posted: Mon Oct 13, 2003 12:57 pm
by nonstop
Consider a Two-Operation Machine (TOM for short) with nine registers, numbered 1
Posted: Mon Oct 13, 2003 4:07 pm
by makbet
This task is from the recent IOI.
As far as I recall, nobody scored
a perfect 100 on it, so for the
optimal algorithm you'd have to ask
somebody very smart
.
Posted: Tue Oct 14, 2003 1:33 pm
by junjieliang
If you want the link the suggested algorithm is
http://www.ioi2003.org/ioitasks/data-reverse.pdf. But I think if you want answers that are proven to be optimal perhaps you need to use DP or brute force (though I have no idea how to DP it).
thanx
Posted: Tue Oct 14, 2003 3:47 pm
by nonstop
thanks...
the information is useful~~~
thank you many much!!!
about alorithm 2
Posted: Wed Oct 15, 2003 2:11 pm
by nonstop
as the algorithm 2 mentioned in
http://www.ioi2003.org/ioitasks/data-reverse.pdf
i still can't understand it's spirit completely.
for the case of N=44,i initialize the registers' value as :
register 1 2 3 4 5 6 7 8 9
N N-2 N-5 N-9 N-14 N-20 N-27 N-35 0
and i know no matter what value N is, the last register9 must always
be zero....
also,i suppose i've got the idea of the performance steps as N=44;
but i am confused with the initial values when N is bigger than 44
for example,N=70, N=120............
please give me some hints!!
thank you ^^