Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Titandrake]

Just started today. Anybody here registered for it?

[dnkywin]

Me! I'm dnkywin on the code jam as well.

[rrenaud]

I wrote this problem for Code Jam 2008.

https://code.google.com/codejam/contest/32008/dashboard#s=p2&a=2

[theory]

I wrote this problem for Code Jam 2008.

https://code.google.com/codejam/contest/32008/dashboard#s=p2&a=2

That looks way scarier than even the TopCoder Level Threes.  Care to walk us through how to solve it?

[rrenaud]

It's not really scary at all.

I thought it was cool because so many programming contest problems are dynamic programming problems, and my intended solution isn't really DP.  But alas, there is a simple DP solution ;(.

There are plenty of solutions online.  This one is simple/good.

http://chrk.atwebpages.com/index.php?title=Test_Passing_Probability

My intended solution is basically finding the top M shortest paths in a very structured/restricted graph induced by the test questions.  Anytime you pick a particular response for a question, you pay a cost that is proportional to the log of the probability of it being right.  And then the cost of a set of responses(=path) is the sum of the individual costs.  The independence assumptions means that all the good response sets are very related so you can explore only the best ones without suffering from the exponential explosion of brute force.

[soulnet]

I wrote several problems for Google Code Jam and the Europe-only version back when it was managed by TopCoder and I was actively writing for them. I also participated in the first couple of versions, currently "retired" from competing and just writing and managing ICPC regionally.

[blueblimp]

Thanks for pointing out the start of the contest. When I was still in university, I did a lot of contests, but lately I haven't done many and keep missing the starts of the good ones since I'm not following the scene anymore.

[werothegreat]

It doesn't say - which language are you supposed to code in?

[soulnet]

It doesn't say - which language are you supposed to code in?

Whichever you want. You can download the test inputs and need to upload the output, they may be generated with any means you want as long as the programs used (compiler, interpreter), if any, are freely available. You can solve them by hand, although usually it is not possible. There should be a FAQ somewhere.

[Davio]

Is it similar to project Euler? I dabbled in that one, about 50 problems solved.
I always used imperative languages like Java and C# while mathy problems may be easier with functional languages like Haskell...

[DStu]

Is it similar to project Euler? I dabbled in that one, about 50 problems solved.
I always used imperative languages like Java and C# while mathy problems may be easier with functional languages like Haskell...

I haven't see much numerics be done in Haskell, so I doubt this...

[Avin]

