Urban Planning - A Proposed New Problem
Back to General discussions forum
This is a combinatorics problem; hopefully not too difficult.
Clive, thanks a lot! At first glance it looks horribly difficult, but truly it looks like resembling some combinatorics puzzles so even I hope to try it in some time :)
Meanwhile I remember one more problem supposed by our colleague moxieman is waiting - I'm still a bit in hurry but
going to implement it soon. Sorry for delay.
CSF, this is a really neat problem. The more I pick it apart the more I discover some pretty interesting patterns, and I've boiled it down so that for strip of length N, I need to perform at most 3*N operations (excluding MODs). But when N > 10^18 it just takes too long! I think the key is figuring out some secret relationship between two well-known series... Or likely there is some very simple combinatorics concept that is completely going over my head! I'd love to share my thought process so far so that I could know if I'm on the right track or just going down an irrelevant rabbit hole, but I'm afraid that posting anything may give away too many hints. Hopefully I haven't referenced too much already...
Congrats to gardengnome and zelevin for solving this one - truly envious of your math-fu!
And @Rodion, there is no need for apologies - and no need for hurry on account of me! I had emailed you an additional BF problem proposal as well, which may seem simpler but still utilizes a new concept not required in existing problems. I'm also trying to flush out a TM problem, and also trying to formulate a regular problem based on some 3d geometry I use at work with CMM's (Contact Measuring Machines). But I hope I'm not causing overload or a sense of rush, since there's no deadline for anything to be implemented by! Feel free to take any time necessary :)
My favourite algorithm of them all: divide-and-conquer. Not giving much away, this applies to the majority of problems here.
I also learnt a few interesting things: the series has smilarities to Fibonacci numbers, and I discovered Fibbinary numbers. Not of much help here though as CSF is looking for very large elements of the series.
moxieman, hi
When setting the problem I thought of 3 different ways in which it could be solved but I'm sure that there will be more. gardengnome's suggestion of divide-and-conquer was certainly one of the three methods that I had in mind; although not the one that I actually used for the problem setter. When you do eventually find out how to reach the big numbers you will be very impressed at how rapidly you can calculate the answer. Normal Python solves the problem in 0.006 seconds. Meanwhile carry on exploring. You clearly have the right approach to problem solving in general. Eventually you will find what you need to move forward. There is one observation in this problem which it helps to have made at an early stage.
I love this problem. Took me a concerted effort of working my way through a series of at least three Aha! moments. Thanks, Clive!
Mathias: one can absolutely compute the [SPOILER] series for very large inputs by using a clever approach to [SPOILER] multiplication. Feel free to check my solution if you are curious.
I of course had a look, but I have no idea how your solution works - it's like magic to me. :) I've clearly failed to make the important observation that was mentioned, but the trusty divide-and-conquer came to the rescue. My solutions for the recent problems 393, 389 and 365 (all by CSF) all use the same basic structure.