Computer Science Canada

Ccc 2007!
Author:  Naveg [ Tue Feb 27, 2007 4:37 pm ]
Post subject:  Ccc 2007!
I did the CCC Senior today, as I'm sure many other people on this site did as well. How did you all find it?
Author:  Clayton [ Tue Feb 27, 2007 4:40 pm ]
Post subject:  Re: Ccc 2007!
I found it pretty good. Finished S1 in ~10 minutes, S2 took a little more time purely because I was thinking about it in the wrong way. Then for the last 2 hours I worked solid on S5 and pwned it Very Happy
Author:  klopyrev [ Tue Feb 27, 2007 4:52 pm ]
Post subject:  Re: Ccc 2007!
That was a fun contest!!! I finished 1-4 in the first 1 hour. 4 was too easy. Took me 2 hours to finish 5. There is 1 problem though. My teacher started marking my work and it had a lot of input reading problems because of the test data. Many of the files for problem 1 have an extra space on the first line, which throws off parsing the int in java. Also, many of the other test files have a blank line between each line of data. I don't think that I should lose marks because of that. Hopefully they will change the test data in a few days.

KL
Author:  Clayton [ Tue Feb 27, 2007 4:57 pm ]
Post subject:  Re: Ccc 2007!
If you ask me, all the data and such was poorly handled this year....
Author:  PaulButler [ Tue Feb 27, 2007 5:00 pm ]
Post subject:  RE:Ccc 2007!
I completed S1-S5, but I had to use a brute-force approach for S5. I would love to see the correct way, if anyone has a copy of their code (I don't know what the rules are around sharing this).

I found it quite easy, half way through I got worried that I might have been writing the junior instead of the senior.

That's too bad about the test data, mine was written in Java as well and things like this would definitely screw it up.
Author:  zwnage [ Tue Feb 27, 2007 5:21 pm ]
Post subject:  RE:Ccc 2007!
Can anyone tell me how this is marked? Would they check for commenting, format, etc, or are they just looking at your run window? Is there a time factor like who hands it in fastest? I did the junior today, but I definitely should have asked stuff like that before the test >.<
Author:  eklypze [ Tue Feb 27, 2007 5:36 pm ]
Post subject:  Re: Ccc 2007!
I took Senior. Haven't programmed for such a long time so I found it pretty difficult, or at least time consuming. I really should've prepared more... >.>
Author:  JakeP [ Tue Feb 27, 2007 5:39 pm ]
Post subject:  Re: Ccc 2007!
I got S1 in about 10 minutes, S2 fairly quickly, S3 I took longer on, and ended up goofing it up (hopefully I get part marks), S4 I'm pretty sure I aced, and S5 didn't bother with (only had a half hour left)

Hoping for 45 at least.

Does anyone have the official test data?
Author:  klopyrev [ Tue Feb 27, 2007 5:39 pm ]
Post subject:  Re: Ccc 2007!
Your code is not marked. The markers only look at the output. There shouldn't be a time factor for the Junior. As for the Senior, problem 4 and 5 have a 1 minute time limit. For Senior 5, I think it is a dynamic programming problem. A state is the starting location and the number of balls left. The answer would be the answer for the state starting at 0 with K balls left. To calculate each state, you can either place that ball at the starting location or not. Thus dp[i][k] = max(dp[i+1][k],dp[i+W][k-1] + sum(i, i+W)). You should output dp[0][k] for the answer. Taking care of edge cases like k = 0 or i+W > N will make the solution work. I think that solution should work in time and get all the test cases correct. Too bad I didn't implement that exactly on the contest. I did a little less efficient way Sad

KL

PS: If anyone has a better solution or if anyone thinks my solution is wrong, feel free to reply to this post.
Author:  Naveg [ Tue Feb 27, 2007 5:39 pm ]
Post subject:  RE:Ccc 2007!
If you used Java, you should have used the Scanner class for input. It completely removes the hassle of parsing ints and such. Just use Scanner.nextInt() and it reads the next int in the file, regardless of how much whitespace is in between.
Author:  JakeP [ Tue Feb 27, 2007 5:46 pm ]
Post subject:  Re: Ccc 2007!
Luckily I used C++ with the STL functions, they automatically strip spaces and newlines Cool
Author:  stde [ Tue Feb 27, 2007 6:08 pm ]
Post subject:  Re: Ccc 2007!
did u guys use linked list for s3?
Author:  klopyrev [ Tue Feb 27, 2007 6:11 pm ]
Post subject:  Re: Ccc 2007!
If anyone wants a working solution for S5, feel free to contact me.

Konstantin Lopyrev

Edit: Included is a JAVA solution. Sorry, there is no explanation for the solution.
Author:  bugzpodder [ Tue Feb 27, 2007 6:17 pm ]
Post subject:  RE:Ccc 2007!
this is all really great, but there are people writing as we speak. I know of at least one school who won't finish till 6:30pm. I urge people to stop showing off until end of the day.
Author:  bugzpodder [ Tue Feb 27, 2007 6:17 pm ]
Post subject:  RE:Ccc 2007!
and putting a complete solution for download is just totally inconsiderate
Author:  cool dude [ Tue Feb 27, 2007 6:38 pm ]
Post subject:  Re: Ccc 2007!
Freakman @ Tue Feb 27, 2007 4:40 pm wrote:
I found it pretty good. Finished S1 in ~10 minutes, S2 took a little more time purely because I was thinking about it in the wrong way. Then for the last 2 hours I worked solid on S5 and pwned it Very Happy


Freakman i did the same ones as you did. 3 and 4 i couldn't really do because i don't have data management knowledge.

If anybody has solution to 4 please post i spent all my remaining time on that question and couldn't get it. i know there is an algorithm though.

I also got a copy of junior questions and i must say they are ridiculously easy. i wish that last year when i was doing junior it was that easy.
Author:  ericfourfour [ Tue Feb 27, 2007 6:40 pm ]
Post subject:  Re: RE:Ccc 2007!
Naveg @ Tue Feb 27, 2007 5:39 pm wrote:
If you used Java, you should have used the Scanner class for input. It completely removes the hassle of parsing ints and such. Just use Scanner.nextInt() and it reads the next int in the file, regardless of how much whitespace is in between.


For the people stuck with BufferedReaders in Java 1.4 (the compiler version in RTP) you can use:
Java:
String[] s = br.readLine().strip(" ");
int[] nums = new int[s.length];
for (int i = 0; i < s.length; i++) {
    nums [i] = Integer.parseInt(s [i]);
}

I figured it out today when I was writing S1. Smile
Author:  Clayton [ Tue Feb 27, 2007 6:41 pm ]
Post subject:  Re: Ccc 2007!
The Junior problemset was retarded.... I mean for J2 that was ridiculous (take smilies and output what they mean, along with a couple of abbreviations). Makes me wish I had've written the junior competition Razz
Author:  klopyrev [ Tue Feb 27, 2007 6:48 pm ]
Post subject:  Re: Ccc 2007!
Here are even better solutions for S4 and S5. Interesting how they are both dynamic programming.

Konstantin Lopyrev
Author:  ericfourfour [ Tue Feb 27, 2007 6:50 pm ]
Post subject:  RE:Ccc 2007!
The third one was my favourite. It is really hard to explain so when I get my code I can show it. I was (silently) cheering to myself when I got it.

Cool dude, for S4 I planned on mapping each marker and doing a depth first search starting at 1 and whenever I hit the last marker, I would add 1 to the counter. I didn't get around to coding it because I didn't have enough time.

For S5, I briefly read over it but didn't really do anything.
Author:  cool dude [ Tue Feb 27, 2007 6:52 pm ]
Post subject:  Re: Ccc 2007!
Freakman @ Tue Feb 27, 2007 6:41 pm wrote:
The Junior problemset was retarded.... I mean for J2 that was ridiculous (take smilies and output what they mean, along with a couple of abbreviations). Makes me wish I had've written the junior competition Razz


i wonder what was more retarded j1 or j2. find the middle number. anyone can program it! how much harder was intermediate last year where we had to make othello.
Author:  cool dude [ Tue Feb 27, 2007 6:55 pm ]
Post subject:  Re: Ccc 2007!
klopyrev can you please explain the algorithm of question 4. i do not understand your code.
Author:  klopyrev [ Tue Feb 27, 2007 6:59 pm ]
Post subject:  Re: Ccc 2007!
In that problem, I am using a technique called memoization. Basically, if you have a graph like this:

1
2 3
4

1 is connected to 2 and 3, 2 is connected to 4 and 3 is connected to 4. The number of ways to reach 4 is basically the sum of the number of ways to reach 2 and 3. In this example, the number of ways to reach 2 is 1 way. The number of ways to reach 3 is also 1 way. Thus, the number of ways to reach 4 is 2. Memoization stores calculated values so they don't have to be recalculated again. Because there are no cycles, this algorithm works.

KL
Author:  cool dude [ Tue Feb 27, 2007 7:03 pm ]
Post subject:  Re: Ccc 2007!
so how would it look if it was 5 instead of 4?

is this sort of like pascals triangle? i heard people saying something like that.
Author:  klopyrev [ Tue Feb 27, 2007 7:11 pm ]
Post subject:  Re: Ccc 2007!
In dynamic programming, you use the solution to subproblems to calculate the solution to the original problem. In question 4, the problem is: how many ways are there to reach a given vertex. Suppose you have a vertex N. Vertex N is connected to N-1 and N-2 and nothing else. If memo[i] is the solution to the problem - how many ways to reach a given vertex, then memo[N] = memo[N-1] + memo[N-2]. Note that this is not a general formula. It only applies to the given example. For this example, what memo[N-1] would tell you how many ways there are to reach N-1 and memo[N-2] would tell you how many ways there are to reach N-2. Thus, the number of ways to reach N would be the number of ways to reach N through N-1 + the number of ways to reach N through N-2. Here is another example: there are 50 ways to reach vertex 4 and 49 ways to reach vertex 5. It doesn't matter what the other vertexes are. All you know is that vertex 4 is connected to vertex 6 and vertex 5 is connected to vertex 6. Suppose you want to find the number of ways to reach vertex 6. Then there will be 50 paths of the form ... -> 4 -> 6 and 49 paths of the form ... -> 5 -> 6. The ... indicates that it doesn't matter. Therefore, the number of ways to reach vertex 6 is 99. If you still don't understand, feel free to ask again.

KL
Author:  LaZ3R [ Tue Feb 27, 2007 7:18 pm ]
Post subject:  Re: Ccc 2007!
Wrote it myself today as well. Did the junior competition since I haven't done this before and will probably attempt Senior for grade 12.

Questions 1-4 took me about an hour (Spent some time making sure it worked fully well, even though I'm sure some marks will be taken off for some reason Smile

Question 5... was seriously messed up and I doubt I'll even get 1 mark for what I produced in the end since it was like... barely functional at all.

The deal or no deal question was funny Razz.

Good luck to all, hopefully I get myself on the list of high scores Very Happy.
Author:  PaulButler [ Tue Feb 27, 2007 7:20 pm ]
Post subject:  RE:Ccc 2007!
I just used a recursive function for S4. It's probably not as fast as dynamic programming, but it works. Basically, I created a function that takes a point and if a child of that point is the end point, adds one to a counter. Then it adds to the counter the result of the (same) function on each child branch. The return is the final value of the counter. The only math operation needed is addition.

When I saw "hint: start from the bottom" my first though was dynamic programming, but in this case I don't think it makes a difference where you start/end from.
Author:  klopyrev [ Tue Feb 27, 2007 7:28 pm ]
Post subject:  Re: Ccc 2007!
Unless you stored some calculated values so you don't have to calculate them again, your solution should get 3/5 or 9 points. I remember that 1 of the test cases I saw had 500000000 ways and another 1000000000.

KL
Author:  klopyrev [ Tue Feb 27, 2007 7:53 pm ]
Post subject:  Re: Ccc 2007!
Wow, what a year. J5 is also dynamic programming. That J5, S4 and S5 are dynamic programming. Razz Better start practising more for stage 2 then, if I get in.
KL
Author:  Naveg [ Tue Feb 27, 2007 8:08 pm ]
Post subject:  RE:Ccc 2007!
klopyrev, weren't you supposed to output to a file, sX.out, and not the terminal?

Edit: nevermind, the website says you could have done either. My teacher didn't know that.
Author:  StixandRox [ Tue Feb 27, 2007 8:29 pm ]
Post subject:  Re: Ccc 2007!
my first year, did junoir. Was pretty easy except for J5, took like 1.5 hours and I might not have gotten it -_-
anyone have the senior questions? I wanna try those 2night Mr. Green
Author:  klopyrev [ Tue Feb 27, 2007 8:35 pm ]
Post subject:  Re: Ccc 2007!
Here is a solution to S3 if anybody wants it. I don't like my solution though. Its not very elegant. If anyone has a better one, tell me!!!
KL
Author:  xHoly-Divinity [ Tue Feb 27, 2007 8:42 pm ]
Post subject:  Re: Ccc 2007!
Did anyone else use turing for the senior one? Embarassed

How many points do u need to go to stage two. I finished 3 programs, so what r my chances?
Author:  PaulButler [ Tue Feb 27, 2007 8:46 pm ]
Post subject:  Re: Ccc 2007!
xHoly-Divinity @ Tue Feb 27, 2007 8:42 pm wrote:
Did anyone else use turing for the senior one? Embarassed

How many points do u need to go to stage two. I finished 3 programs, so what r my chances?


Were they the first 3, or others?

Considering this years was relatively easy, I would imagine the cutoff will be in the high 50s. This is probably not attainable with three questions, unless maybe they were the last three.
Author:  Reality Check [ Tue Feb 27, 2007 8:53 pm ]
Post subject:  Re: Ccc 2007!
Whats a good mark to get in junior? I found it pretty easy. I finished 4. For Senior I heard 3 is very good and 4 is awesome.
Author:  bugzpodder [ Tue Feb 27, 2007 9:13 pm ]
Post subject:  RE:Ccc 2007!
A friend of mine finished senior in one hour and got perfect. piece of cake?
Author:  Clayton [ Tue Feb 27, 2007 9:21 pm ]
Post subject:  RE:Ccc 2007!
Your friend sir, is a geek, no question about it Razz
Author:  StixandRox [ Tue Feb 27, 2007 9:24 pm ]
Post subject:  Re: Ccc 2007!
1 hour!? Thats crazy Shocked
edit

Someone was nice enough to send them, thanks!

edit
if someone wants the Junior let me know and ill scan em
Author:  PaulButler [ Tue Feb 27, 2007 9:39 pm ]
Post subject:  RE:Ccc 2007!
One hour? That's hard to believe. Even if I could do them in an hour, I would probably stick around for another hour at least to make up some test data.
Author:  StixandRox [ Tue Feb 27, 2007 9:41 pm ]
Post subject:  Re: RE:Ccc 2007!
PaulButler @ Tue Feb 27, 2007 9:39 pm wrote:
One hour? That's hard to believe. Even if I could do them in an hour, I would probably stick around for another hour at least to make up some test data.


well if you have the skills to do them in an hour, the problems were probably nothing more then put statements to him/her (although I would still test them myself..)
Author:  klopyrev [ Tue Feb 27, 2007 9:55 pm ]
Post subject:  Re: Ccc 2007!
Joy! I have received a reply from Troy Vasiga of UofW concerning the test data. It has been reformatted and is available for download by the teachers.

KL
Author:  StixandRox [ Tue Feb 27, 2007 10:00 pm ]
Post subject:  Re: Ccc 2007!
klopyrev @ Tue Feb 27, 2007 9:55 pm wrote:
Joy! I have received a reply from Troy Vasiga of UofW concerning the test data. It has been reformatted and is available for download by the teachers.

KL


Ill let my teacher know. Were they emailed or can they just sign in the site somewere? Just so I don't go "Yeah you can dl better test data. Where you say? No idea"
Author:  bugzpodder [ Tue Feb 27, 2007 10:09 pm ]
Post subject:  RE:Ccc 2007!
why do you have access to your teachers email account is the question i would like to know
Author:  klopyrev [ Tue Feb 27, 2007 10:11 pm ]
Post subject:  Re: Ccc 2007!
I don't have access to my teacher's email account. I just emailed the guy using my own email address. He told me the new test data is available for download by the teachers.

KL
Author:  StixandRox [ Tue Feb 27, 2007 10:12 pm ]
Post subject:  Re: RE:Ccc 2007!
bugzpodder @ Tue Feb 27, 2007 10:09 pm wrote:
why do you have access to your teachers email account is the question i would like to know


Where did I say I had access? I simply asked if they were emailed or did they have to get it another way. If they were emailed then I don't need to inform him of properly formated data. We have seniors who wrote the contest in java, I read that was a problem and could have lost them marks.

Edit
Unless of course you mean the other guy lol
Author:  StixandRox [ Tue Feb 27, 2007 11:29 pm ]
Post subject:  Re: Ccc 2007!
For S5 (others too easy in my opinion, although 3 was rough) is the width always odd? If not I guess I would just place it in between the pins and knock over two on each side...yeah that would work. It doesn't specify so I thought Id ask your opinions =/
Author:  zylum [ Tue Feb 27, 2007 11:35 pm ]
Post subject:  RE:Ccc 2007!
can anyone post the problems for the senior?
Author:  StixandRox [ Wed Feb 28, 2007 12:02 am ]
Post subject:  Re: Ccc 2007!
Anyone have some solutions in Turing or C++ for s3 or s2 (Yeah s2 was too easy thats why I want to see anothers XD). Ill post mine if someone posts theres first (incase mine sux I can upgrade ;p). s3 is the only one I think is wrong though....not good at linking (s4 was easier linking though)
Author:  zylum [ Wed Feb 28, 2007 2:08 am ]
Post subject:  RE:Ccc 2007!
klopyrev, for your s5, i get a stack overflow for n > 8000, k = w = 1... dp would be better in this case.
Author:  PaulButler [ Wed Feb 28, 2007 6:51 am ]
Post subject:  Re: Ccc 2007!
StixandRox @ Tue Feb 27, 2007 11:29 pm wrote:
For S5 (others too easy in my opinion, although 3 was rough) is the width always odd? If not I guess I would just place it in between the pins and knock over two on each side...yeah that would work. It doesn't specify so I thought Id ask your opinions =/


Why start from the center? Just go pin-by-pin and knock over the [width] number of pins following that pin. You don't have to worry about zeros at the end of the pins, just stop [pins - width] from the end.
Author:  StixandRox [ Wed Feb 28, 2007 7:14 am ]
Post subject:  Re: Ccc 2007!
PaulButler @ Wed Feb 28, 2007 6:51 am wrote:
StixandRox @ Tue Feb 27, 2007 11:29 pm wrote:
For S5 (others too easy in my opinion, although 3 was rough) is the width always odd? If not I guess I would just place it in between the pins and knock over two on each side...yeah that would work. It doesn't specify so I thought Id ask your opinions =/


Why start from the center? Just go pin-by-pin and knock over the [width] number of pins following that pin. You don't have to worry about zeros at the end of the pins, just stop [pins - width] from the end.


Wow I always do stuff like that, thanks makes better sense ^^;
Author:  klopyrev [ Wed Feb 28, 2007 8:33 am ]
Post subject:  Re: Ccc 2007!
zylum wrote:

klopyrev, for your s5, i get a stack overflow for n > 8000, k = w = 1... dp would be better in this case.

I posted another solution later that doesn't have this problem. That one uses dp.

KL
Author:  Clayton [ Wed Feb 28, 2007 2:33 pm ]
Post subject:  Re: Ccc 2007!
Enjoy Very Happy
NOTE: All input comes from a file "sX.in" where X is the problem number and output is either to the screen, or a file "sX.out". Also, S4 and S5 must be finished running in <= 1 minute on a P4 machine at 3.6GHz. Good luck Very Happy

S1: Federal Voting Age

Problem Description:
For the big election on Feb. 27 2007, the government has commissioned an electronic voting system, and you have been hired as a sub-contractor for this very grand programming project.

Your task is to write the system that determines whether a given person is old enough to vote. The voting age is 18, so given someone's birthday, you must determine whether that person will be 18 years of age on the day of the election.

Input Specification:
The input will consist of a number n (1 <= n <= 100) on a single line, indicating the number of birthdays to evaluate. Then, each following n lines, will be of the form y m d, where y is the year of a potential voter's birth (0 <= y <= 2007), m (1 <= m <= 12) is the month of birth, and d (1 <= d <= 31) is the day. It is assured that each birthday is a correct and valid date.

Output Specification:
For each date in the input, output a line with either "Yes" if the voter is eligible to vote, or "No" otherwise.

Sample Input:
5
1933 10 29
1989 2 28
1961 11 23
1999 12 31
1989 2 27

Output for Sample Input:
Yes
No
Yes
No
Yes


S2: Boxes

Problem Description:
Nowadays, almost any item can be bought and sold on the internet. The problem is shipping. Before an item can be sent, it must be carefully packaged in a cardboard box to protect it.

While items come in many shapes and sizes, finding a box just the right size can be a problem. If the box is too small, the item will not fit. If the box is unnecessarily big, shipping cost will be higher, and the item is more likely to move around inside the box, and it may break.

Cardboard box manufacturers offer a fixed set of standard box sizes. Your task is to find the standard box size with the smallest volume into which an item will fit.

Each box is a rectangular prism with a given length, width, and height. Each item is also a rectangular prism with a given length, width, and height. An item may be rotated by multiples of 90 degrees in any direction before being packed into a box, but when it is packed, its faces must be parallel to the faces of the box. An item will fit into a box as long as its dimensions are equal to or less than the dimensions of the box.

Input Specification:
The first line of input will contain a single integer n, 0 < n < 1000, the number of different sizes of boxes available. The next n lines will contain a single integer m, 0 < m < 1000, the number of items to be packaged. The next m lines will contain three integers each, giving the length, width, and height of an item. All dimensions will be in millimeters and in the range from 1 mm to 2000 mm.

Output Specification:
Output is to consist of m lines, one for each item in the input. For each item, output a line containing a single integer, the volume (in mm^3) of the smallest box into which the item will fit. The same size of box may be reused for any number of items. If an item does not fit in any box, print the line: "Item does not fit."

Sample Input:
3
1 2 3
2 3 4
3 4 5
5
1 1 1
2 2 2
4 3 2
4 3 3
4 4 4

Sample Output:
6
24
24
60
Item does not fit.


S3: Friends

Problem Description:
In a certain school, it has been decided that the students are spending too much time studying and not enough time socializing. To address this situation, it has been decided to give every student a friend. Friendship is one-way. That is, if Janet is assigned to be Sarah's friend, Janet must be friendly to Sarah, but Sarah is not required to reciprocate.

The assignment of friends is done by computer using student numbers. Every student is assigned exactly one friend. Sometimes, a 'circle of friends' occurs. For example, if Marc is assigned Fred, Fred is assigned Lori, Lori is assigned Jean, and Jean assigned Marc, we have a circle of 4 friends containing Marc, Fred, Lori, and Jean. In the circle, we can say that Marc has a separation of 0 from Fred, of 1 from Lori, of 2 from Jean, and of 3 from Marc.

Your task is to identify, given the computer assignment of friends, whether the two students are in the same circle of friends, and if so, determine their separation.

Input Specification:
Input begins with a single integer n (2 <= n <= 9999), on a line by itself, indicating the number of students in the class. The next n lines contain the computer assignment of friendship. An assignment is the form x y (where 1 <= x <= n, 1 <= y <= n, x != y). For example, 1234 8765 is a possible friendship assignment indicating that student 1234 must be friends with student 8765.

Following friendship assignments, there are a series of lines containing two student numbers, separated by a single whitespace. These lines represent the pairs of students that you will determine if they are in the same circle of friends and, if so, their separation. The last line of input can be identified by the use of the 0 0 as the friend assignment.

Output Specification:
For each case, you are to print, on a seperate line, either "Yes" or "No" depending on whether they are in the same circle of friends. If the answer is "Yes", follow the output "Yes" with a single whitespace and then an integer indicating the friend's seperation.

Sample Input:
6
1 2
2 3
3 1
10 11
100 10
11 100
1 100
2 3
0 0

Output for Sample Input:
No
Yes 0


S4: Waterpark (timed)

Problem Description:
The local waterpark has a great slide complex, with many paths crisscrossing down the hill. There is one start point and one end point, but at various points one can turn and take different paths. Walter and Wanda are wondering exactly how many different ways there are to go down the slide. Can you solve their problem?

More precisely, there are n marked points (including the start at 1 and the end at n) where the paths down the hill may split or merge. All the paths move down the hill to higher numbered positions; some paths will actually cross over without meeting, but we don't have to worry about that. We won't worry about the collisions between sliders that can happen either. Out problem is simply to determine the number of different sequences of marked points we can follow down the hill.

For example, at one small waterpark, there are 4 points with direct slides from 1 to points 2 and 4; from 2 to 3 and 4; and from 3 to 4. There are 3 ways down the hill. You can check this by seeing that we can go (1, 2, 3, 4), (1, 2, 4) or (1, 4).

(Here is a hint: think about starting at the bottom of the slide.)

Input Specification:
Input begins with a single integer n (1 <= n <= 9999), on a line by itself, indicating the number of marked points. The next n lines contain point pairs of the form x y where 1 <= x < y <= n. For example, 1234 8765 indicates a direct slide from point 1234 to point 8765. The last line of input will be indicated by the point pair 0 0.

Output Specification:
The output is an integer, which is the number of different paths from piont 1 to point n. you can assume that the number of paths will be less than 2 ^ 30. It is possible that there is no path from point 1 to n, in which case the number of paths is 0.

Sample Input:
4
1 2
1 4
2 3
2 4
3 4
0 0

Output for Sample Input:
3


S5: Bowling for Numbers (timed)

Problem Description:
At the Canadian Carnival Competition (CCC), a popular game is Bowling for Numbers. A large number of bowling pins are lined up in a row. Each bowling pin has a number printed on it, which is the score obtained from knocking over that pin. The player is given a number of bowling balls; each bowling ball is wide enough to knock over a few consecutive and adjacent pins.

For example, one possible sequence of pins is: 2 8 5 1 9 6 9 3 2

If Alice was given two balls, each able to knock over three adjacent pins, the maximum score Alice could achieve would e 39, the sum of two throws: 2 + 8 + 5 = 15 and 9 + 6 + 9 = 24.

Bob has a strategy where he picks the shot that gives him the most score, then repeatedly picks the shot that gives him the most score from the remaining pins. This strategy doesn't always yield the maximum score, but it is close. On the test data, such a strategy would get a score of 20%

Input Specification:
Input consists of a series of test cases. The first line of input is t 1 <= t <= 10, indicating the number of test cases in the file. The first line of each test case contains three integers n k w. First is the integer n, 1 <= n <= 30000, indicating the number of bowling pins. The second integer k, 1 <= k <= 500, giving the number of balls available to each player. The third and final integer is w, 1 <= w <= n, the width of the bowling ball (the number of adjacent pins it can knock over.) The next n lines of each test case each contain a single non-negative integer less than 10000, giving the score of the pins, in order. 20% of the test data will have size n <= 50

Output Specification:
For each test case, output the maximum achievable score by the player. This score is guaranteed to be less than one billion.

Sample Input:
1
9 2 3
2
8
5
1
9
6
9
3
2

Output for Sample Input:
39
Author:  haskell [ Wed Feb 28, 2007 3:06 pm ]
Post subject:  RE:Ccc 2007!
I honestly don't see why it surprises that someone finished all 5 of these problems... They are very simple, and very similar to the types of problems at USACO. If you practiced there, you'd probably make a time record or something. Or at the very least, have these types of problems down.

But then again, I'm guessing this is for Highschool students? Or am I mistaken?

Anyways, those problems combined with USACO's could be a good training for the next competition.
Author:  Clayton [ Wed Feb 28, 2007 3:10 pm ]
Post subject:  Re: Ccc 2007!
Yes, this is highschool students....
Author:  Flikerator [ Wed Feb 28, 2007 3:47 pm ]
Post subject:  Re: Ccc 2007!
I finished s1, s2, and s4 in roughly 35 minutes and finished 5 at the 1:10 mark...3 took me until the 2:20 mark to finish. I just kept making so many errors. I found 3 the hardest, 5 was pretty simple.

They all work for the test data, but I managed to fumble 3 if a ring of friends has only 1 person (2 or more is fine). The way I did it was putting people in a ring of friends and then determining if each set was in any of the rings of friends. The way I did it made an error for any circle with 1 friend, I was in the middle of fixing and time ran out so Im finger crossed on that one.

5 will only work for some test data. I wanted it to work from all cases in under a minute (efficient) so I did it recursivly in a way that would never repeat the same step; which it wont, but it will only go so far down the pins (Its efficient it just won't always work. The best case would have to be in a certain range). For instance, with a width of 3 and 2 balls it would go until 10. Luckily the pins were 9 so its alright. However if the pins were 15 and the highest set was somewhere past 10 then it wouldn't work. The more balls / distance the better the chances I got it right.

1, 2, and 4 were too simple in my opinion. Although 4 looked like it was going to be tough.
Author:  PaulButler [ Wed Feb 28, 2007 4:17 pm ]
Post subject:  Re: Ccc 2007!
Flikerator @ Wed Feb 28, 2007 3:47 pm wrote:
They all work for the test data, but I managed to fumble 3 if a ring of friends has only 1 person (2 or more is fine). The way I did it was putting people in a ring of friends and then determining if each set was in any of the rings of friends. The way I did it made an error for any circle with 1 friend, I was in the middle of fixing and time ran out so Im finger crossed on that one.


A ring of friends should never only have one person. "A [friend] assignment is of the form x y (where [...] x [is not equal to] y)" therefor a circle of one friend can't exist.
Author:  Flikerator [ Wed Feb 28, 2007 4:56 pm ]
Post subject:  Re: Ccc 2007!
PaulButler @ Wed Feb 28, 2007 5:17 pm wrote:
Flikerator @ Wed Feb 28, 2007 3:47 pm wrote:
They all work for the data, but I managed to fumble 3 if a ring of friends has only 1 person (2 or more is fine). The way I did it was putting people in a ring of friends and then determining if each set was in any of the rings of friends. The way I did it made an error for any circle with 1 friend, I was in the middle of fixing and time ran out so Im finger crossed on that one.


A ring of friends should never only have one person. "A [friend] assignment is of the form x y (where [...] x [is not equal to] y)" therefor a circle of one friend can't exist.


Correction sorry, I mean a ring with only two people. When I found two people not in a ring I assigned them and looked for a match. For isntance if 2 3 havn't been placed in a circle then;

I would place them in a ring (if Im starting a new one) and then search for a new person (starting with 3). If I found one I would add that person to ring. So I found 3 6 then 6 would be added to the ring {2, 3, 6} and I would look for another starting in 6.

Anything with {n1, n2} crashed and I ran out of time before I could fix it (Small tiny error). Would be nice if I got full marks, but the competition was fun either way.
Author:  Anon [ Tue Mar 06, 2007 9:05 pm ]
Post subject:  RE:Ccc 2007!
hey, I just got my results from the CCC senior, and it turn out that there seems to be some extra whitespace in many of the input files.
I was using the java BufferedReader to read the input line by line (I was using java 1.4, so I didnt have access to the scanner class)

I was just wondering, did anyone else have this problem?

This read error cuts my score by 30 points, but if the excess whitespace is removed, most of my programs run just fine. Is it too late to do anything about this?

thanks
Author:  MihaiG [ Tue Mar 06, 2007 9:37 pm ]
Post subject:  Re: Ccc 2007!
ya, i brute forced s5 then


then i hear that one of the sample input was like 600kb file...and i was like ...oh f*ck


but i only did s1 and s5

i had 20 mins lef tos i did j1,j2,j3

meh Sad BooHoo
Author:  klopyrev [ Tue Mar 06, 2007 9:50 pm ]
Post subject:  Re: Ccc 2007!
Quote:
hey, I just got my results from the CCC senior, and it turn out that there seems to be some extra whitespace in many of the input files.
I was using the java BufferedReader to read the input line by line (I was using java 1.4, so I didnt have access to the scanner class)

I was just wondering, did anyone else have this problem?

This read error cuts my score by 30 points, but if the excess whitespace is removed, most of my programs run just fine. Is it too late to do anything about this?

thanks


My solutions had the same problem, but your teacher should have done something to correct it. First of all, there are other input files that lack this problem. Ask your teacher to download the unix files. The read error is not your fault, because BufferedReader is what they actually use in the example program on the CCC website. If your teacher still doesn't give you the marks for your problem, ask him to email the people at Waterloo and ask them. You should get the marks if your solution works with the correctly formatted files.

KL
Author:  OneOffDriveByPoster [ Tue Mar 06, 2007 10:29 pm ]
Post subject:  Re: Ccc 2007!
Hi klopyrev, looks like you got your solutions posted on the MMHS website. Congrats on solving the problems.

The version posted on the website (J5) suffers from an int overflow problem though--I gather the website operator ported it to Turing from something else? For S5, getting the sum of the next "width" balls can be done right-to-left with a little less logic.

Just looking to share ideas. I got pretty much the same thing for both (but with motel back to zero for J5 and no "supersum" for S5).
Author:  klopyrev [ Wed Mar 07, 2007 1:28 am ]
Post subject:  Re: Ccc 2007!
For J5, the int overflow must have resulted from the port to Turing from Java. As for S5, what do you mean by getting the sum can be done from right-to-left with less logic.
As I gather, calculating the sum from left to right vs right to left would make no difference. Please share your way. As for the supersum thing, I thought it would make it slightly faster, but strangely enough, it actually makes it slightly slower. Anyway, the supersum thing made the first algorithm I implemented much faster and I just didn't remove it from the new one.

KL
Author:  OneOffDriveByPoster [ Wed Mar 07, 2007 3:56 am ]
Post subject:  Re: Ccc 2007!
klopyrev @ Wed Mar 07, 2007 1:28 am wrote:
For J5, the int overflow must have resulted from the port to Turing from Java.

Okay, because the max output is too large for a 32-bit signed int. The test data doesn't seem to go there though.

Quote:
As for S5, what do you mean by getting the sum can be done from right-to-left with less logic.
As I gather, calculating the sum from left to right vs right to left would make no difference. Please share your way.

I did say it is only slight less logic (maybe you or someone else could improve on it for us):
code:

void sumw(n, w, sum, pin)
        int n, w, *sum, *pin;
{
    // w <= n
    int i = n - 1, last = 0;
    for (; i >= n - w; --i) {
        sum[i] = last = last + pin[i];
    }
    for (; i >= 0; --i) {
        sum[i] = last = last - pin[i + w] + pin[i];
    }
}


Basically, if you want the sum to be for values to the right of your index, then go from right to left and vice versa.
Author:  klopyrev [ Wed Mar 07, 2007 7:38 am ]
Post subject:  Re: Ccc 2007!
That makes sense! Cool, thanks!

KL
Author:  PaulButler [ Wed Mar 07, 2007 11:28 am ]
Post subject:  RE:Ccc 2007!
I just noticed yesterday that there was a correction to the test data for S3, I lost some points to that. My teacher seems to think that they test all the programs on their side, but I don't think this is possible due to the number of languages accepted. Does anyone know if this is the case?
Author:  Cervantes [ Wed Mar 07, 2007 2:08 pm ]
Post subject:  RE:Ccc 2007!
As I recall, testing is done at the high school. The marks are then sent to Waterloo. The university might mark the top entries, though.
Author:  Clayton [ Wed Mar 07, 2007 5:40 pm ]
Post subject:  Re: Ccc 2007!
IIRC, all of the entries that make it to Stage 2 (sorry Juniors) get marked by Waterloo to ensure no one got in by a teacher's (mis) marking.
Author:  whlue [ Thu Mar 08, 2007 10:06 pm ]
Post subject:  Re: Ccc 2007!
You know what sucks? When you mis-type information in the third question of the Junior competition. I mistyped 100000 as 1000000, and ended up having two 1000000's. Got my results back: 72/75
Author:  Omnipotence [ Sun Mar 11, 2007 6:10 pm ]
Post subject:  Re: Ccc 2007!
This year's junior got easier than last years. I actually scored perfect.
Author:  cool dude [ Wed Mar 14, 2007 9:21 pm ]
Post subject:  Re: Ccc 2007!
Omnipotence @ Sun Mar 11, 2007 6:10 pm wrote:
This year's junior got easier than last years. I actually scored perfect.


juniour this year was rediclously easy. much easier than last year where we had to program othello in the time limit given.

did anyone else get overflow errors on some of the senior programs? i guess i shouldn't have used vb. oh well.
Author:  PaulButler [ Wed Mar 14, 2007 9:32 pm ]
Post subject:  Re: Ccc 2007!
cool dude @ Wed Mar 14, 2007 9:21 pm wrote:
Omnipotence @ Sun Mar 11, 2007 6:10 pm wrote:
This year's junior got easier than last years. I actually scored perfect.


juniour this year was rediclously easy. much easier than last year where we had to program othello in the time limit given.

did anyone else get overflow errors on some of the senior programs? i guess i shouldn't have used vb. oh well.


Which questions gave you overflows? I got an overflow on S3 at first because there was a typo in the test data, but when I used the fixed data it went away.
Author:  PaulButler [ Thu Mar 15, 2007 4:45 pm ]
Post subject:  Re: Ccc 2007!
Freakman @ Wed Mar 07, 2007 5:40 pm wrote:
IIRC, all of the entries that make it to Stage 2 (sorry Juniors) get marked by Waterloo to ensure no one got in by a teacher's (mis) marking.


Actually, I just got an email from the CCC and it turns out this isn't the case. The mark your teacher gives you is final.
Author:  McKenzie [ Fri Mar 16, 2007 8:26 am ]
Post subject:  Re: Ccc 2007!
No, I think Freakman is right. Juniors under 55 and seniors under 40 get whatever the teacher marked them. At 55/40 and up all of the actual code get sent to Waterloo. I've seen marks change once it goes to Waterloo so they must re-mark them. For Example: Last year was the first year that Senior was supposed to read from file and print to screen. One student assumed that it was supposed to output to file. I e-mailed Troy, the CCC co-ordinator, he told me to apply a 5 mark penalty for the mistake. The official score Waterloo gave him did not have the 5 mark penalty on it.
Author:  PaulButler [ Fri Mar 16, 2007 11:07 am ]
Post subject:  RE:Ccc 2007!
Hmm, thats odd that the score was changed, I don't see how they could do this since they allow any language supported by the school.

I mis-read Freakman's post as saying that every submission is re-done. It would make sense for them to test the top 20 only.

That said, this was my first CCC so I can only go by what I have heard and the email from Troy. If you have experience with how the marking works there is a good chance you are right.
Author:  aramadia [ Sat Mar 17, 2007 10:33 am ]
Post subject:  Re: Ccc 2007!
For those who enjoy contests like the CCC, I hope you get into Stage II and perhaps the IOI. If you think you are extremely good and want to take this to the "next level" , you can actually money of this (besides the measly $100 for winning at a regional level in the CCC). Please visit http://www.topcoder.com/, a contest websites for professionals who are simply insanely good at programming contests. I believe the winner last year got $100,000 for winning the top coder finals.

Also, if you go to university, there is an ACM-ICPC contest, which is similar to IOI except it is designed for university students. For those who are looking for immediate practise, please visit http://acm.uva.es/problemset/ which is an online judge. An online judge automatically marks your program so your output has to be exact.
Author:  StepStep [ Wed Mar 28, 2007 6:14 pm ]
Post subject:  Re: Ccc 2007!
Anyways
Anyone got perfect on senior?
+anyone here went to stage 2 last year?
Author:  A.J [ Sun Jan 20, 2008 11:58 am ]
Post subject:  Re: Ccc 2007!
I did it in approx 3-4 hrs (number three took me some time)
number 4 and 5 were just trivial DP questions.

the 2008 CCC will definitely be harder that last year's (according to Andy Kong)

good luck to evryone!!!

(P.S): the link below is the solution to Q5 in turing. if anyone has any questions, just ask me)
Author:  A.J [ Sun Jan 20, 2008 12:00 pm ]
Post subject:  Re: Ccc 2007!
here is an updated version to the above Q5 (i took out all the streams)
Author:  klopyrev [ Fri Feb 01, 2008 4:45 pm ]
Post subject:  Re: Ccc 2007!
Have you been to http://access.mmhs.ca/ccc/? Now solve Bowling for Numbers 2... It's way more fun, but still pretty easy.
Author:  A.J [ Fri Feb 01, 2008 5:02 pm ]
Post subject:  Re: Ccc 2007!
i've read the question, and it is sort of puzzling. I still don't know how to solve it (i have other problems to think about, like the n-puzzle solver. if you can help me out with that, i'll be grateful)
Author:  klopyrev [ Fri Feb 01, 2008 6:13 pm ]
Post subject:  Re: Ccc 2007!
The state for the Bowling for Numbers 2 problem is the same as for Bowling for Numbers. However, the transition is different. If you need more of a hint, I'd be happy to give you one.
Author:  A.J [ Fri Feb 01, 2008 7:05 pm ]
Post subject:  Re: Ccc 2007!
trANsition?
of what sort?
Author:  klopyrev [ Sat Feb 02, 2008 1:05 am ]
Post subject:  Re: Ccc 2007!
You have two DP states. How they relate to each other, that is called the transition. For example, consider Bowling for Numbers:

F(i,j) = sum(i, N-1) i>=N-W
= max( F(i+W,j-1) + sum(i, i+W-1), F(i+1, j) ) i<N-W

i - current pin you are considering
j - Number of bowling balls left
W - How many pins a bowling ball knocks down
N - Total number of pins

When i<N-W, you see that F is a recursive function. F(i+W, j-1) is the next state. So is F(i+1, j).

Bowling for Numbers II has a different transition. It is more complicated. However, the states are the same.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy