L19 Programming Problem Championship: Round 1 (Recursion)

[Solomon]

Following Kirby's idea for a weekly tsumego contest, I wanted to do something similar with programming problems after it looked like there was some interest in the Google Code Jam thread.

I'll be hosting the problems on Kattis, and every week I can either have the problems set to a certain "theme" (e.g., this Friday will be recursion / DP, next week could be strings, another week on graph problems, etc.), or just pick problems at random (but at various levels of difficulty) as a fun way to get the people in the venn diagram of Go and programming (which is a rather large intersection it seems) keep their programming sharp.

On a personal note, this year's GCJ has motivated me to try and do well in competitive programming. Specifically, like how in Go I set a goal to reach 1d, I've set a goal in the competitive programming space to reach purple on Codeforces and get into Div. 1, so it'll be motivating for me to participate myself in these (and I'd be cheating myself if I put in problems I've already done before, so don't worry about that).

Anyways, I already set up the first contest here, feel free to sign up and join (the problems on Kattis are quite good on their own):
https://open.kattis.com/contests/nhx45f

Time start: 2017-04-29 02:00:00 UTC (Fri Apr 28 2017 7pm PST)
Duration: 50 hours
Problems: 7
Theme: Recursion, DP

We can use this thread to discuss solutions after a contest, keep track of the overall leaderboard, and discuss other ideas for themes and contests. Hope to code with you this Friday!

[dfan]

That was fun, thanks! I will have more detailed comments after it's over.

[Kirby]

My parents are over, and we went hiking today, but I should have time to take a look tonight. Thanks for making the time limit long enough to have good enough time to participate

[Kirby]

I don't quite get it. Do I just submit my source file? Is there a specific input filename I should read?

[Kirby]

Looks like it's stdin:
https://open.kattis.com/contests/nhx45f/help/judgements

I'll give it a shot.

[Kirby]

Nice problems

I'm having memory issues for larger inputs on the few I've tried so far. Maybe my approaches are too simplistic.

[Solomon]

Nice problems

I'm having memory issues for larger inputs on the few I've tried so far. Maybe my approaches are too simplistic.

Thanks! I hit MLE on problem C, but it was well deserved when I realized I'm dealing with input as large as 10^18. Hit TLE on B, but unfortunately it seems like it was just a language issue. When I rewrote the algorithm from Python 3 to C++, I got the AC.

[Kirby]

...but it was well deserved when I realized I'm dealing with input as large as 10^18. ...

I've really got to improve on this front. I've been practicing problems recently, and I can usually come up with an algorithm pretty quickly, but it seems I'm still pretty weak with large inputs.

I'll hide the following comments since I'm discussing some problem details.

1st Problem: Apparently easy based on what everyone else did - I must be missing an easier way to solve the problem. What I suspect may be the problem is that I maintain the board state on each recursive call (or maybe it's something else - this is just all that I could think of). This appeared to work for smaller inputs, but as soon as things got large, I immediately ran into OOM when trying to allocate an array to store everything. I tried to improve on this by using a bunch of bits to represent board state, and this resolved the OOM problems. But then I get a stack overflow for large inputs since I recur every time.

2nd Problem: Seemed similar to first, so I skipped it, suspecting I'd encounter similar problems.

3rd Problem: I just wrote up the program as the problem defined, and maintained a map of solutions I'd already done. When I came up with a new string, I added it to the map. I used a string builder to avoid many string copies. But the map was still too big to fit into memory for large input. Not using the map resulted in slow running time. Maybe there's some pattern I'm missing?

4th Problem: Didn't get a chance to read it.

5th Problem: Writing up directly how to get the sum was really straight forward and easy. But it's too slow for large input. I realized that I can probably take advantage of multiplication by the digits. But I ran out of time to work on this tonight.

I'm going to have to call it a night, and stop here for the problems this week (I'll be busy tomorrow). I realize I'm pretty weak at this, but I'll try to do better for Round 2.

[Solomon]

