Railroad Rat - A possible New Problem
Back to General discussions forum
This problem introduces Roland the intelligent rat.
Thank you Clive! The puzzle is ready! As a sidenote I'm a fan of railroads!
The note that Roland likes to participate in experiments devised by Ann and Bob reminds me sarcastic suggestion by some author "and perhaps on contrary rats are just conducting tests on simple-minded scientist" (with reference to "Hitchhiker's guide to Galaxy").
I'm a big fan of Douglas Adams and the Hitchhiker's Guide to the Galaxy. I first listened to the original radio series and was lucky enough to have recorded it. I did eventually lose the recording but have since bought a commercial copy. I really like the quirky humour and the outrageous ideas.
For me it long seemed a some special book for programmers, because I only heard of it from university mates and FIDO folks. Eventually it happened my wife got upon it and after reading she suggested we may watch a movie based upon it. I was somewhat surprised the book made such impression for her, person quite remote from any technical science!
But the tale is really... outstanding, both satirical, philosophical etc. Explosion of sudden thoughts and ideas :)
Meanwhile, I wanted to say, your problem is not ignored! I recently sat upon it, saying "aha, it is some obvious DP-like thing". Well, after I wrote typical double loop I suddenly found it is counting very different things because it doesn't address duplicates. The puzzle suddenly is more puzzling! Great job :)
As a bit of encouragement, a double-loop DP can certainly be part of the solution but there needs to be an "additional" bit ...
I gave up the hope to find a way solely on my own and asked here and there for any subtle hints. One of the answers likened it to the problem of counting all possible proper subsequences of parentheses. Another said it is similar to finding all possible subsequences of characters in arbitrary string at all... Well, perhaps I'll put it together some day with your hint Mathias, thanks. However as a sidenote, these advices were given by "orange-grade" person at Codeforces, where I'm just "blue". From this I deduce the puzzle is of the kind suitable for some advanced round at some rated internation contest :)
It's a pity our colleague tzyLee still haven't introduced him/her-self...
Hi Rodion, this problem is indeed similar to one of the hints given. CSFP's evergreen recommendation - have a go with pen & paper - is exactly what I did. I used a signal like 1011 and worked out what distinct move sequences I could get for each position after using / not using each part of the signal. Look carefully and a pattern might emerge.
PS I am not sure whether my code handles all edge cases (around first and last positions) correctly.
PPS I am as blue as you.
I'm intrigued by the interest in the problem. Unfortunately, I don't think I can offer a hint without actually divulging the means by which the checker finds the solution. It might help to know that it is fast. The Python code sets and solves all parts of the problem in less than 0.001 seconds. Best of luck with your endeavours.