Computer Science Canada

Found Out About CCC Yesterday...
Author:  r691175002 [ Thu Feb 21, 2008 12:30 am ]
Post subject:  Found Out About CCC Yesterday...
I believe my computer science teacher mentioned that we might participate in a contest a few weeks ago, however on Tuesday he let us know that we are all registered for the CCC on the 26th. I am a competent programmer however, to be honest, I don't really think I am suited to these kinds of problems. I have been frantically practicing (At the expense of some other subjects...) and reading as much as possible but a week isn't much time to prepare. I don't necessarily want to get into stage 2, however I don't want to embarrass myself either. I am in grade 11, so I should be better prepared if we compete next year, however I am undecided on whether I should take the junior of senior contest.

I have managed to finish all 1.1 and 1.2 problems on the USACO training site with the exception of Milking Cows (Which I cannot finish within the time limit, any hints?) and an trying to force dynamic programming and graph theory into my head. I am pretty confident I could get 4-5 problems on the junior test, however I am only confident for 3/5-4/5 on the senior test. I have half days on Thursday and Friday so I will attempt a few past tests and practice more.

Any suggestions on how to prepare as fast as possible, or suggestions on which test to take? My preferred language is Java because of the standard library containers, but having practiced a bit I feel like switching to C++ because it is faster to code these kinds of problems in (And executes faster). What kind of written materials do you bring in? I am considering a calendar, rules for leap years, line intersection and some papers on dynamic programming.

Thanks
Author:  HeavenAgain [ Thu Feb 21, 2008 12:45 am ]
Post subject:  RE:Found Out About CCC Yesterday...
Quote:
What kind of written materials do you bring in? I am considering a calendar, rules for leap years,
are, you, serious? you MOST CERTAINLY do NOT need a calendar.... neither is the rules for leap years necessary, if there will be questions on these things (ad hoc), they will provide all the informations you'll need. Its a good idea to bring in reference books.... but exactly names im not sure, plus bring a copy of the api (since you are using java) on your usb

and if you really think you are not ready for it, go for junior, at least you will stand a chance of getting the top 20 there, unless you feel really confident about the senior, then go for it! no harm done, you will only gain experience, nothing to lose. (junior to senior is a big jump tho)

also you should check out the previous year's senior and junior question, to get a feel of what it is like.... and as Tony's blog suggested, time yourself 3 hours, see how far you'll get Wink best of luck!

