L19 Programming Problem Championship: Round 1 (Recursion)

[phillip1882]

the bishops problem is also trivially simple, its

x +x-2
with the exception of a 1x1 board.

place a row of bishops on one edge, the a row on the opposite edge minus the corners.

i have no idea how to program an efficient solution to the holey chessboard problem however.

[Solomon]

Next round's theme will be strings. Just giving a heads up in case anyone wanted to refresh on string algorithms during the week, contest link here. I'll post a new thread when it starts (Friday 7pm PDT) with the link and other details.

[Kirby]

Both in go and in programming, I should doubt my intuition more.

Well, two people tell me that it's just about working on better intuition. Maybe I'm wrong - maybe it doesn't matter that I rely on intuition during games and programming. I thought I did it too much.

I guess I just need to develop better intuition, and that's that.

Well, then, how to develop your intuition?

There is a popular misconception that I would like to address, and that that you only develop your intuition by relying upon it. I am not against relying upon intuion. Sometimes you take a leap into the unknown. And, as you know, I encourage people to develop seeing, not just reading. But back in my cognitive psyche class we learned that intuition is associated with knowledge. As a rule, the people with the best intuition about certain things also have the greatest knowledge about those things. And in my own life I have found that knowledge increases my intuition. One of your recent tsumego problems has a Golden Cock Stands on One Leg position, another has a double snapback. Each of those chunks of knowledge helps you to see the correct play. Intuition always runs ahead of knowledge, and increasing your knowledge lets it run further.

OC, increasing your knowledge is not the whole story either, but people tend to contrast intuition with knowledge when, in truth, they go together.

As for doubting your intuition, that's healthy, too. In fact, testing your intuition is a way to increase your knowledge. Earlier you said something about reading just one move ahead. If you mean go move (ply), I doubt it. Often you also see your opponent's reply. As you know, when doing an and/or search, to prove that an option leads to a solution, you do not have to examine other options, but you do have to examine all of the replies to it. So in go, it is more important to see your opponent's plays than your own. That way you can test your intuition and in so doing, increase your knowledge.

Agree with what you say. Also, in this case, the topic of the competition was recursion, so I might have focused too much on trying to find a recursive definition of the problem, and not enough about trying to solve the problem itself.

As soon as I read the problem, I was thinking, "OK, if I want to solve for board size N, how do I get this from board size N-1?"

I may have been to eager to use a technique, rather than really solving the problem at hand.

That being said, I'm pretty confident with the upcoming string competition - recursion and DP are weak points of mine. Though, given that I received 0 points this round, we'll see whether that confidence is founded

[Bill Spight]

while I did briefly try to find some kind of equation to solve Batmanacci, stuff like Bill's solution leaves me befuddled (never mind it would probably be less practical to implement than what everyone actually did).

This may make it clearer. (Not that it was obvious to me. It took a while to get there. Intuitively, I felt that there should be a straight line fit to the distribution of "N"s, but I had to guarantee that the maximum error was contained.)

Consider the sequence of these points:

1.5, 4.118, 6.736, 9.354, 11.972, 14.590. 17.208, 19.826, 22.444, ...

The difference between two consecutive points is Φ+1 = 2.1680... They represent the ideal positions of "N". OC, "N"s occur only at integer positions, so let's round the numbers. The first number could round either way, to 1 or 2, but that is true of our actual sequences. After rounding we get this sequence for the rest:

4, 7, 9, 12, 15, 17, 20, 22, ...

Which is the actual sequence of positions for "N".

Instead of rounding a floating point number I added 0.5 and used INT.

The proportion of "N"s is approximately 1/(Φ+1) = 0.382... Because, for positions greater than 2, all Fibonacci positions are "A"s, the proportion of "N"s in the next two positions after a Fibonacci number is 0.5. That is where the maximum deviations occur. You can already see that the fractional parts of 14.590 (after 13) and 22.444 (after 21) are near 0.5. The maximum deviations approach 0.5 in the limit as the positions approach ∞, but they remain bounded.

In a contest I probably would have just built bitstrings as necessary. Knowing that the string positions are identical after 2 meant that you could confine yourself to strings with a length of the next Fibonacci number after K. For instance, for 777 you just have to look at a string of length 987. But if I had found my solution quickly enough, I would probably have tried it without checking for the maximum deviations, just to be different.

[peti29]

This is interesting. I just found this. I'll join for round 2. Though is this a programming challenge or is it mathematics challenge?

[Solomon]

Though is this a programming challenge or is it mathematics challenge?

More programming than mathematics, but if mathematics is involved, it's usually in combinatorics or {number, graph, probability} theory at an elementary level.

[peti29]

Warmup

Hmm has anyone been able to solve
https://open.kattis.com/problems/rationalsequence2
in c#?

I keep getting a timeout limit and it's killing me...

Edit: never mind. I've had enough, cheated, googled the answer and meh, that's what I call a more mathematical than programming challenge...