Find Mines Facebook Hacker Cup 2013
Since the competition has ended, I would like to ask a question on this matter. I have really wrestled with this issue for the last three days because I really can't figure it out.
Here is the question: Find minus Facebook Hacker Cup 2013
Here's the site where I found a solution for this: Solutions
What I can't figure out is the next part:
While these first K values ββcould be anything, we can make some useful observations about the contents of the array after the initial K elements:
- Each element will be between 0 and K (inclusive) like a pigeon.
- Therefore, each window of K + 1 consecutive elements will contain each value between 0 and K exactly once (i.e. contains a permutation of integers from 0 to K).
- Therefore, for i> 2K: M [i] = M [i - (K + 1)].
Although I can understand the second and third points if the first is correct. The first one really worries me. Why must the elements be between 0 and K, why can't they all be the minimum non-negative integer that is missing from the initial K.
For example: For the following test case:
1
46 18
7 11 9 46
First K elements:
[7, 40, 35, 26, 19, 34, 15, 36, 37, 2, 31, 28, 41, 0, 9, 16, 1, 20]
Now why should the rest of the elements be between 0 and 18 when I have elements that are older than 18 in my previous K elements.
source to share
Imagine you have K numbers {a0,a1,a2...a(k-1)}
, now you want to find the first non-negative number that does not belong to them. Could there be more K
? Well, if that is the case, then all the numbers {0,1,...K}
are present in the above set, and the number K+1
must be present in the above set of numbers K
. It is impossible and judging a contradiction with the assumption that the new number is greater than K
. Thus, at each step, the next number added will be in the range [0,K]
and, therefore, in the step, K+1
all the last numbers K+1
will be in this step and, therefore, will be different numbers in this range.
source to share