Posted: Wed Apr 06, 2005 12:50 pm Post subject: (No subject)

Props to Waterloo!

Tony

Posted: Wed Apr 06, 2005 1:29 pm Post subject: (No subject)

Those crazy Russian took 1st and 2nd places.

Now as a Russian kid attending Waterloo, I have lots and lots of potential but lucky for everybody else, I'm lazy

Andy

Posted: Wed Apr 06, 2005 5:43 pm Post subject: (No subject)

err tony, china was number 1, russia was second and third

thegoose

Posted: Wed Apr 06, 2005 7:01 pm Post subject: (No subject)

Cool...gj to the Waterloo team
Chinese ownage again...
Aidin...think you and Simon can match that next year? (I presume that you guys will do ACM after going to Waterloo)

Tony

Posted: Wed Apr 06, 2005 7:49 pm Post subject: (No subject)

Andy wrote:

err tony, china was number 1, russia was second and third

that website wrote:

1 Moscow State University
2 St Petersburg Institute of Fine Mechanics and Optics
3 University of Waterloo

Since when is Moscow State University located in China?

jamonathin

Posted: Wed Apr 06, 2005 8:25 pm Post subject: (No subject)

They went there in Rush Hour 2, didn't you see them there tony?...

[Gandalf]

Posted: Thu Apr 07, 2005 1:49 am Post subject: (No subject)

lol
Russians and Chinese always own compsci always getting the highest marks...

Sponsor Sponsor

thegoose

Posted: Thu Apr 07, 2005 6:15 am Post subject: (No subject)

that website wrote:

1 Moscow State University
2 St Petersburg Institute of Fine Mechanics and Optics
3 University of Waterloo

tony wrote:

Since when is Moscow State University located in China?

http://icpc.baylor.edu/icpc/Finals/default.htm
Rank Name Solved Time
1 Shanghai Jiaotong University 8 1517
2 Moscow State University 7 711
3 St Petersburg Institute of Fine Mechanics and Optics 7 888
4 University of Waterloo 7 1046
It also says on the site entrance that the winning team was Shanghai Jiaotong University.

Andy

Posted: Thu Apr 07, 2005 6:38 am Post subject: (No subject)

Posted: Thu Apr 07, 2005 11:24 am Post subject: (No subject)

I'm trying to do problem A....damn that's hard...

Aidin Kashigar

Posted: Thu Apr 07, 2005 2:24 pm Post subject: (No subject)

well, you're going at it the wrong way. None of the 80 teams successfully solved, or even submitted a solution, to problem A. You might have more luck on problem E or H.

Martin

Posted: Thu Apr 07, 2005 2:38 pm Post subject: (No subject)

Aidin Kashigar wrote:

well, you're going at it the wrong way. None of the 80 teams successfully solved, or even submitted a solution, to problem A. You might have more luck on problem E or H.

I found that out after I started. Ahh well, it doesn't seem too bad...

Posted: Thu Apr 07, 2005 3:36 pm Post subject: (No subject)

martin wrote:

Aidin Kashigar wrote:

well, you're going at it the wrong way. None of the 80 teams successfully solved, or even submitted a solution, to problem A. You might have more luck on problem E or H.

I found that out after I started. Ahh well, it doesn't seem too bad...

The 'simple' solution is easier than you think. This might run into issues with float point but it should get MOST of the points (which is same as none for ACM). I'm not saying this is an easy problem since the ugly case work and the possible float point error. So here it is (please point out if I'm stupid)
Several Cases (of the lines in the picture requiring mapping):
1.
There are more than 2 horizontal and 1 vertical lines.
Pick the lines which each of the 3 segments maps onto. This should determine the shift/magnification uniquely. The rest is trivial (cycle through, binary search). (N^2)M(N+M)log(N+M) calculations. Should run fast if pruned.
2.
1 horizontal and 1 vertical.
Should be able to map onto any intersetion point if shrinked by a factor of infinity.
3.
Everything is horizontal or everything is vertical
Without loss of generality, assume they're vertical Pick the 2 lines and the lines they maps onto. This should give what lines each line map onto and their respective length. Then figure out the 'region' the first line can be in without causing an intersection a horizontal line in the region. If the region exist, a mapping would be possible. This is (N^2)(N+M)log(N+M)
4.
All horizontal segment have the same x value and all vertical have the same y-value:
There would be a 'focal point'. Map this to all such points on the 'big' picture (NM such points). Then for each segment, find the 'magnification' range for it to map to another segment (aka. check each pair). NMNM=(N^2)(M^2) operations. If at the end, the range exist, then it's doable. This might be a bit slow, but should work out.

Overall, the solution works by the idea of 2 lines fixes the transformation ratio, 1 horizontal and 1 vertical fixes the location of the transfer. Time complexity is O((N^2)M(N+M)log(N+M)) with a fairly small factor due to pruning.