Ps. if you get about 4 questions perfect on senior, you are most likely invited to stage 2, but I think this year will be different....
Author:  Tony [ Thu Feb 21, 2008 9:02 am ]
Post subject:  RE:Found Out About CCC Yesterday...
You could just look over the questions of both contests on the day off, and decide which one appeals best. When I was writing my Junior CCC, I finished all the questions with time to spare, so I've started writing Senior problems. Junior and Senior had an overlap of three questions (at least back then). After my teacher has marked me for two separate devisions, it was up to me to decide which mark was going to be submitted.
Author:  r691175002 [ Thu Feb 21, 2008 8:40 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
How long do your programs have to complete the test data? I practiced 2007 s1-s4, completed (including testing on their test data) in ~1.5h. S1-S3 was fine, but I didn't feel like letting my S4 run more than a few minutes on the large test cases. I used a brute force, method so I am going to read up some more on dynamic programming. I haven't tried S5 yet, I could brute force it but I know that wouldn't be a good solution.

For S4 is the correct solution to store the number of paths from each node to tile 1 by adding up the values of its parent node? As far as I understood, that would be a dynamic solution right?
I can't think of how a dynamic solution for S5 would look, it seems to me that the way I have in mind would suck up too much memory (Storing optimal position to throw the ball for each combination of already thrown balls).
I'll try S4 and S5 later tonight and see how it goes, otherwise on the test I may just brute force and take whatever marks I can get.

(Link to 2007 Senior CCC here: http://cemc.uwaterloo.ca/ccc/2007/seniorEn.pdf );
Author:  HeavenAgain [ Thu Feb 21, 2008 8:48 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
Quote:
How long do your programs have to complete the test data?
1 second normally, for Java (maybe Turing too?) probably 3 seconds time
Author:  Tony [ Thu Feb 21, 2008 9:05 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
r691175002 @ Thu Feb 21, 2008 8:40 pm wrote:
How long do your programs have to complete the test data?

5 seconds, maybe. Anything more means you are doing something horribly wrong. Typically it should be within a second.
Author:  Coding_Guy [ Sat Feb 23, 2008 8:54 am ]
Post subject:  RE:Found Out About CCC Yesterday...
Guys I also have some questions, like how lodng did it take to be able to write dynamic problems, cause i can't do them.

also can you bring your own laptop to school, because our computers at school suck.

i currently downloaded tutorial on Dynamic Programming from this website, but does anyone else also knows any good sources, where i could get them, and that won't be over complicated

thanks in advance
Author:  OneOffDriveByPoster [ Sat Feb 23, 2008 10:10 am ]
Post subject:  Re: Found Out About CCC Yesterday...
Memoization is a way to approach a problem solvable by DP:
http://compsci.ca/v3/viewtopic.php?t=9581&postdays=0&postorder=asc&start=16
Author:  Coding_Guy [ Sat Feb 23, 2008 3:51 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
thanks man, i will read this for sure, but anyone knows something with either java or C++, cause i never learned turing Question
Author:  StealthArcher [ Sat Feb 23, 2008 4:59 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
Turing is semi-verbose, it should read easily if you under stand a few things:

1. Treat most of turing as pseudo code.

2. put is our cout.

3. loops for loops end with a statement end loop/end for

4. case is our switch statement
Author:  r691175002 [ Sat Feb 23, 2008 5:07 pm ]
Post subject:  Re: RE:Found Out About CCC Yesterday...
Coding_Guy @ Sat Feb 23, 2008 8:54 am wrote:
Guys I also have some questions, like how lodng did it take to be able to write dynamic problems, cause i can't do them.
i currently downloaded tutorial on Dynamic Programming from this website, but does anyone else also knows any good sources, where i could get them, and that won't be over complicated
thanks in advance

Yeah, I had some trouble with dynamic programming too. This was the tutorial that made it click for me:
http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

Keep going if you don't get the first examples. The second example was the one that made sense for me. Analyzing how the tables in the first example were derived may help as well. Do it on paper, following their instruction to generate the tables of optimal solutions, then check your tables against theirs.

Its something you "Get" and then its fine. That being said, I am not comfortable enough to try to apply dynamic programming to something like S5 during a 3 hour contest. I will probbably end up brute forcing such a question for partial marks.
Author:  r691175002 [ Sat Feb 23, 2008 9:08 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
Unsure over double post policy here, but new question:

What are the differences between Memoization and Dynamic Programming? Is Memoization just a subset of Dynamic Programming?

My solution for problem S4 (Successfully completed all tests in well under 1s):
code:
    public static int getConnect (int n) {
                if (memory.get(n) != null) {
                        return memory.get(n);
                }
               
                int c = 0;
               
                if (con.get(n) != null) {
                        for (int i = 0; i < con.get(n).size(); i++) {
                                c += getConnect (con.get(n).get(i));
                        }
                }
               
                memory.put(n,c);
               
                return c;
        }

Recursively determines the number of paths to the first square. I know for sure that this is an example of Memoization, but is it also an example of Dynamic Programming since it uses previously solved problems to find its solution? (Paths to current nodes = The sum of paths to all previous nodes with node 1 being 1).
Author:  whlue [ Sat Feb 23, 2008 9:41 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
r691175002 @ Sat Feb 23, 2008 9:08 pm wrote:
Unsure over double post policy here, but new question:

What are the differences between Memoization and Dynamic Programming? Is Memoization just a subset of Dynamic Programming?

My solution for problem S4 (Successfully completed all tests in well under 1s):
code:
    public static int getConnect (int n) {
                if (memory.get(n) != null) {
                        return memory.get(n);
                }
               
                int c = 0;
               
                if (con.get(n) != null) {
                        for (int i = 0; i < con.get(n).size(); i++) {
                                c += getConnect (con.get(n).get(i));
                        }
                }
               
                memory.put(n,c);
               
                return c;
        }

Recursively determines the number of paths to the first square. I know for sure that this is an example of Memoization, but is it also an example of Dynamic Programming since it uses previously solved problems to find its solution? (Paths to current nodes = The sum of paths to all previous nodes with node 1 being 1).


Memoization can be considered dynamic programming because it takes advantage of a problem's overlapping problems, one of the jewels of dynamic programming. In a question like S4 for last year's Senior competition, it would work well enough to score perfectly without running out of time. However, if you can write a solution to the question top-down using recursion and memoization, you're around half-way there to solving it bottoms-up with dynamic programming iteratively.
Author:  r691175002 [ Sun Feb 24, 2008 12:02 am ]
Post subject:  Re: Found Out About CCC Yesterday...
So dynamic programming is similar to Memoization but without recursion?

For example, if I iteratively filled in the array of possible paths to Node 1 in order until it reached node N would that be dynamic programming?
Author:  whlue [ Sun Feb 24, 2008 12:20 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
r691175002 @ Sun Feb 24, 2008 12:02 am wrote:
So dynamic programming is similar to Memoization but without recursion?

For example, if I iteratively filled in the array of possible paths to Node 1 in order until it reached node N would that be dynamic programming?


Well, you can consider both as a dynamic programming method of solving the problem, because both ways sacrifices space for speed. If you can figure out the recurrence relationship of your problem, which you have, then you can easily program it recursively with memoization. If you're stuck on finding a bottom-up way, sometimes just using recursion with memoization is good enough.

I suggest taking a read at this: http://acm.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf. It has a brief section on dynamic programming (among others) that has some neat examples you can work off of.
Author:  Coding_Guy [ Mon Feb 25, 2008 8:07 am ]
Post subject:  RE:Found Out About CCC Yesterday...
Thanks guys, i'm already reading this stuff, but i gues, i'll write junior this year,

@whlue this page, you linked, for some reason isn't found
Author:  OneOffDriveByPoster [ Mon Feb 25, 2008 8:49 am ]
Post subject:  Re: RE:Found Out About CCC Yesterday...
http://acm.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf ... This site has trouble with periods.

Anyhow, with memoization the biggest problem is if your recursion does not make use of overlapping subproblems effectively. Look out if your recursion has parameters that can be derived from the other parameters--your memoization should not include those extra parameters.
Author:  r691175002 [ Tue Feb 26, 2008 12:22 am ]
Post subject:  Re: Found Out About CCC Yesterday...
Thanks for all the tips guys, I really appreciate it. I feel a lot more confident now.

The teacher did not guarantee that Java would be installed, I practiced a bit with C++ and I personally find the standard library too cumbersome, so I will be bringing an old laptop with Java 1.6 on it so I have that option. I find that structs make it easier to code quick problems, so I may alternate languages.

My copy of Programming Challenges arrived today (lol) so I will get some reading in. I will probbably do the senior unless there is a pretty major jump in difficulty. Good luck everyone!
Author:  r691175002 [ Tue Feb 26, 2008 1:50 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
Update: Took senior, Finished S1-S4. I brute forced S2 and fell back on area formula where n > 5000.
Expecting a mark of ~56. Had 50 minutes to spare for S5 but to no avail.
Author:  Nick [ Tue Feb 26, 2008 3:11 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
heh I did S1 and S2 and failed on the last three but did calculations on how to actually do them

I didn't finished them all but I will try next year and by then I should be able dto do better Smile
Author:  r691175002 [ Tue Feb 26, 2008 4:15 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
Im not going to lie, I really think that the junior was harder than the senior this year.
I didn't really look at it, but the pre/postfix operator question made no sense to me and S5/J5 were the same.

The senior test had some harder problems, but S3 was a textbook graph problem and most of the other ones were pretty traditional.
Author:  Nick [ Tue Feb 26, 2008 4:24 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
I find jounior easier J4 was hard to understand but once it clicks its easy just string manip
Author:  Bored [ Tue Feb 26, 2008 4:27 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
I never got a look at the junior competition, but all I know is S5 was extremely hard. I couldn't figure it out for the life of me. I'm definately going to try this one once I get home. The rest of it seemed pretty easy and I'm pretty sure I got all of the first four. But honetly S5, I just couldn't get in time.
Author:  CodeMonkey2000 [ Tue Feb 26, 2008 4:29 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
s1-s3 were easy, s4 was AAAAA, s5 was straight forward. My computer froze on me halfway through. I was soo pissed. VC++ on win98 sucks ass. I kept getting messages that I'm out of memory. Apparently VC++ uses 10 megs per file and we are only allowed 50 megs. We need a good computer lab. Windows 98 should be euthanized. I freaking hate it.
Author:  pistolpete [ Tue Feb 26, 2008 4:56 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
don't know if anyone else noticed, but j5 is the exact same problem as s5 this year. Apparently the only difference is in the test cases.

Anyways, i kind of bombed the juniors. The c++ compiler wouldn't work on my computer so I had to go through the entire contest without testing it. So it took me 1.5 hours to do the first four questions (the first programming language I learned, Scheme, actually used prefix notation so I was pretty comfortable with j4), took another 1.5 hours thinking about the last question which I didn't finish. When the time was up, we found a computer that would work and I ended having 3 compiler errors on my 4th solution and 2 on my 3rd, all of which were fixed in 5 seconds. But my CS teacher wasn't accepting them so now technically the only solutions I have are 1 and 2.
Author:  StealthArcher [ Tue Feb 26, 2008 5:13 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
I got 1 and 2 done effortlessly, then overwrote my number 1 file without knowing it, my 3 kept crashing for unbeknownst reasons(I still cannot figure out why...) , and then I had to rewrite my 1.
Author:  OneOffDriveByPoster [ Tue Feb 26, 2008 5:18 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
Waiting for someone to post the problem set...
Author:  StealthArcher [ Tue Feb 26, 2008 5:23 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
For number 3?


You live on pizza, friends drew yu pizza map lol.


These mean the following:

+ move any direction
- only east/west
| only north/south
* block

get from north west corner to southeast


sample input:

1
2
2
++
++

answer:
3
Author:  Coding_Guy [ Tue Feb 26, 2008 5:33 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
wow guys, i gues, it will take me a while to reack your level, i only finished first three juniors, and couldn't understand how input was comverted for the forth one, unless i could search for an algorithm online, which is called "cheating"
Author:  Clayton [ Tue Feb 26, 2008 5:53 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
I nerfed S5 good.
Author:  Reality Check [ Tue Feb 26, 2008 6:04 pm ]
Post subject:  Re: Found Out About CCC Yesterday...
aw man I did S1 and S2. I feel disappointed in myself that I didn't actually do some practice. I went in to this thing with no knowledge of any of the more complex concepts. Well, thanks to my failure I'm going to do a lot more programming on the side and not rely on the school.
Author:  StealthArcher [ Tue Feb 26, 2008 6:09 pm ]
Post subject:  Re: RE:Found Out About CCC Yesterday...
Clayton @ Tue Feb 26, 2008 4:53 pm wrote:
I nerfed S5 good.


Is that a good or bad thing?
Author:  Tony [ Mon Mar 03, 2008 3:10 pm ]
Post subject:  RE:Found Out About CCC Yesterday...
I'm returning this thread to the Contests forum.

:


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

Terms of Use | Privacy Policy