Posted: 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.
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.
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
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)
8 1 0
2 7 4 4
4 5 2 6 5
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
Posted: 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.
Posted: 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
Posted: 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.
Posted: Sat May 24, 2003 1:51 am Post subject: (No subject)
PM'd the code to you Bugz
Posted: 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
Posted: 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.
Posted: 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?
Posted: 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.
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
var c : int := 1
for i : 1 .. n
for j : 1 .. c
get : f, tri (i, j)
c += 1
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))
highest := max (sum, highest)
Sum (1, 1, 0)
close : f
open : f, "numtri.out", put
put : f, highest
close : f
This works perfectly, tis just sloooooowwwwww......
Posted: Wed May 28, 2003 10:15 pm Post subject: (No subject)
what does ccc stand for anyway?
Posted: Wed May 28, 2003 10:18 pm Post subject: (No subject)
look in above threads... Canadian Ccomputer Ccompetition