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.

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.

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.

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.

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.

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.

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.

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

Except for the first two letters, the rest of the letters are fixed, as this lineup illustrates.

N
A
NA
ANA
NAANA
ANANAANA
NAANAANANAANA

If you are looking for the Kth letter, as long as K > 2 it is arithmetically computable from K alone. OC, if K < 3 then which letter it is depends upon the parity of N.

Let Φ be the Golden Ratio = (1 + sqrt(5))/2 = 1.618...

If K > 2 AND K = int((Φ+1)*int(K/(Φ+1))) + 2
Then the Kth letter is "N"
Else the Kth letter is "A"



If K = 7, then (Φ+1)*int(K/(Φ+1)) + 2 = 7.236... and the Kth letter is "N".
If K = 777, then (Φ+1)*int(K/(Φ+1)) + 2 = 776.938... and the Kth letter is "A".
If K = 777777, then (Φ+1)*int(K/(Φ+1)) + 2 = 777778.009... and the Kth letter is "A".

I failed to make any observation about the properties of the board, noting that N=1 should be a single bishop, and for N>1, I could take a board solution for N-1, and check every open spot for placing new pieces.

Obviously that takes a lot of time and memory, though, it appears to "work".

Checking here: http://mathworld.wolfram.com/BishopsProblem.html

I see that the answer is just 2n-2 for N>1. Had I thought a bit more, maybe programming this would have been trivial.

It helps to be lucky! As I said in my writeup, I thought I could just place bishops on all the squares of two adjacent sides. Obviously in retrospect you end up with lots of mutually attacking pairs. Luckily for me you can rearrange them and the solution remains the same. I didn't realize until I followed your link that my proposed arrangement was completely invalid.

Reducing a problem to a smaller one is often a good strategy, but you'd also have to prove (to your own satisfaction at least) that an optimal bishop arrangement for board N necessarily includes an N-1 board solution on a subboard. This isn't entirely obvious to me in this case, and it does not hold for the obvious arrangement of bishops (two almost filled rows, one at the bottom and one at the top column).