Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Congrats to Waterloo ACM team
Index -> Contests
Goto page 1, 2, 3  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Aidin Kashigar




PostPosted: Wed Apr 06, 2005 12:38 pm   Post subject: Congrats to Waterloo ACM team

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
Sponsor
Sponsor
Sponsor
sponsor
jamonathin




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

Claping Dance Claping Dance Claping Dance Claping Dance Claping Dance Claping Dance Claping
Props to Waterloo!
Tony




PostPosted: 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 Very Happy but lucky for everybody else, I'm lazy Wink
Andy




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

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




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

Cool...gj to the Waterloo team Very Happy
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




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

Andy wrote:
Confused Confused Confused 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? Thinking
jamonathin




PostPosted: 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?... Razz
[Gandalf]




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

lol
Russians and Chinese always own compsci Very Happy always getting the highest marks...
Sponsor
Sponsor
Sponsor
sponsor
thegoose




PostPosted: 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? Thinking

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




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

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




PostPosted: Thu Apr 07, 2005 8:31 am   Post subject: (No subject)

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




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

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




PostPosted: 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




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

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




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

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.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 3  [ 31 Posts ]
Goto page 1, 2, 3  Next
Jump to:   


Style:  
Search: