AshrafSustS19's blog

Weak test case for problem 1771C (Problem no C of last round)
By AshrafSustS19, history, 23 months ago, In English

I wasn't happy with the time complexity of my solution. So, I was looking for a solution with improved time complexity. And I found this. This guy solved this problem by only checking the first 200 elements after each index and comparing GCD of each pair . He won with the power of probability!

His submission: 184781213

Test Case

Test Case result should be Yes. His solution prints No

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

»
23 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

What about picking $$$\min(n, 100)$$$ numbers randomly and then trying all possible pairs of them? Will it work?

How to calculate the probability of getting it right?

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

    No, would have worked during the contest, but further test cases have been added. 184857290

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It doesn't work because you can construct an array with only one pair such that $$$\gcd(a_i, a_j) = 1$$$. In that case, the probability of both $$$i, j$$$ being chosen randomly is $$$(100 \cdot 99) / (n \cdot (n-1))$$$, too low.

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Why does this work? I see it's AC and he got points for problem C

→ Reply