University Question (Very Hard)

Martin · **Posted:** Thu Oct 02, 2003 11:18 pm

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.

Catalyst · **Posted:** Thu Oct 02, 2003 11:40 pm

#1 or #2?

Catalyst · **Posted:** Fri Oct 03, 2003 12:07 am

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

Amailer · **Posted:** Fri Oct 03, 2003 12:44 am

if that works...
you'll never have a problem with bits for the rest of your life!

Martin · **Posted:** Fri Oct 03, 2003 1:31 am

No, number 1. Number 2's easy enough it seems...

By the way Catalyst, where'd you get your avatar from...it looks awesome.

Catalyst · **Posted:** Fri Oct 03, 2003 6:53 am

http://www.compsci.ca/v2/viewtopic.php?t=2025

Martin · **Posted:** Fri Oct 03, 2003 7:58 am

That is awesome Wink

Tony · **Posted:** Fri Oct 03, 2003 4:35 pm

can someone teach me the basics of depth-first-search?

I wanna try to solve that problem, seems interesting enough.

Catalyst · **Posted:** Fri Oct 03, 2003 10:41 pm

might be a little difficult to solve since they provide nothing to test it against

Tony · **Posted:** Fri Oct 03, 2003 11:03 pm

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.

bugzpodder · **Posted:** Sat Oct 04, 2003 7:16 pm

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

bugzpodder · **Posted:** Sat Oct 04, 2003 7:21 pm

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

bugzpodder · **Posted:** Sat Oct 04, 2003 7:32 pm

2000 bits to anyone who successfully solves 10270 (the 3rd link in the above thread) before Oct 30, 2003

rizzix · **Posted:** Sat Oct 04, 2003 8:32 pm

here's something worth looking into: http://www.topcoder.com/pl/?module=Static&d1=google&d2=google_overview

you need to be 18+

bugzpodder · **Posted:** Sat Oct 04, 2003 9:21 pm

do you participate in regular topcoder SRMs rizzix? do you have a username?

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members