Google Kick Start 2019 Round C Q3 Catch Some

The original question statement is here

Restating the problem

On a 1D street, Bundle’s house is at position 0. She starts off there. She wants to observe closely shy dogs of different color. Being shy means the dogs can be observed only if she is wearing the same color as the dog. N Dogs, each dog (indexed i) having color $A_i$, lives at integer positions $P_i$. It takes no time to observe a dog, 1 second to move 1 step, no time to change the color she is wearing (but she needs to be at position 0, home).

Given the task of observing k dogs, what is the fastest time at which she can complete the task?

Note that she doesn’t need to return home to declare the completion of the task.

Limits

There are at most 1000 colors in existance. The dog positions are at 1~$10^5$. For the simple case (resp. hard), there are at most 50 dogs (resp. 1000) dogs

Reflection

Clearly, the intuition is that changing colors takes time because of the need to return to the house. It will be a good idea to reduce this. The problem can be divided into sub-problems. For each T-shirt color, she performs some movement: $0\rightarrow?\rightarrow?\rightarrow?$ where ? are the dog positions. This is based on the fact that coming back to a same color is never obtimal, swapping the orders of color trajectory such that the same colored dogs are always grouped removes redundant homecoming time! So it is safe to assume that for the optimal solution: each color trajectory is the last of its kind.

Clearly for each colored trajectory, there is an optimum way to visit the dogs: greedily observe the first dog of the color in question that she sees, making a visit in increasing order of the doggy positions. Depending on whether there is a next color trajectory, she will go home or declare that she finished the task.

So it boils down to these steps:

1. choose a subset of colors that she wishes to visit
2. for each subset, select a dog that will be the last dog she visits, all dogs of the same color in between are automatically observed.
3. permutations of the colors in a way that the last color’s last dog is furthest away: we want to save the longest returning trip!

In the end, the total time will be

$2\sum(p_c,c\in C)-\max(p_c,c\in C)$,

where C are the chosen colors, $p_c$ is the position of the last dog to be visited of that color.

It is intuitive to think that the optimization can be done in two steps, first on $\sum(p_c,c\in C)$, then on the minus term.

★ In the end, this intuition was proven to be incorrect, you can jump to the counter-example, but since this is suppose to be a a blog for my train of thought, I’ll just continue along…★

So we are left with the question of choosing the appropriate set of C’s and last dogs.

Think Greedy algorithm

For this, the added time cost of shifting the choice of a last dog of a particular color (supposing that a dog for every color is at home, and we raise the number K accordingly). Is the distance to the next dog of that color. We have completely simplified the problem because now the set of chosen colors are all the colors! The problem becomes a choose-the-last-dog-for-each-color problem. Is it optimal? can a greedy last-dog shift in the present induce a deadend for good shifts? It seems possible…

Let’s consider this scenario for red,blue,green dogs:

0 denotes home
0...R.....
0....GG...
0.....BBB.

K=1: answer = time to visit 1 R
K=2: answer = time to visit 2 G
k=3: answer = time to visit 3 B

The choice of R forbids finding the solution of 2G. So Greedy doesn’t work…

Think dynamical programming/recursion

• Maybe a 2D table whose axes are: number of chosen colors and K ? This requires the chosen colors to be memorized in each entry… Ties will create expontial branching…
• Largest family is which one?… nah, that’s plain brute-force

Linear programming?

Could work!: The observation of each dog is a variable. The cost function is the incremental time to shift the role of last-dog to the next. There are implications within a color-chain of dog variables: An observed dogs imply closer dogs of the same color are all observed. That is just a bunch of $\ge$, still it is ugly… 300 variables and less than 300 inequalities. That should be very much possible. But this problem is supposed to be solved under contest time! Surely there must be a better way!

★ Linear programming can be used to solve the first return-required problem. I feel it is still true for the no return case, but we will need a few more variables… ★

Realization of wrongness of the proof

0 denotes home
0..R....R
0...G....

K = 2
return is a must, optimal: 1R and 1G = 2*(3+4)
return isn't a must, optimal: 2R = 3+5 = 8
  better than 1R and 1G = 2*3+4 = 10

Pametrizing the score

Reversing the problem sometimes helps let’s ask, for a given time limit, what is the most dogs that we can visit?

To be continued