[contest]CCC type contest

bugzpodder · **Posted:** Thu May 22, 2003 5:15 pm

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

bugzpodder · **Posted:** Thu May 22, 2003 6:41 pm

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 · **Posted:** Thu May 22, 2003 7:12 pm

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

bugzpodder · **Posted:** Thu May 22, 2003 7:18 pm

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

Martin · **Posted:** Sat May 24, 2003 1:51 am

PM'd the code to you Bugz

bugzpodder · **Posted:** Sat May 24, 2003 8:40 am

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 · **Posted:** Sat May 24, 2003 12:23 pm

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 · **Posted:** Mon May 26, 2003 8:01 pm

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

Martin · **Posted:** Wed May 28, 2003 10:10 pm

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 · **Posted:** Wed May 28, 2003 10:15 pm

what does ccc stand for anyway?

Tony · **Posted:** Wed May 28, 2003 10:18 pm

look in above threads... Canadian Ccomputer Ccompetition

Martin · **Posted:** Wed May 28, 2003 10:23 pm

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

Tony · **Posted:** Wed May 28, 2003 10:33 pm

ether way, the point is the same... some dumb contest we write to show off our programming skillz.

bugzpodder · **Posted:** Sun Jun 01, 2003 9:08 am

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

Tony · **Posted:** Sun Jun 01, 2003 7:25 pm

is stage two already over?

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