Throwing Easter Eggs Part 2
Back to General discussions forum
Mathias, thanks for another interesting problem; probably the best of the Easter Bunnies series so far. It was good fun thinking of a suitable way in which to structure the data.
It was good fun thinking of a suitable way in which to structure the data
honestly at first glance I feel puzzled by your code, not being able to understand whether you have used the approach Mathias intended (the algorithm one may need to know/remember - I never learnt it but seemingly it's time now) or it is some kind of innovation :) Looks impressive.
I don't know what approach Mathias had in mind and I know very few standard algorithms; so I don't know to what extent my approach compares with the intended solution. It never occurred to me to search for some algorithm to solve the problem. The fun bit is designing the algorithm in the first place.
That's what I suspected :)
I myself know regretfully miserable number of algorithms (which I feel keenly when looking at the list at cp-algorithms for example). Regretfully I don't have such "inventive" power :) Now while I've been able to peek what popular structure Mathias uses, I'm now looking for some different method I can conveniently implement to solve this without feeling myself plagiator :)
Unless I'm mistaken it is probably very popular problem with more than 2 or 3 solutions. Probably this article is listing them: Range Minimum Query - you may check whether any of them is close to your invented way!
I didn't necessarily expect any specific algorithm (many roads and Rome and so on).
- Brute-force works! But it is slow and not very satisfying.
- As the egg throws are random, the values in individual cells don't get very big, and this could be exploited to speed things up.
- Rodion mentioned Range Minimum Queries.
- Last but not least, I would like to mention Segment Trees. It is good to understand the basic idea behind them.
Hi Rodion, the saga continues, i.e you have mail ... we are moving away from eggs (temporarily).
Mathias, Hi! That's great, thanks! Sehr wunderbar! I see the mail, shall dive into it immediately :)
UPD: it was fast! Thanks for code, the problem is live now!
Thanks for the speedy release. And I can see that a discussion among solvers is going on ...
Well, some people are particularly particular about coloring them, my wife is one of those :) Thanks a lot, the puzzle is live! Initially I thought there may be use in some more detailed explanations (e.g. that, seemingly, Bunnies do not like any subsequence of blue eggs "framed" below red ones - not solitary blue egg, right?) - on the other hand deducing this from example and perhaps test submission may be part of the problem. Brevity is mother of Clarity! :)
That must be some form of record - thanks for the super speedy release. And yes, working out what sequences are okay is part of the puzzle. The examples provide some hints.
Ah, it would be faster unless I for inexplicable reason tagged it with #python2 initially and started fixing incompatibilities :)))
By the way, I thought it may be convenient to you, and just made some minor addition:
the button summon admin below - if you click it, you'll see from now it allows to provide some text message along with
notification. e.g. happy 7 july or bunnies are watching you etc.
This can help against cases when you write "check mailbox" in forum and then some people add some other comments :)