Found Out About CCC Yesterday...

[r691175002]

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

[HeavenAgain]

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 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....

[Tony]

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.

[r691175002]

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 );

[HeavenAgain]

Quote:

How long do your programs have to complete the test data?

1 second normally, for Java (maybe Turing too?) probably 3 seconds time

[Tony]

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.

[Coding_Guy]

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

[OneOffDriveByPoster]

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

[Coding_Guy]

thanks man, i will read this for sure, but anyone knows something with either java or C++, cause i never learned turing

[StealthArcher]

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

[r691175002]

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.

[r691175002]

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).

[whlue]

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.

[r691175002]

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?

[whlue]

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.