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?
--------
Comments (0)
