Google Code Jam 2016 – solution to problem D: Fractiles.
This is problem to get 10 points for free.
Small part is very easy.
If S = K this means that we can use K positions to test if there is gold.
We will use all of them.
Let’s assume there is gold in 1st position of original sequence.
Then 1st position of final sequence will be gold too – this is very easy to understand.
So we choose 1.
If there is no gold at 1st position – it means that first K numbers in final sequence are the same as in original.
So small solution which wirks for all inputs:
1 2 3 4 … K
To solve large input next idea becomes a solution:
Let’s imagine some start sequence and end sequence which has complexity C=2.
How we can clean 1 tile and check if 2 origina tiles contain gold or not?
Here is image which explains which tile we need to check to verify tiles 1 and 2 in original sequence.
This easily becomes feasible idea for solution – for complexity C – each additional level allows us to check +1 original tile by cleaning corresponding tile in corresponding position.
Minimum number of tiles which are required is floor(K / C)