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?
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
̶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.
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.
Yeah this example breaks my code.
Thank you.
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.
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.
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%.