I'll be asleep when the contest is finished in a few hours, but when I wake up I'll post the scores. Since I'm also working on these problems and I haven't gotten around to solving all of the problems, I'll just post my thoughts at a high level of how I approached the ones I did manage to get. It would also be cool if dfan and others who got all problems correct post their thought process for solving some of the more difficult problems. Also, was 7 a bit too many problems? I'm thinking for next round to drop it to 5 problems (1 easy, 2 medium, 2 hard). Let me know what you guys think, and congrats to everyone who did get all 7 in.

[bernds]

I'll be asleep when the contest is finished in a few hours, but when I wake up I'll post the scores. Since I'm also working on these problems and I haven't gotten around to solving all of the problems, I'll just post my thoughts at a high level of how I approached the ones I did manage to get. It would also be cool if dfan and others who got all problems correct post their thought process for solving some of the more difficult problems. Also, was 7 a bit too many problems? I'm thinking for next round to drop it to 5 problems (1 easy, 2 medium, 2 hard). Let me know what you guys think, and congrats to everyone who did get all 7 in.

I think 7 problems was fine, I had fun, and also it gives more choice if something seems like too big an obstacle.

When I saw the earlier Google Code Jam discussions I already thought this could be fun but I'd apparently missed the deadline, and the later rounds of that seem to have been unreasonably short. Can we see each other's solutions somehow on the Kattis site?

Bishops: quite trivial once you think about how to arrange them. How many diagonals are there, and can we fit one on each diagonal? Google also confirms the solution immediately. Got some failures trying to deal with EOF from gets. What can I say, that doesn't come up too often...

