Clone3's blog

CR #360 Div2 E [Random-based solution]
By Clone3, history, 8 years ago, In English

Is there anyone who can prove or disprove my random-based 18809719 solution of this problem?

Short description:

visited[i] on phase j consists of all possible prefix sums that we could have met by collecting coins from left to right.

Example:

{2, 1} is a set of coins, then

visited[0..3] = {{0}, {0, 1}, {0, 2}, {0, 2, 3}}

Suppose that we are looking for value X in visited[K], if we shuffle input many times , then X is gonna be one of prefix or suffix sums on the way to K. (To consider all Suffixes, simply for every X in answer add K - X to the answer)

The question is how many times do I actually need to shuffle input so that I get all values of X with high probability?

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

If I understand the algorithm correctly, I think this case might make it perform badly and have a low probability of finding the sum 6:

28 481
1 2 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    ̶W̶e̶l̶l̶ ̶I̶ ̶c̶a̶n̶'̶t̶ ̶u̶n̶d̶e̶r̶s̶t̶a̶n̶d̶ ̶t̶h̶i̶s̶ ̶e̶x̶a̶m̶p̶l̶e̶ ̶t̶h̶a̶t̶ ̶f̶a̶s̶t̶,̶ ̶b̶u̶t̶ ̶m̶y̶ ̶s̶o̶l̶u̶t̶i̶o̶n̶ ̶s̶e̶e̶m̶s̶ ̶t̶o̶ ̶g̶e̶t̶ ̶t̶h̶i̶s̶ ̶s̶u̶m̶ ̶o̶n̶ ̶*̶*̶f̶i̶r̶s̶t̶*̶*̶ ̶i̶t̶e̶r̶a̶t̶i̶o̶n̶ ̶i̶n̶ ̶*̶*̶1̶0̶0̶%̶*̶*̶ ̶o̶f̶ ̶c̶a̶s̶e̶s̶

    Misread it a bit.

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

      Okay, I am probably misunderstanding how it works then. The idea was that in order to get a sum of 6 on the way to 481 (which is the sum of everything), the elements 1, 2, and 3 would all have to occur together at the beginning or end of the array after the shuffle.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Yeah this example breaks my code.

        Thank you.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can avoid considering all suffix sums in your proof if you wish, obviously, you can increase times of iterations twice and all possible sums will be prefixes at some point with decent probability.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have random solution too, but I have another approache. 18807562
I fix number i which I want to check and collect money for it. Then I block elements which in this number and try collect k.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The best I can do for breaking this is the following case: n = 167, k = 495, a = {165 2's and 2 165's}. Then, to find a sum of 330, the only ways to get the sum are 165+165 and 2+2+...+2, and after getting 330, a 165 is needed to end up with a sum of 495. So 330 has to be made with the 165 2's to save the 165 for later. For this to happen, the last element in the shuffled array has to be a 165, which has a 2/167 chance of happening. So the chance of succeeding after 40 trials would be 1 — (165/167)^40, or about 38.2%.

    → Reply