A possible new problem Squirrels vs Acorns
Back to General discussions forum
Took a liberty of adding my own solution to Every Leaf on Every Tree.
Also, put together another nature-inspired problem. Rodion, it's in your mailbox; I would be honored by your consideration. If you do use it, can you please add a one-minute limit?
Cheers,
V.
Vladimir, Hi! Thanks for your kind proposal, moreover squirrels are popular theme for me :)))
can you please add a one-minute limit
in my understanding if problem author thinks there should be limit - then it should be :)
just give me please some time to try and add necessary extension for answer checking functionality.
Vladimir,
Thanks for another nice problem. I really don't think that the time limit was necessary here. You could easily have increased the number of acorns/squirrels by a factor of 10 (or even 100) to make any attempt at brute force extremely unlikely.
Although the actual program runs in a small fraction of a second, the time limit of 1 minute is still rather awkward (at least for some people like me). In the one minute you have to achieve the following:
Bring up a new seed
Copy the program to the CodeAbbey window (because refreshing the screen has removed it)
Copy the seed into the program
Run the program
Copy the result and paste this into CodeAbbey
Scroll down to find the submit button and click on this
My coordination isn't very good so I had to run through a number of practice attempts before I finally did this inside the minute!
Other than that, keep up the good work. Several different people are now submitting problems. Everyone has their own style which adds to the variety of different problems.
Vladimir,
You clearly kept the numbers small in order to keep the checking times below 1 second. However, you can still achieve a brute force run-time which is more than 30 times longer then that for the current problem.
Using Python 2 I increased the number of acorns/squirrels to 600000 while keeping the run-time inside 1 second. This gives 3.6 x 10^11 values to check via brute force, which would require an extremely long run-time.
On reflection, I might have been a bit hasty in saying that the time limit was not necessary. However, if there is to be one then 2 minutes seems a much better allowance. This gives time for clumsy people like me to carry out all of the required actions and certainly does not make any difference to afficionados of the brute force technique for problem solving!
Thank you for all the acorns and squirrels!
Btw, I think the 1-minute limit is fine, especially if you use one of the languages that are supported by the code running tools on CodeAbbey.
I believe reading inputs from standard input in the program is to be preferred over hardcoding them or
explicitly loading them from a file.
For this problem and using Python (for example), something like seed = int(input()) will achieve that.
The necessary steps then become:
- Copy your program
- Refresh CodeAbbey - the timer starts now
- Paste your program
- Click the Python button to run the program on the server
- Wait until your program has run and has written the result to the answer textbox
- Click the Submit button
That's essentially one paste and two button clicks after the refresh, all on the CodeAbbey site.
Hi Friends!
I tend to agree with Clive - and really most of problems with 1 minute limit secretly have 90 second
limit instead, but this time I just forgot this :)
Probably, if everyone agree, let change it to 2 minutes then - I guess it shouldn't greatly help
bruteforcing? Hm-m-m, perhaps I should try to solve (at least bruteforce) it myself...
Paste your program
Really after submission have failed once and page with problem is reloaded, I think latest solution should self-load automagically if it was sent just few minutes ago...
Perhaps additionally we can try adding url to submit solution in automated manner (e.g. retrieve input with one http request and send answer with another)... But choosing proper limit should be more friendly :)
Thanks for feedback, everyone!
The decision to pick the current value of N was indeed due to the tradeoff between making it difficult for people to brute-force the solution but making it quick enough for the code that generates the problem to fit inside 1 second limit. Clive does have a point that N can be increased further without, hopefully, bumping against the checker's limit.
Rodion: I would suggest silently changing the timeout to the value indicated above, but leaving the text (and the value of N) as it is. This would solve both goals: help with accessibility (and this is indeed something I had concerns about) but also gently suggest to the potential solvers to try and avoid O(N^2). If the folks on this thread disagree, I can suggest a higher value of N.
Mathias, Clive: thanks for solving! There might be another problem in a week or so, I expect.
Well, as Beatles song suggest I "wrote in C"
short bruteforce solution - on my very meek and cheap laptop it takes
slightly more than 1 minute. However if compiled with -O3 optimization option it takes only 10 seconds.
I think we can leave it as is - whoever is so cunning to compile to native code and turn on speed optimization - probably have idea of proper solution anyway.
But feel free to tell if you would like to increase N 3, 5 or 10 times. Corrected limit to 90.
[laugh] I did the same exercise (timed the brute force in C, which ran in just a shade over one minute), but, naturally, forgot about compiler flags.
Here's what I propose. On my machine, increasing the N to 316228 (so that N^2 just tops one hundred billion) makes the problem generator run in ~900ms. If using this value makes the server code complete in under one minute, then, Rodion, I would appreciate if you could change N: once in the code and four times in the problem description. If you do make this change, please also change the two examples in the text to:
input:
1
answer:
49929169112
input:
2147483646
answer:
50070978872
I did this! :) though of course 123456 looked more cute, but the new one is more mysterious!
I took a liberty of adding my own solution to "Squirrels vs. Acorns".
Rodion: if you check your mailbox, you will find another proposed problem. ;)