Hi community,
I've been thinking about some problem for a while, and was wondering if it has a polynomial time solution. The problem goes as follows:
You character starts with B blue tickets and R red tickets. There are N offers proposed to you, the i'th in which you first lose ai blue tickets, bi red tickets, and then right afterwards gain ci blue tickets and di red tickets (Suppose all values except N are ≤ 109). You lose if you ever have a negative amount of either ticket type. Is it possible to complete all offers and not lose?
Obviously you first want to complete all offers that yield positive profit for both red and blue tickets, but even then there might be some offers you can't complete. The rest is not so trivial.
Does anyone have ideas or seen this problem before? As said, this is original, so I don't have a problem link and am simply looking for the best time complexity possible.
What about greedily choosing offers?
Lets divide the offers by 4 types: 1. Both tickets are gained. 2. Looses Blue 3. Looses Red 4. Loosed Both.
Now, lets start with B and R tickets and choosing from category 1: Select any offer which looses less amount than current hold. If none exist, than we are done here.
Next, process 2 and 3 simultaneously, maybe a Topological Sort or DP can help. I need some time to figure this out. I will let you know if I ever reach here.
For category four, we can choice them in any order. If any fails, we are done there.
It's NP-complete, you can embed a subset-sum problem in it. Say you start with 0 blue and X red, and there are following offers, listed as ai, bi, ci, di:
X 0 10^9 10^9
10^8 10^8 0 0
0 c_1 c_1 0
0 c_2 c_2 0
...
0 c_k c_k 0
You need to find a subset of all c_i that sums up to exactly X.
Ok, I see, thanks :)
1D version looks solvable.