finding max catches if you can move at a certain speed while objects appear at particular timestamps?

user_1192497 0
Viewed 46

I faced this problem in an interview, I couldn't solve it in interview. I recall a similair problem that i solved during IOI though cannot recall it.

Given N houses in a line. each of M pokemon makes an appearance at a house exactly once. ex - a pokemon appears for an instant at 5th house at time = 6. another pokemon appears for an instant at 7th house at time = 1. and so on.

we start at house P, we can move at speed of X house/sec. find max number of pokemon you can catch?

All i can think of is greedy or bruteforce but bruteforce is exponential and greedy is incorrect.

algorithm c++
1 Answers

Observation: Each Pokemon disappears right after they appear, so we need to be at a house at time=x to catch the Pokemon. If we can not make it in time, we never stop there.

Solution: create a new directed graph G=(V,A) where each v_i in V represents a house h_i = house(v_i) where a Pokemon appears at time t(v_i). Create A containing arc u->v, for each such pair if t(u)+distance(house(u),house(v)) =< t(v). In other words: if it is possible to catch Pokemon at at house(v) after Pokemon at house(u), given the time constraints.

Create a root s of the DAG and create an arc s->u for u in V if distance(P, house(u)) <= t(u).

Now, for example, with a depth-first search, you can find the longest path and reconstruct the route you take in the original instance.

user_193300780
Related