Congrats to Waterloo ACM team

[Aidin Kashigar]

Congratulations to Waterloo's ACM team which ended up 4th in the ACM World Finals. If you're interested, the results are posted at http://icpc.baylor.edu/icpc/Finals/default.htm

[jamonathin]

Props to Waterloo!

[Tony]

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]

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

[thegoose]

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]

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]

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

[[Gandalf]]

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

[thegoose]

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]

tony... idunno what ur looking at, but thats not what i see when i go
http://icpc.baylor.edu/icpc/Finals/Standings.html

[Tony]

ops, I was looking at a different page
http://icpc.baylor.edu/icpc/Finals/Scoreboard/index.html

[Martin]

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

[Aidin Kashigar]

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]

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...

For anyone interested, here're the problems.
http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf

[thegoose]

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...

For anyone interested, here're the problems.
http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf

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.