Last weekends didn’t promise anything unusual. By an old tradition I won the programming competition among the students of the Vologda State Pedagogical University.
When I came back home, I soon discovered a list of problems, sent over by the coach to be solved by the end of the week. I decided to start immediately, and about midnight I sat down to the problems.
By 4 o’clock I was done with 2 of them, and went to bed, pleased.
Next day I decided to go on with the problems, and there it started…
By some miracle in 1 day I was through with 6 problems out of 7. I didn’t expect such vim from myself. The coach was a bit shocked as well. But the evening stuck in my memory because of the problem “ Nikifor” from the Timus Online Judge.
Brute-force method was discarded at the very outset as having no prospects. Just for fun I decided to try the following:
it’s obvious that each 7th number is divisible by 7. Thus, the probability to get the result divisible by 7 by a random permutation of digits with truncation of initially incorrect variants was about 1 to 7.
As a result, I wrote a program that chooses at random which digit from this number to insert into the current position.
At first I got WA a couple of times. Introduced some changes and immediately got AC with the total time about 0.5 seconds (Java).
PS: the coach said it was silly to rely on this and I should never return to the practice of applying brute-force search to problems by means of “black art”.
And I have a question to you, as more experienced and successful participants of programming contests, what is your opinion about this approach (probability) to problem-solving, if in principle one can do without it there. Has it ever helped you? Is there any point thinking over such solutions?
When I came back home, I soon discovered a list of problems, sent over by the coach to be solved by the end of the week. I decided to start immediately, and about midnight I sat down to the problems.
By 4 o’clock I was done with 2 of them, and went to bed, pleased.
Next day I decided to go on with the problems, and there it started…
By some miracle in 1 day I was through with 6 problems out of 7. I didn’t expect such vim from myself. The coach was a bit shocked as well. But the evening stuck in my memory because of the problem “ Nikifor” from the Timus Online Judge.
Brute-force method was discarded at the very outset as having no prospects. Just for fun I decided to try the following:
it’s obvious that each 7th number is divisible by 7. Thus, the probability to get the result divisible by 7 by a random permutation of digits with truncation of initially incorrect variants was about 1 to 7.
As a result, I wrote a program that chooses at random which digit from this number to insert into the current position.
At first I got WA a couple of times. Introduced some changes and immediately got AC with the total time about 0.5 seconds (Java).
PS: the coach said it was silly to rely on this and I should never return to the practice of applying brute-force search to problems by means of “black art”.
And I have a question to you, as more experienced and successful participants of programming contests, what is your opinion about this approach (probability) to problem-solving, if in principle one can do without it there. Has it ever helped you? Is there any point thinking over such solutions?
UPD: I’ll be grateful if someone counts more accurately – how many attempts at a potentially correct answer does this program need to give the really right answer?
--------
Great thanks to Julia for help in translation my original russian text.
1) it can be seen in "Recent Actions" with russian locale switched on
2) comments for the russian post did not become comments for it's translation
Probably everything is OK and I just misunderstand something.