OSt's blog

By OSt, 12 years ago, In English
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?

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.


 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It seems that this post was added incorrectly, because of two reasons:
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.