----------------------------------- Naveg Tue Feb 27, 2007 4:37 pm 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? ----------------------------------- Clayton Tue Feb 27, 2007 4:40 pm 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 :D ----------------------------------- klopyrev Tue Feb 27, 2007 4:52 pm 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 ----------------------------------- Clayton Tue Feb 27, 2007 4:57 pm Re: Ccc 2007! ----------------------------------- If you ask me, all the data and such was poorly handled this year.... ----------------------------------- PaulButler Tue Feb 27, 2007 5:00 pm 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. ----------------------------------- zwnage Tue Feb 27, 2007 5:21 pm 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 >.< ----------------------------------- eklypze Tue Feb 27, 2007 5:36 pm 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... >.> ----------------------------------- JakeP Tue Feb 27, 2007 5:39 pm 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? ----------------------------------- klopyrev Tue Feb 27, 2007 5:39 pm 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 :( KL PS: If anyone has a better solution or if anyone thinks my solution is wrong, feel free to reply to this post. ----------------------------------- Naveg Tue Feb 27, 2007 5:39 pm 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. ----------------------------------- JakeP Tue Feb 27, 2007 5:46 pm Re: Ccc 2007! ----------------------------------- Luckily I used C++ with the STL functions, they automatically strip spaces and newlines 8-) ----------------------------------- stde Tue Feb 27, 2007 6:08 pm Re: Ccc 2007! ----------------------------------- did u guys use linked list for s3? ----------------------------------- klopyrev Tue Feb 27, 2007 6:11 pm 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. ----------------------------------- bugzpodder Tue Feb 27, 2007 6:17 pm 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. ----------------------------------- bugzpodder Tue Feb 27, 2007 6:17 pm RE:Ccc 2007! ----------------------------------- and putting a complete solution for download is just totally inconsiderate ----------------------------------- cool dude Tue Feb 27, 2007 6:38 pm 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 :D 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. ----------------------------------- ericfourfour Tue Feb 27, 2007 6:40 pm Re: 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. For the people stuck with BufferedReaders in Java 1.4 (the compiler version in RTP) you can use: String I figured it out today when I was writing S1. :) ----------------------------------- Clayton Tue Feb 27, 2007 6:41 pm 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 :P ----------------------------------- klopyrev Tue Feb 27, 2007 6:48 pm Re: Ccc 2007! ----------------------------------- Here are even better solutions for S4 and S5. Interesting how they are both dynamic programming. Konstantin Lopyrev ----------------------------------- ericfourfour Tue Feb 27, 2007 6:50 pm 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. ----------------------------------- cool dude Tue Feb 27, 2007 6:52 pm 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 :P 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. ----------------------------------- cool dude Tue Feb 27, 2007 6:55 pm Re: Ccc 2007! ----------------------------------- klopyrev can you please explain the algorithm of question 4. i do not understand your code. ----------------------------------- klopyrev Tue Feb 27, 2007 6:59 pm 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 ----------------------------------- cool dude Tue Feb 27, 2007 7:03 pm 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. ----------------------------------- klopyrev Tue Feb 27, 2007 7:11 pm 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 ----------------------------------- LaZ3R Tue Feb 27, 2007 7:18 pm 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 :) 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 :P. Good luck to all, hopefully I get myself on the list of high scores :D. ----------------------------------- PaulButler Tue Feb 27, 2007 7:20 pm 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. ----------------------------------- klopyrev Tue Feb 27, 2007 7:28 pm 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 ----------------------------------- klopyrev Tue Feb 27, 2007 7:53 pm Re: Ccc 2007! ----------------------------------- Wow, what a year. J5 is also dynamic programming. That J5, S4 and S5 are dynamic programming. :P Better start practising more for stage 2 then, if I get in. KL ----------------------------------- Naveg Tue Feb 27, 2007 8:08 pm 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. ----------------------------------- StixandRox Tue Feb 27, 2007 8:29 pm 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 :mrgreen: ----------------------------------- klopyrev Tue Feb 27, 2007 8:35 pm 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 ----------------------------------- xHoly-Divinity Tue Feb 27, 2007 8:42 pm Re: Ccc 2007! ----------------------------------- Did anyone else use turing for the senior one? :oops: How many points do u need to go to stage two. I finished 3 programs, so what r my chances? ----------------------------------- PaulButler Tue Feb 27, 2007 8:46 pm Re: Ccc 2007! ----------------------------------- Did anyone else use turing for the senior one? :oops: 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. ----------------------------------- Reality Check Tue Feb 27, 2007 8:53 pm 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. ----------------------------------- bugzpodder Tue Feb 27, 2007 9:13 pm RE:Ccc 2007! ----------------------------------- A friend of mine finished senior in one hour and got perfect. piece of cake? ----------------------------------- Clayton Tue Feb 27, 2007 9:21 pm RE:Ccc 2007! ----------------------------------- Your friend sir, is a geek, no question about it :P ----------------------------------- StixandRox Tue Feb 27, 2007 9:24 pm Re: Ccc 2007! ----------------------------------- 1 hour!? Thats crazy :shock: edit Someone was nice enough to send them, thanks! edit if someone wants the Junior let me know and ill scan em ----------------------------------- PaulButler Tue Feb 27, 2007 9:39 pm 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. ----------------------------------- StixandRox Tue Feb 27, 2007 9:41 pm Re: 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. 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..) ----------------------------------- klopyrev Tue Feb 27, 2007 9:55 pm 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 ----------------------------------- StixandRox Tue Feb 27, 2007 10:00 pm 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 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" ----------------------------------- bugzpodder Tue Feb 27, 2007 10:09 pm RE:Ccc 2007! ----------------------------------- why do you have access to your teachers email account is the question i would like to know ----------------------------------- klopyrev Tue Feb 27, 2007 10:11 pm 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 ----------------------------------- StixandRox Tue Feb 27, 2007 10:12 pm Re: RE:Ccc 2007! ----------------------------------- 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 ----------------------------------- StixandRox Tue Feb 27, 2007 11:29 pm 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 =/ ----------------------------------- zylum Tue Feb 27, 2007 11:35 pm RE:Ccc 2007! ----------------------------------- can anyone post the problems for the senior? ----------------------------------- StixandRox Wed Feb 28, 2007 12:02 am 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) ----------------------------------- zylum Wed Feb 28, 2007 2:08 am 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. ----------------------------------- PaulButler Wed Feb 28, 2007 6:51 am 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 =/ 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. ----------------------------------- StixandRox Wed Feb 28, 2007 7:14 am 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 =/ Why start from the center? Just go pin-by-pin and knock over the Wow I always do stuff like that, thanks makes better sense ^^; ----------------------------------- klopyrev Wed Feb 28, 2007 8:33 am 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. I posted another solution later that doesn't have this problem. That one uses dp. KL ----------------------------------- Clayton Wed Feb 28, 2007 2:33 pm Re: Ccc 2007! ----------------------------------- Enjoy :D 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 =N-W = max( F(i+W,j-1) + sum(i, i+W-1), F(i+1, j) ) i