### Algorithm: How do i solve this in a faster and more accurate way?

Here is the question:

If we did not have the constraint k, we could solve this problem using a greedy approach,
 ``123456`` ``````while c < N i = c while price[day i] > price[day i+1] increment i j = i+1 while price[day j] < price[day j+1] increment j add price[day j] - price[day i] to our profit c = j+1 ``````

But we cant use it here because whether to visit on a particular day or not depends on how many days we visited. Here is what i had tried

 ``123456`` `````` /* Store all the pairs generated in the previous algorithm in a linked list L, each element has two attributes buy,sell*/ while length of L > k/2 find an element i in the list such the (L[i].sell- L[i-1].buy) - (L[i-1].buy - L[i-1].sell) - (L[i].buy - L[i].sell) is maximized. Then set L[i-1].sell to L[i].sell and delete i from the list ``````

This is a problem on an online judge and when i submitted it I got time limit exceeded for some of the test cases and wrong answer for some and correct for just one test case.
What is wrong in my method, and how can it be slow because even if it takes about O(NK) time where N and K < 400.
How can i improve my algorithm to solve the problem correctly?
Last edited on
I love this kind of stuff. Super fun.

This reminds me of an approach I took to a compression algorithm a long time ago. I would approach it like this:

Ignoring the 'K' restriction for now...

At any given day, Ramu has 2 choices:
1) he can do nothing
or
2) he can trade (sell if he has a buffalo, or buy if he doesn't)

With that in mind, you can form several "chains" which represent different paths Ramu could take. To speed up the search, after each day you can go through and eliminate all chains except for 2. You only need to keep tabs on the two chains where Ramu has the most money (one chain with a buffalo, and one without)

It's difficult to put in psuedo-code... so let's walk through the example:

10 12 8 11 11 10 12 15 13 10

After day 1, possible outcomes for Ramu is he could have bought a buffalo (leaving him -10 rupees + buffalo), or he could have done nothing (leaving him with 0 rupees)

So there's 2 chains: 0 and -10* (* denotes Ramu has a buffalo)

After day 2, that turns into 4 chains, because each chain could decide to buy/sell or do nothing

Chains after day 2: 0, 2, -12*, -10*

0 if he did nothing both days
2 if he bought on day 1 and sold on day 2
-12* if he did nothing day 1 and bought on day 2
-10* if he bought on day 1 and did nothing on day 2

But now after seeing these chains, we can eliminate chains 0 and -12* because they are inferior paths to 2 and -10*.

after the final day, you just take the chain with the highest rupee value as the solution.

My big O notation sucks but I think that works out to something like O(4*N)

Reintroducing the 'K' restriction changes it slightly, but not much. All you'd have to do in that case is keep track of how many days Ramu took action. And when eliminating chains, you'd only eliminate a chain if another chain has more money and <= the number of action days.

EDIT:

Is this a public problem? Like could I submit a program to this online judge and see if it works?
Last edited on
thanks a lot for your solution, and you can submit the problem here http://opc.iarcs.org.in/index.php/problems/BUFFALOES but you may have to create an account.
Sweet. Got it on the first try.

http://opc.iarcs.org.in/index.php/results/12723

I don't know why those are so much fun... but they are.

EDIT: Balls... that site isn't using a C++11 compiler. Laaaaaame.
Last edited on
Even i got it accepted, i was stuck on this problem for so long, thanks again
Topic archived. No new replies allowed.