Return to Answer

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
2. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

2. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

3. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity:

solving 1. and 2. takes $ O(nlog(n)) $ (solving each exponential equations takes $ O(log(n)) $ using binary search)

solving 3. takes $ O(V+E) $ where $ V=n, E<=n^2 $

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
2. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

2. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

3. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity:

solving 1. and 2. takes $ O(n\log(n)) $ (solving each exponential equations takes $ O(\log(n)) $ using binary search)

solving 3. takes $ O(V+E) $ where $ V=n, E\le n^2 $

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
2. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

2. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

3. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity: solving 1. and 2. takes $ O(n^2) $, solving 3. takes $ O(V+E) $ where $ V=n, E<=n^2 $

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
2. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

2. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

3. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity:

solving 1. and 2. takes $ O(nlog(n)) $ (solving each exponential equations takes $ O(log(n)) $ using binary search)

solving 3. takes $ O(V+E) $ where $ V=n, E<=n^2 $

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
2. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

2. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

solving 1. takes $ O(n^2) $, and worst case of solving 2. takes $ O(n^2) $

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
2. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
3. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

2. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

3. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity: solving 1. and 2. takes $ O(n^2) $, solving 3. takes $ O(V+E) $ where $ V=n, E<=n^2 $