Computer Science Canada University Question (Very Hard)

 Author: Martin [ Thu Oct 02, 2003 11:18 pm ] Post subject: University Question (Very Hard) Here's the link to the question. http://www.cs.uwaterloo.ca/features/programmingTeam/index.shtml#sampleProblems if anyone has any insights... if anyone gets it, let's just say that they'll never have a problem with bits for the rest of their life.

 Author: Catalyst [ Thu Oct 02, 2003 11:40 pm ] Post subject: #1 or #2?

Author:  Catalyst [ Fri Oct 03, 2003 12:07 am ]
Post subject:

heres #2

 code: proc Bubble (var a : array 1 .. * of real, n : int)     var hold : real     for i : 1 .. n         for k : 1 .. n - 1             if a (k) > a (k + 1) then                 hold := a (k)                 a (k) := a (k + 1)                 a (k + 1) := hold             end if         end for     end for end Bubble function Distance (x1, y1, x2, y2 : real) : real     result ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 end Distance var numCases : int var numWithSat : int var numStations : int get numCases get numWithSat get numStations var stationListx : array 1 .. numStations of int var stationListy : array 1 .. numStations of int var stationListd : array 1 .. numStations, 1 .. numStations of real var stationListassc : array 1 .. numStations, 1 .. numStations of int var satList : array 1 .. numWithSat + 1 of real for i : 1 .. numWithSat + 1     satList (i) := 100005 end for for i : 1 .. numStations     get stationListx (i)     get stationListy (i) end for for i : 1 .. numStations     for k : 1 .. numStations         stationListd (i, k) := Distance (stationListx (i), stationListy (i), stationListx (k), stationListy (k))     end for end for for i : 1 .. numStations     for k : 1 .. numStations         if (i not= k) then             Bubble (satList, numWithSat + 1)             for j : 1 .. numWithSat + 1                 if (stationListd (i, k) <= satList (numWithSat + 1)) then                     satList (numWithSat + 1) := stationListd (i, k)                 end if             end for         end if     end for end for Bubble (satList, numWithSat + 1) for i : 1 .. numWithSat + 1     put satList (i):2:2 end for

 Author: Amailer [ Fri Oct 03, 2003 12:44 am ] Post subject: if that works... you'll never have a problem with bits for the rest of your life!

 Author: Martin [ Fri Oct 03, 2003 1:31 am ] Post subject: No, number 1. Number 2's easy enough it seems... By the way Catalyst, where'd you get your avatar from...it looks awesome.

 Author: Catalyst [ Fri Oct 03, 2003 6:53 am ] Post subject: http://www.compsci.ca/v2/viewtopic.php?t=2025

 Author: Martin [ Fri Oct 03, 2003 7:58 am ] Post subject: That is awesome

 Author: Tony [ Fri Oct 03, 2003 4:35 pm ] Post subject: can someone teach me the basics of depth-first-search? I wanna try to solve that problem, seems interesting enough.

 Author: Catalyst [ Fri Oct 03, 2003 10:41 pm ] Post subject: might be a little difficult to solve since they provide nothing to test it against

 Author: Tony [ Fri Oct 03, 2003 11:03 pm ] Post subject: just make your own data file. Print out a copy of visual data generated by the data file. Now keep it simple, use a ruler to measure the shortest path. That * DPI = your answer in piixels to compare against. +- a few would be a good output.

 Author: bugzpodder [ Sat Oct 04, 2003 7:16 pm ] Post subject: The first problem is, well, shall I say solved. the website has already outlined the solution ... all you have to do is follow its instructions... The second problem is as stated: quiet easy. but i would like to see someone emailing Gordon Cormack though...

 Author: bugzpodder [ Sat Oct 04, 2003 7:21 pm ] Post subject: if u guys like interesting problems, here is one: http://online-judge.uva.es/p/v1/108.html I solved this one: http://online-judge.uva.es/p/v104/10482.html cant make my program fast enough for this: http://online-judge.uva.es/p/v102/10270.html I know how to do the first two, so i can tell you how to do them (efficiently) if you wish. you may submit your solution in C/C++/Java/Pascal when you are done and they will check it for you. a few thousand others can be found in the problemset in http://online-judge.uva.es 10s limit on these problems

 Author: bugzpodder [ Sat Oct 04, 2003 7:32 pm ] Post subject: 2000 bits to anyone who successfully solves 10270 (the 3rd link in the above thread) before Oct 30, 2003

 Author: rizzix [ Sat Oct 04, 2003 8:32 pm ] Post subject: here's something worth looking into: http://www.topcoder.com/pl/?module=Static&d1=google&d2=google_overview you need to be 18+

 Author: bugzpodder [ Sat Oct 04, 2003 9:21 pm ] Post subject: do you participate in regular topcoder SRMs rizzix? do you have a username?

 Author: rizzix [ Sat Oct 04, 2003 11:35 pm ] Post subject: no not really. i will be signing up soon though. I only want to signup for the contests. So i decided to wait a year.

 :