Notes on the problem

Mathias, thanks for suggestion, that is reasonable and shouldn't be hard - I'll go and have a look at it.

Meanwhile I was told by someone (my-wife-s-violin-student-who-solved-here-problems-too) that for some problems there could be reason to have notes (perhaps, a kind of hints) which are visible even when problem is not solved yet. I thought they could be embedded into problem statement (either in ROT13 form or as an expand-on-click block) but haven't yet came to some final decision... so any thoughts about this are also welcome!

Sorry for delay, I believe it could be tested now - on the task page, when you are author, there is a "notes" button along with "view checker code". The editing form is somewhat primitive, but markdown should work.

gardengnome, this is a wonderful suggestion! I've tested it out on the Wormholes of Cygnus page, and it appears to be working correctly.

Hi Kevin, thanks for check! Actually, while programmer would test "it working", general QA will be curious to try some side-effects... for example that author can't update (or even see) some other's problems notes :)

Meanwhile I got your email couple days ago and the new problem you proposed is live now. I marked it "simple" according to your own definition though I feel it may drive one to some interesting thoughts (though I won't be surprised if Clive and Mathias for example would solve it with some O(1) formula... it should be something logarithm-based I guess). Going to test it myself bit later.

Thanks for quick proof-solving, corrected! No way it could be O(log(N)) by the way?

Thanks for uploading it Rodion! And I'm glad you enjoyed it gardengnome!

As I had mentioned in the email, I'm very curious if these types of problems could be solved in faster than O(n) time with some clever method, or if their structure restricts them to O(n)... I couldn't find any more shortcuts in this example, but others here with better dp-fu have surprised me before :)

Also I did notice one possible 'bug' in the 'notes' feature... If I have entered some notes but have not actually solved the problem myself, then I still get the "You should solve the problem to see these hints!" message. I can still see the properly formatted text on the notes editor page so it's not causing any hassle or anything, just not sure if that was the intended behavior.

On the closer inspection I see here is factorial involved (in denominator) which is not calculable better than in O(1) (even ignoring precision issues). So while there could be some nice approximations probably exact value requires a loop which is actually slightly worse than O(N) because to prevent precision loss we need to use numbers quickly growing in length.

then I still get the "You should solve the problem to see these hints!" message.

do you mean the page where we see "who solved this", please?

@Rodion: just sent you an email with a solution with O(1)-ish time, I think.

And correct, the notes aren't showing up on the who solved this page, unless I've also solved the problem.

Kevin, thanks :) let not shock people, as I understand under "solution" you mean approximation (just what I suspected in the previous message) - and interesting sidenote of your message is that I completely missed the fact the answer is a sum of harmonic series :)))

Returning to the issue with the rights to see notes on the mentioned page - thanks a lot, obviously I completely forgot to update the check here! Now should be fixed!

Thanks Rodion - the visibility on that page is now fixed!

And true, that method could not find the "exact" solution but rather "approximation accurate to X decimal places", which I suppose is enough to mostly solve the problem at least.

Also... maybe we should be a bit less public on the answer here, since this thread is visible to those who haven't solved the problem yet :)