Thanks for mentioning this here! I participated back in 2004 but completely missed the signups and start for it ever since then. The format has gotten a lot better now that they are doing it independently from TopCoder. I was able to see this thread with about two hours to spare from the end of the qualification round, and it took me that long to try a practice problem, then do the first two qualification round problems (although had I seen the third I probably could have done that very quickly, I just didn't even read it).

Are the points cumulative? In other words am I starting with a disadvantage due to only attempting two of the problems in the qualification round?

[Davio]

So I am too late or can I still participate starting Round 1?

[Titandrake]

So I am too late or can I still participate starting Round 1?

If you didn't do the Qualifying round, then you can't participate. However, you can look at the problems.

Thanks for mentioning this here! I participated back in 2004 but completely missed the signups and start for it ever since then. The format has gotten a lot better now that they are doing it independently from TopCoder. I was able to see this thread with about two hours to spare from the end of the qualification round, and it took me that long to try a practice problem, then do the first two qualification round problems (although had I seen the third I probably could have done that very quickly, I just didn't even read it).

Are the points cumulative? In other words am I starting with a disadvantage due to only attempting two of the problems in the qualification round?

Points aren't cumulative. Only your current round score matters.

[dnkywin]

Hooray I qualified.

My program for C-large-2 failed because I didn't include square palindromes of the form Xrev(X)^2 where X is 25 digits long (for example, 1010000000000000001000000001000000000000000101^2) because my loop stopped at len<25. Once I changed the <25 to a <26 my program passed the second large case 

[theory]

It's not really scary at all.

I thought it was cool because so many programming contest problems are dynamic programming problems, and my intended solution isn't really DP.  But alas, there is a simple DP solution ;(.

There are plenty of solutions online.  This one is simple/good.

http://chrk.atwebpages.com/index.php?title=Test_Passing_Probability

My intended solution is basically finding the top M shortest paths in a very structured/restricted graph induced by the test questions.  Anytime you pick a particular response for a question, you pay a cost that is proportional to the log of the probability of it being right.  And then the cost of a set of responses(=path) is the sum of the individual costs.  The independence assumptions means that all the good response sets are very related so you can explore only the best ones without suffering from the exponential explosion of brute force.

I think the key in there was realizing that you didn't actually have to find the optimal strategy yourself in order to solve the problem.

[rrenaud]

You can modify that solution so that it can return the kth best strategy in O(Q) time (==length to print it out) by keeping around some back pointers without an asymptotic slow down in time usage, as long as k < M.  The memory usage would increase to O(M*Q) instead of O(M).

The key insight to solve it used by that answer is that a top M solution after k steps contained a top M solution after k-1 steps.  So you never need to keep around that many partial answers to get a great final answer.

[Avin]

Hooray I qualified.

My program for C-large-2 failed because I didn't include square palindromes of the form Xrev(X)^2 where X is 25 digits long (for example, 1010000000000000001000000001000000000000000101^2) because my loop stopped at len<25. Once I changed the <25 to a <26 my program passed the second large case 

I'm curious the execution time of your program and for anyone else who solved the large-2 input.

Without precalculating the fair and square numbers my program runs in 18.657 seconds, and I'm using C#.

Unfortunately I didn't actually attempt this problem during the preliminary round since as I mentioned above I didn't start it until late. I took a few hours getting it down to this running time too but I thought it would be an interesting challenge to see how fast I could get it even after I had it fast enough to solve the problem at all.

[dnkywin]

Hooray I qualified.

My program for C-large-2 failed because I didn't include square palindromes of the form Xrev(X)^2 where X is 25 digits long (for example, 1010000000000000001000000001000000000000000101^2) because my loop stopped at len<25. Once I changed the <25 to a <26 my program passed the second large case 

I'm curious the execution time of your program and for anyone else who solved the large-2 input.

Without precalculating the fair and square numbers my program runs in 18.657 seconds, and I'm using C#.

Unfortunately I didn't actually attempt this problem during the preliminary round since as I mentioned above I didn't start it until late. I took a few hours getting it down to this running time too but I thought it would be an interesting challenge to see how fast I could get it even after I had it fast enough to solve the problem at all.

My program ran in 1.013 seconds on a 2.60GHz machine (used C++, with precalculation).

Who's doing Round 1A this Saturday?

[qmech]

It's not really scary at all.

I thought it was cool because so many programming contest problems are dynamic programming problems, and my intended solution isn't really DP.  But alas, there is a simple DP solution ;(.

There are plenty of solutions online.  This one is simple/good.

http://chrk.atwebpages.com/index.php?title=Test_Passing_Probability

My intended solution is basically finding the top M shortest paths in a very structured/restricted graph induced by the test questions.  Anytime you pick a particular response for a question, you pay a cost that is proportional to the log of the probability of it being right.  And then the cost of a set of responses(=path) is the sum of the individual costs.  The independence assumptions means that all the good response sets are very related so you can explore only the best ones without suffering from the exponential explosion of brute force.

This problem is a nice example of where laziness can be useful.  In Haskell you can use the same logic as the DP solution to construct the full list of strategies ordered by effectiveness.  Taking the the top 40 elements of that list will result in the program doing pretty much exactly the same work as the DP solution, but you've separated the concerns of comparing the strategies and computing no more than you have to.

[Avin]

My program ran in 1.013 seconds on a 2.60GHz machine (used C++, with precalculation).

Okay but how long was the precalculation? The algorithm to generate the numbers is what I'm interested in.

[Drab Emordnilap]

My program for C-large-2 failed because I didn't include square palindromes

 

[blueblimp]

Hooray I qualified.

My program for C-large-2 failed because I didn't include square palindromes of the form Xrev(X)^2 where X is 25 digits long (for example, 1010000000000000001000000001000000000000000101^2) because my loop stopped at len<25. Once I changed the <25 to a <26 my program passed the second large case 

I'm curious the execution time of your program and for anyone else who solved the large-2 input.

Without precalculating the fair and square numbers my program runs in 18.657 seconds, and I'm using C#.

Unfortunately I didn't actually attempt this problem during the preliminary round since as I mentioned above I didn't start it until late. I took a few hours getting it down to this running time too but I thought it would be an interesting challenge to see how fast I could get it even after I had it fast enough to solve the problem at all.

My program ran in 1.013 seconds on a 2.60GHz machine (used C++, with precalculation).

Who's doing Round 1A this Saturday?

I'll be doing Round 1A, but in my time zone, it's Friday.

Online round 3 looks like the real killer in this format. 500 people whittled down to 25. When I was doing competitions regularly, getting top 500 would be easy, but I was never good enough to get top 25 reliably. Too bad the algorithm competition boom has mellowed a bit--used to be the on-site numbers were bigger, like 100 (Google Code Jam 2008) and 72 (TopCoder Open 2008). Still fun to participate online, but far more difficult to get a free trip.

[dnkywin]

My program ran in 1.013 seconds on a 2.60GHz machine (used C++, with precalculation).

Okay but how long was the precalculation? The algorithm to generate the numbers is what I'm interested in.

The 1.013 seconds includes the precomputation.

I'm just in the competition for the T-shirt... sadly I didn't get my T-shirt last year even though I made Round 3... 

[Titandrake]

Qualified for round 2, just. I failed one of the large test cases that I was sure I had gotten, so it was a lot closer than I was expecting.

I'm satisfied with this, since my goal was to at least tie what I did last year (qualify for round 2, then solve none of the problems.)

Edit: Okay wow, just realized why I got it wrong. Pro tip: reading the questions other people ask helps a lot.