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

Username:   Password: 
 RegisterRegister   
 [contest]CCC type contest
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
bugzpodder




PostPosted: Thu May 22, 2003 5:15 pm   Post subject: [contest]CCC type contest

seeing that a lot of people are interested in the CCC type contest, i thought i might as well post a question and see how it goes. post your source code here. btw run-time counts. i aint want to wait 30 hours for your program to finish (you'll see why). i'll be the judge and i'll tell you if your correct or not. mods will probably give you bits for this but I'll have to talk to them first.

btw these are ranked as "hard". they are not that hard though.

your goal is to create a reasonable program that does the following. the run-time should be reasonable for *all* test cases. lets say 30 seconds tops.
code:

Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

PROGRAM NAME: numtri
INPUT FORMAT
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
SAMPLE INPUT (file numtri.in)
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

OUTPUT FORMAT
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
30
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: Thu May 22, 2003 6:41 pm   Post subject: (No subject)

lets set the deadline to about one month from now (end of june sounds good?) the winner will be the fastest (run-time) solution provided that it is correct.
Tony




PostPosted: Thu May 22, 2003 7:12 pm   Post subject: (No subject)

if there's a tie between times, then the winner will the the first one who posted the code... Ofcourse I suspect that people will try to modify your code to make it run faster and submit as their own... So I guess you should try to work your bugs out... or do it on purpose while keeping some tricks in mind and then let other people try to mod your program for you Laughing
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
bugzpodder




PostPosted: Thu May 22, 2003 7:18 pm   Post subject: (No subject)

or if you want, PM me the source works too. if it works, i'll post it at the end of the contest.
Martin




PostPosted: Sat May 24, 2003 1:51 am   Post subject: (No subject)

PM'd the code to you Bugz
bugzpodder




PostPosted: Sat May 24, 2003 8:40 am   Post subject: (No subject)

first 5 test cases, OK, when presented with a test case of 1000 lines, it went way too slow. (come on, i told you pure recursion wont work). as in the fibbonacci sequence, you have to try not to calculate anything twice in order to cope with the time limits.

new rule, if the time limit was close with my solution (within 1 second) or better for test cases 6,7,8 then that person will be the winner. I'll judge the winner based upon time correctness (fully correct)->time limit-># of submission->submission date
Martin




PostPosted: Sat May 24, 2003 12:23 pm   Post subject: (No subject)

I'm doing it dynamically now...(I finally think I'm beginning to understand) Right now I'm leaving to play D&D, but I'll post it later.
Homer_simpson




PostPosted: Mon May 26, 2003 8:01 pm   Post subject: (No subject)

could u explain a lil more about what we're suppose to do with that triangle?
Sponsor
Sponsor
Sponsor
sponsor
Martin




PostPosted: Wed May 28, 2003 10:10 pm   Post subject: (No subject)

Alright, I haven't gotten the problem dynamically, but here's my recursive solution. Feel free to mess around with this.

code:
var f : int
open : f, "numtri.in", get
var n : int
get : f, n
var tri : array 1 .. n + 1, 1 .. n + 1 of int
for i : 1 .. n + 1
    for j : 1 .. n + 1
        tri (i, j) := -1
    end for
end for
var c : int := 1

for i : 1 .. n
    for j : 1 .. c
        get : f, tri (i, j)
    end for
    c += 1
end for

var highest : int := -1

proc Sum (r, c : int, sum : int)
    if r not= n + 1 then
        put r, " ", c
        Sum (r + 1, c, sum + tri (r, c))
        if tri (r + 1, c + 1) not= -1 then
            Sum (r + 1, c + 1, sum + tri (r, c))
        end if
    else
        highest := max (sum, highest)
    end if
end Sum

Sum (1, 1, 0)
close : f
open : f, "numtri.out", put
put : f, highest
close : f


This works perfectly, tis just sloooooowwwwww......
Homer_simpson




PostPosted: Wed May 28, 2003 10:15 pm   Post subject: (No subject)

what does ccc stand for anyway?
Tony




PostPosted: Wed May 28, 2003 10:18 pm   Post subject: (No subject)

look in above threads... Canadian Ccomputer Ccompetition
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Martin




PostPosted: Wed May 28, 2003 10:23 pm   Post subject: (No subject)

Actually I think it's Computing not Computer, but not 100% sure on that one.
Tony




PostPosted: Wed May 28, 2003 10:33 pm   Post subject: (No subject)

ether way, the point is the same... some dumb contest we write to show off our programming skillz.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
bugzpodder




PostPosted: Sun Jun 01, 2003 9:08 am   Post subject: (No subject)

on that note, I got silver in stage 2 :S
Tony




PostPosted: Sun Jun 01, 2003 7:25 pm   Post subject: (No subject)

is stage two already over?
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
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  [ 23 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: