Problem J  World Finals 2005
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Here's how we did problem D:
First, finding the number of shuffles is fairly easy.
Then, we construct a permutation P based on the "misplaced" elements of the input (if the element at the place where we should have an A was B (where we might have B = A), this permutation maps A > B).
Next we look at the cycle structure of P. The assumption of our solution which we never proved but which seems innocent enough if you think about it a while is that any two elements which have been accidentally swapped in an error in one of the shuffles must be in the same cycle of P. Matching this against pairs of elements which were actually adjacent during the performed shuffles, we get a relatively small set of possible errors which could have been made.
Then, finally, we simply do an exhaustive search among these (relatively few) possible errors to find the way using as few errors as possible.
First, finding the number of shuffles is fairly easy.
Then, we construct a permutation P based on the "misplaced" elements of the input (if the element at the place where we should have an A was B (where we might have B = A), this permutation maps A > B).
Next we look at the cycle structure of P. The assumption of our solution which we never proved but which seems innocent enough if you think about it a while is that any two elements which have been accidentally swapped in an error in one of the shuffles must be in the same cycle of P. Matching this against pairs of elements which were actually adjacent during the performed shuffles, we get a relatively small set of possible errors which could have been made.
Then, finally, we simply do an exhaustive search among these (relatively few) possible errors to find the way using as few errors as possible.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
problem C is very similar to a topcoder problem; for an idea for the solution read the description of the solution for topcoder problem Triptych: http://www.topcoder.com/index?t=statist ... nline_rd_4
And problem I can be solved with greedy in O(n^2)
If I said something wrong, please someone who participated in the finals correct me.
And problem I can be solved with greedy in O(n^2)
If I said something wrong, please someone who participated in the finals correct me.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
abishek Said
"the problem set was very good and I really enjoyed it, though I should crib saying that too much of geometry was there. A, B, E, F, G all had some kind of floating point operations involved and I have always hated floating point numbers "
F had nothing to do with floating point number. Although at first sight I also thought that floating point number is a must for this problem. As far as I know that G had nothing to do with floating point number as well. G was the hardest problem according to derek (he solved all the problems I didn't). Voronoi diagram was not required for B. I guess some teams did not touch it considering that they need to implement V diagram.
The Author of D was Bonomo.
"the problem set was very good and I really enjoyed it, though I should crib saying that too much of geometry was there. A, B, E, F, G all had some kind of floating point operations involved and I have always hated floating point numbers "
F had nothing to do with floating point number. Although at first sight I also thought that floating point number is a must for this problem. As far as I know that G had nothing to do with floating point number as well. G was the hardest problem according to derek (he solved all the problems I didn't). Voronoi diagram was not required for B. I guess some teams did not touch it considering that they need to implement V diagram.
The Author of D was Bonomo.
I quite agree and said so at the coaches' briefing. I believe there was general consensus.Per wrote:By the way, regarding the problem set: despite us not doing as good as we had hoped, I really enjoyed the problem set, it was definitely one of the better ones I've seen (and I've seen quite a few by now ).
Re: hmm
I think we need to find the number of intersections of the road with vornoi boundaries in problem B. But I don't see how to find it without the vornoi diagram itself.shahriar_manzoor wrote: Voronoi diagram was not required for B. I guess some teams did not touch it considering that they need to implement V diagram.
May be I missed it but where the judges ever called to the stage or introduced at the finals?
I don't think so. (except for the price winning ceremony where judges just accompanied the teams)

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
Yes u missed it. But it is not a big deal as the contestants r to be focused in the prize giving ceremony. Judges were on stage for a brief period as the link below shows:
http://icpc.baylor.edu/dmt/view_image.a ... 6&size=reg.
It is odd to post someones own image but I don't think anyone will be able to answer this question but me as I struggled a lot to find this image.
http://icpc.baylor.edu/dmt/view_image.a ... 6&size=reg.
It is odd to post someones own image but I don't think anyone will be able to answer this question but me as I struggled a lot to find this image.