weily's blog

Can anyone hack it?
By weily, history, 6 months ago, In English

In last night's contest, I didn't come up with the correct solution to problem C. I used many large integers, instead of the least common multiple. But it really worked!

264483249

Can anyone hack it?

English is not my native language; please excuse typing errors.

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by weily (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Your solution is correct. Clearly your solution never prints a solution when there is none, so the only interesting question is whether your solution ever prints $$$-1$$$ when a solution exists.

As mentioned in the editorial, there is a solution if and only if $$$\sum_{i = 1}^n \frac{1}{k_i} < 1$$$. There are only 24269653 such arrays under the constraints of the problem ($$$k_i \le 20$$$). I simply ran your program on all those arrays and found no countertest. So it seems that trying 200 values is sufficient under the constraints of this problem.

→ Reply