Holey n-Queens: also not too hard. You recurse, placing new queens wherever it's valid to do so. Keep track of which row, column, and each of the two diagonals already have a queen; you don't really need a board at all unless you want to print it (and since it came up in this thread: you don't need to allocate new boards or other information, just modify a global one before a recursive call, and undo your changes afterwards). Since you know you have to place n queens you can limit the possibilities a little, on recursion depth N you place a queen only on row N. I was worried we'd have to consider symmetries, but the examples showed we didn't. On the internet you can find correct outputs for the "N 0" case to verify your algorithm.

Batmanacci: I started with this one, I thought it sounded neat. Obviously you can't store all the strings: K can be too big. There's two tricks you have to realize: once you know fibN-1 and fibN-2, then for string sN you can tell which character comes from which predecessor sequence. If K is smaller than fibN-2, then you reduce N by 2, otherwise, reduce N by 1 and K by fibN-1. The other trick is to realize that even with 64 bit numbers you'll start getting overflow, but the limit for K is chosen such that at some point you will always be in the first half of the string, and only need to reduce N by 2 until you reach a magic number (92 or so) where you can correctly compute the fib numbers.

Pebble Solitaire: another problem where I didn't see anything obvious other than to recurse. The trick is making it go fast: subdividing the problem whenever you can prove that two subparts cannot influence each other. I think you can't cross two empty spaces from any given direction, so if you can show that there's a point you can't cross from either side, you can split your search into independent parts there. Also, black&white pebbles make nice binary numbers, and you can make a big lookup table where you store results up to a certain length. I was never quite clear on the memory limit: does it only apply to malloc, can I make really big static tables? Tried some pruning as well (if there are more isolated pebbles than in the best solution we've found at any level, we can stop), but it didn't seem that helpful.

Digit Sum: I was guessing a trivial implementation would be too slow. The idea was to find a way to increment by entire blocks of 10/100/1000 whereever possible, and to do it in two stages. If you want to go to 34567, you can do it from a starting point of 30000 by doing 4x1000, 5x100, etc. If you're coming from 23456, you then need to first get to 30000, starting from the low digits and working your way up. So, one step where your additions have carries, and one where they don't. After that it's just fiddly getting all the calculations right, and remembering to use unsigned long long everywhere.

Walrus Weights: Obvious steps: read in the weights, sort them, then compact the table to merge ones of equal weight. Had some mental block trying to decide what to do next; I think more practice with these sorts of problems would make it more obvious. A recursive algorithm works but fails runtime length requirements on one of the hidden problems. Finally got the algorithms book out to look at the knapsack problem, and that got me past it. I had been thinking the whole time I needed to build up a table of solutions iteratively but it would be too big, but then I realized I don't need to store combinations, I just needed to store weights achievable by the combinations of weights 0..N, iterating over N. I guess in hindsight it was obvious to me that this would be the solution, I just tried the recursive one first because the details eluded me. Doing these problems instead of sleeping might have had something to do with it.

Buying Coke: The main problem here was thinking it was fairly trivial and not realizing I sometimes had to insert 10+1+1+1 to get an extra fiver for later. I'm actually not convinced that my solution does the right thing in all cases (how about not having enough ones and therefore having to do some 5+5 combinations where you otherwise wouldn't), but the site accepted it. I liked this one least; if there is some important approach it teaches, it went over my head.

[dfan]

General comments:

The problems were good. Pretty much all of the were of the form "There's a straightforward algorithm that is far too inefficient for the size of the actual test inputs, so you need a clever trick," except for maybe Holey N-Queens, which I pretty much brute-forced.

It's too bad that the time constraints meant that Python was often not a good choice. (They even say so in the FAQ.) I started with Python but mostly switched to C++ after I had to spend a lot of time doing stupid Python optimization tricks to get my Holey N-Queens time low enough. Doing the rest in C++ reminded me of why Python is so much more pleasant to program in.

It was really tough not getting any more detail than "wrong answer" for code that produced the wrong answer on some input. I understand the reasoning, but it can be a real pain. This is the main reason that Buying Coke took me 19 tries (yikes).

I am out of practice when it comes to these sorts of problems but I am probably dan level when it comes to algorithms and programming puzzles. So it was nice to have a subject here that I could excel at for once.

Comments on the individual problems (I'm happy to go into more detail on any of them if desired):

A. Bishops

Right away I assumed that you'd just put bishops all the way down two adjacent sides of the board, and it was easy to confirm that this produces the maximum number (imagine putting them on the west and south sides, then look at at all the NE-SW diagonals; we fill them all, so there are no more bishops to place). I made a couple of careless mistakes (forgetting about the n=1 case, not noticing that I have to leave out one corner) so it took me three tries.

B. Holey N-Queens

I couldn't think of a better way than a standard recursive solution, going column by column and picking a valid row, and that was sufficient, though I needed to put in a fair number of optimizations to get my Python solution to be fast enough.

C. Batmanacci

Clearly you are not supposed to construct the actual strings. Ah, the ith letter in the nth string comes from either the n-1th string or the n-2nd string, and it's easy to find the correct index into that string (you just may have to subtract off the length of the n-2nd string), so once you compute all the Fibonacci numbers you may need it's a straightforward recursive algorithm. I did stick with Python for this one because it handles arbitrarily long integers and it was clear that my algorithm was going to be fast enough.

D. Pebble Solitaire

There are only 2²³ possible boards, which we can index by the integer corresponding to the binary representation of the board. Then it's perfect for dynamic programming. This is the only one I got in one try.

E. Digit Sum

The brute-force solution is clearly far too slow. My first idea was to have checkpoints (say, at 10, 100, 1000...) and precompute digit sums up to that point, then do some tricky differences. Then I realized that

• It's much easier to just compute the full digit sum from 1 to a and from 1 to b, and just subtract one from the other.
• The full digit sum is actually straightforward to compute in a recursive way.

I made two helper tables:

• The digit sum from 0 to 10ⁿ for each n in 0..15
• The digit sum from 0 to n for each n in 0..9

which I used in a slightly complicated but not-too-bad recursive formula.

F. Walrus Weights

It seemed like the key must be to phrase things in terms of the 1001 possible total weights, rather than the 2¹⁰⁰⁰ combinations of individual weights. So I kept a 1001-element boolean array of whether each total weight from 0 to 1000 was achievable in any way with the first n weights, then kept updating that as I ran through n. You do also have to keep track of your best over-1000 result, but that's just one number.

G. Buying Coke

I'm still not sure why this took me 19 tries. I think I kept fixing something and breaking something else in the process. The final issue was that I had a array for number of Cokes to buy that ran from 0 to 149 instead of to 150. Whee, C++ (yeah, I know, C++ has bounds-checking, but "for speed" I was just using a raw C multidimensional array).

In the end, it really was "just" a dynamic programming problem, but the fact that I kept failing kept making me think that there was something more subtle going on. One thing that tripped me up for a while was that my dynamic programming table was only indexed by number of Cokes left to buy, number of five-value coins, and number of ten-value coins, but I didn't clear it out between problems so it could have bogus data (the number of one-value coins is implicit from the other values, but only if you know how many you had to start with).

Thanks again to Solomon for setting this up! If you're going to do this on a regular basis I would definitely suggest reducing the number of problems. You proposed 5 but I think you could even go down to 3.

[bernds]

I started with Python but mostly switched to C++ after I had to spend a lot of time doing stupid Python optimization tricks to get my Holey N-Queens time low enough. Doing the rest in C++ reminded me of why Python is so much more pleasant to program in.

Really? I did everything in C and never felt that language choice would matter much for these kinds of problems, except maybe briefly when I thought I might need more than 64 bits of precision for Batmanacci. I tend to find I'm not enjoying myself much whenever I have to use Python - what was the problem with C++?

There are only 2²³ possible boards, which we can index by the integer corresponding to the binary representation of the board. Then it's perfect for dynamic programming.

Quite. I think the strategy of starting to do problems instead of going to sleep and staying up all night caught me out here too; I think the whole time I fantasized I was under a stricter memory limit than I actually was. so I didn't even consider that even when I started building lookup tables...

G. Buying Coke
In the end, it really was "just" a dynamic programming problem, but the fact that I kept failing kept making me think that there was something more subtle going on.

I wasn't even that subtle about it. If I'd been asked to solve a more general problem with arbitrary sets of coins I'd probably have found a better solution, but somehow I ended up thinking this was a trivial one like Bishops.

Thanks again to Solomon for setting this up! If you're going to do this on a regular basis I would definitely suggest reducing the number of problems. You proposed 5 but I think you could even go down to 3.

I kind of liked the variety. It's not like one actually has to solve all of the problems since there's no prize or anything.

[quantumf]

Unfortunately I was busy this weekend, so didn't really have any time to look at this (apart from a few minutes to do the bishops problem, which didn't really require any coding). Please do it again.

[dfan]

I started with Python but mostly switched to C++ after I had to spend a lot of time doing stupid Python optimization tricks to get my Holey N-Queens time low enough. Doing the rest in C++ reminded me of why Python is so much more pleasant to program in.

Really? I did everything in C and never felt that language choice would matter much for these kinds of problems, except maybe briefly when I thought I might need more than 64 bits of precision for Batmanacci. I tend to find I'm not enjoying myself much whenever I have to use Python - what was the problem with C++?

It really is just a matter of opinion. To me Python is the closest thing to "executable pseudocode", so it offers the least resistance on the path from envisioning an algorithm to obtaining a solution. The arbitrary-length integers were certainly nice in a couple of problems. Parsing is more convenient (though that wasn't much of an issue in this set). Automatic bounds-checking would have saved me from a stupid bug in the Cokes problem. Stuff like that. If you find C more pleasant I will not try to convince you.

There are only 2²³ possible boards, which we can index by the integer corresponding to the binary representation of the board. Then it's perfect for dynamic programming.

Quite. I think the strategy of starting to do problems instead of going to sleep and staying up all night caught me out here too; I think the whole time I fantasized I was under a stricter memory limit than I actually was. so I didn't even consider that even when I started building lookup tables...

Yeah, pretty much the first question I asked myself for every problem was "How much memory can I get away with using for my lookup tables / dynamic programming?"

Thanks again to Solomon for setting this up! If you're going to do this on a regular basis I would definitely suggest reducing the number of problems. You proposed 5 but I think you could even go down to 3.

I kind of liked the variety. It's not like one actually has to solve all of the problems since there's no prize or anything.

True, but some of us have a hard time not cleaning our plate.

[ugoertz]

Thanks for setting up the contest, I also enjoyed it.

I used Python throughout, but for the walrus weights I did not manage to build a solution which ran within the acceptable time limit. (And in all test cases I set up, the run time was a lot shorter than the allowed 2 seconds, so that was a bit puzzling.) However, from the others' comments I see that my choice of algorithm was too naive.

It would be interesting to look at the solutions of the other contestants, but I suppose they are not available via the Kattis website, right?

Best regards,

Ulrich