fushar's blog

Need Help for SPOJ FCANDY
By fushar, 14 years ago, In English
Hello all,

I have been stuck in problem FCANDY in SPOJ for months. I realized that it is an optimized DP problem, but I still cannot reduce the DP complexity.

misof and several coders explained in TC forum as below, but I cannot get it:
What I did consists of two separate steps:
First, consider a knapsack problem: You have N types of coins, the i-th type is worth C_i and you have K_i of those. Can you pay exactly X?
The naive implementation is O(X * sum of K_i). This can be improved to O(X*N) by processing an entire *type* of coins at once.
Suppose that the previous coin sets allowed you reach sum Y. Now you got a new batch containing K_i coins worth C_i each. You can now reach the sums Y, Y+C_i, ..., Y+K_i*C_i.
Now comes the trick: suppose that you could also reach the sum Y-3*C_i with the previous coin set. Then, regardless of how huge K_i is, you only need to mark Y-2*C_i and Y-C_i as reachable, you already marked the other ones when processing Y.

I just don't understand the last sentence.

People in SPOJ forum are talking about slicing the DP into orbits, which I don't understand either.

Any help will be appreciated. :)
  • Vote: I like it
  • +3
  • Vote: I do not like it

14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I wrote a code but It gets WA on test 25. I used memoization on a function f(pos, dif). f(pos, dif) means that we want to distribute calories C[pos..n] in such a way that the difference is closest to dif. And we know that dif cannot be greater than 100000 = 200*500. To compute f, I try all k[pos]/2 types of distributing the calories and try to make the difference closer with dif. Here is the code. I don't know if my approach is correct or not and I don't know why I get WA :D

int f(int pos, int dif) {
    if (pos == n) return 0;
    int &res = dp[pos][dif];
    if (res != -1) return res;
    res = 0;
    int mn = 1000000;
    int taf = k[pos]*c[pos];
    while (taf >= 0) {
        int tmp = abs(f(pos+1, abs(dif-taf))-taf);
        if (abs(tmp-dif) < mn) {
            res = tmp;
            mn = abs(tmp-dif);
        }
        taf -= 2*c[pos];
    }
    return res;
}
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

An attempt to explain the last line:

----------------------------------------------

Let, Previously reached sum is Y, then given new bag of c_i *type* coins,

and there are k_i coins in there.

so, new sums achievable are {y+c_i, y+2*c_i,....,y+k_i*c_i}

And, then suppose like 'Y' we had lots of other reached sums in a set A={Y,X,Z,...}......(these are sums reached before we got the bag of c_i)

and suppose X is Y-3*c_i....and now when we get new bag ,the achievable sums for this X becomes {X,X+c_i,......} which is {Y-3*c_i,Y-2*c_i,Y-c_i,Y,Y+c_i,......}

and we notice common values in new achivable sum from Y and X.

So if we already calculated the common values , when we found achievable sums for Y and then we only need to calculate 2 values...they are Y-2*c_i and Y-c_i;

--------------------------------------------------------

this is what i think is written in last line .


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thank you for your kind reply. But I still don't understand your statement:

    So if we already calculated the common values,

    When did we calculate the common values? You said that A={Y,X,Z,...}are the sums reached before the new *bag* comes in.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      we have set A={Y,X,Z,.....}.....

      Suddendly a bag comes in.....

      We get very happy to see new coins.....

      Now Lets assign some values to Y,X,Z....

      Let Y=5,X=2,Z=8.....

      Now the bag has 10 coins of each having value 1.

      So with Y ...the new possible sums would be...(can u guess) 6,7,8,9,10,11,12,13,14,15.

      And with X...the new possible sums would be...3,4,5,6,7,8,9,10,11,12.

      So, We see that when we calculated new possible sums for X we got 6,7,8,9,10,11,12 again which we already got when we calculated the possible sums for Y and some new values namely 3,4,5. 

      So, why waste time in calculating the values that have already been there in possible sums of Y.

      So just calculate 3,4,5.( savings of 7 calculations).

      ----------------------------------------------

      I don't know how to solve fcandy, I just wrote what I understood from the explanations by misof and others.

      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well I ask quickly to misof this year about this problem and what he told me was almost the same from his comments.

(this part)
"Second, back to the original problem. Assume that you are processing the candies one at a time. What you are looking for is a small value Z for which you can prove the following statement: For any input, there is a way to reach the optimal final difference in such a way that at any moment the difference between the two players is at most Z."

If I didn't understand wrong, he said this Z is not too larger.
→ Reply