## Monday, September 22, 2014

### a bit of greedy: UVa 10670 - Work Reduction

Problem Statement:
UVa 10670 - Work Reduction

Summary:
We want to transform an integer N into integer M. Then we are given 2 operations:
1. $$N \mapsto N-1$$, with cost $$A$$
2. $$N \mapsto \frac{N}{2}$$ (round down), with cost $$B$$
What is the lowest cost?

Solution:
Naturally there is a greedy scheme to follow:
1. If we can divide by 2, take $$min \{ A \lceil \frac{N}{2} \rceil, B \}$$
2. If cannot, use operation 1 for the remaining steps

Proof?

I was exploring on the maths for a bit, for the case $$N = 2^k$$ and $$2^{k-2} < M < 2^{k-1}$$, I get this results...

Suppose we do a few operation 1 ($$x$$ times) and then do operation 2. We will end up with $$2^k \mapsto 2^k-x \mapsto \lfloor \frac{2^k-x}{2} \rfloor$$. Meanwhile, if we follow greedy scheme, we have $$2^k \mapsto 2^{k-1}$$ instead.  I will call the former "deviation" from greedy scheme. Then I observe that greedy scheme actually stays ahead of the deviation. If I take $$\lfloor \frac{2^k-x}{2} \rfloor$$ as the "rendezvous" point, we have 2 costs:
By deviation: $$C' = xA + min \{ A \lceil \frac{2^k-x}{2} \rceil, B \}$$
By greedy scheme: $$C = min \{ 2^{k-1}A, B \} + x'A$$  where $$2^{k-1}-x' = \lfloor \frac{2^k-x}{2} \rfloor$$
Now, if $$x$$ even, we have $$x' = \frac{x}{2}$$, while when $$x$$ is odd, we have $$x' = \frac{x+1}{2}$$. Hence we can say $$x' \geq \frac{x}{2}$$, and also $$x \geq x'$$ for all $$x \geq 1$$.
We have to check the following cases:

Case 1: if $$A \lceil \frac{2^k-x}{2} \rceil > B$$ and $$2^{k-1}A > B$$
Then $$C' = xA + B \geq x'A + B = C$$. Hence greedy scheme is at least equal, and at best cost less than the deviation.

Case 2: if $$A \lceil \frac{2^k-x}{2} \rceil < B$$ and $$2^{k-1}A > B$$
$$C' = xA + \lceil \frac{2^k-x}{2} \rceil A = xA + (2^k - x - 2^{k-1}+x')A$$
$$C' = x'A + A2^{k-1} > x'A + B = C$$ again!

Case 3: if $$A \lceil \frac{2^k-x}{2} \rceil > B$$ and $$2^{k-1}A < B$$
This is impossible by the love of God

Case 4: if$$A \lceil \frac{2^k-x}{2} \rceil < B$$ and $$2^{k-1}A < B$$
then C = C' by simple algebra.

Yay then I can say that the greedy scheme actually stays ahead once there is a deviation from the scheme as we can always reach the state at at worst equal cost to the one resulting from the deviation :D

But for the case in general.. no idea yet

Now.. that's why people always ponder upon the paradox of why such a simple greedy algorithm can actually be so complicated.. A facade of all facades