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

Username:   Password: 
 RegisterRegister   
 University Question (Very Hard)
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Martin




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
Catalyst




PostPosted: Thu Oct 02, 2003 11:40 pm   Post subject: (No subject)

#1 or #2?
Catalyst




PostPosted: Fri Oct 03, 2003 12:07 am   Post subject: (No 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
Amailer




PostPosted: Fri Oct 03, 2003 12:44 am   Post subject: (No subject)

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




PostPosted: Fri Oct 03, 2003 1:31 am   Post subject: (No 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.
Catalyst




PostPosted: Fri Oct 03, 2003 6:53 am   Post subject: (No subject)

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




PostPosted: Fri Oct 03, 2003 7:58 am   Post subject: (No subject)

That is awesome Wink
Tony




PostPosted: Fri Oct 03, 2003 4:35 pm   Post subject: (No subject)

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

I wanna try to solve that problem, seems interesting enough.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Catalyst




PostPosted: Fri Oct 03, 2003 10:41 pm   Post subject: (No subject)

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




PostPosted: Fri Oct 03, 2003 11:03 pm   Post subject: (No 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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
bugzpodder




PostPosted: Sat Oct 04, 2003 7:16 pm   Post subject: (No 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...
bugzpodder




PostPosted: Sat Oct 04, 2003 7:21 pm   Post subject: (No 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
bugzpodder




PostPosted: Sat Oct 04, 2003 7:32 pm   Post subject: (No subject)

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




PostPosted: Sat Oct 04, 2003 8:32 pm   Post subject: (No subject)

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

you need to be 18+
bugzpodder




PostPosted: Sat Oct 04, 2003 9:21 pm   Post subject: (No subject)

do you participate in regular topcoder SRMs rizzix? do you have a username?
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 2  [ 16 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: