Solving a dp problem from codeforces - Cut Ribbon

Question

I was trying to solve this problem and from the comments section in the editorial, I was directed to the following solution :

#include <bits/stdc++.h>
using namespace std;
#define MAX(a,b,c) max(a,max(b,c))

int n,a,b,c,dp[4001];

int f(int x)
{
    if (x == 0) return 0;
    if (x < 0 || (x > 0 && x < a && x < b && x < c)) 
        return 0xACCE97ED;                              // <- **I have doubt here**
    if (!dp[x]) dp[x] = MAX(f(x-a),f(x-b),f(x-c)) + 1;
        return dp[x];
}

int main()
{
    cin >> n >> a >> b >> c;
    memset(dp,0,sizeof(dp));
    cout << f(n) << endl;
}

I wanted to know:

What is the need of the if statement that returns 0xACCE97ED for the test case: 4000 1 2 3. This test case dosen't work when that specific if statement is missing.
Why specifically 0xACCE97ED is being returned? Because when I tried to return any other number (say 9999), then the output is expected output + 9999.

Not related to your question: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — t.niese, Dec 29 '19 at 14:32
If you use c++14 or newer then you don't need to create custom functionality to get the maximum number from any amount of numbers: `std::max({f(x-a), f(x-b), f(x-c)})`. — t.niese, Dec 29 '19 at 14:35
Does checking ``x > 0 && x < a && x < b && x < c`` necessary here? — Robur_131, Aug 07 '20 at 22:51

score 3 · Accepted Answer · answered Dec 29 '19 at 15:53

3

    if (x < 0 || (x > 0 && x < a && x < b && x < c)) 
        return 0xACCE97ED;    // -1395746835

Well looking at the dp function, it is basically maximizing values and this specific if statement is saying:

if x < 0 the length of the ribbon you cut is negative (which should be impossible)

or if x > 0 and x < a, b, c which means you can still cut X but all available sizes would result into having a ribbon of negative length

return 0xACCE97ED; return a random negative value which happens to spell out ACCEPTED because this state is invalid

And since the third if statement will try to get the max value, 0xACCE97ED will never be selected as the max value.

answered Dec 29 '19 at 15:53

alvinalvord

394
2
11

Then why doesn't the code work for the given test case when this if statement is missing? – Tapasvi Bhatt Dec 29 '19 at 15:57
the statement should not be removed because it is removing the invalid state. If you try to change the return value to -1, it will still work. – alvinalvord Dec 29 '19 at 15:58
now the test case ```100 23 15 50``` is disturbing when I put return -1. The expected output is 2 and answer is 5. Could you please help me this last time ! You've been very helpful, thanks. – Tapasvi Bhatt Dec 29 '19 at 16:44
I tried to manually do the tree and 2 is correct. 100 > 50 > 0 = 2 ribbons. – alvinalvord Dec 29 '19 at 17:23
Remember the goal is to go from 100 to 0 and 23 * 4 = 92 which means you need an 8 and 15 * 6 = 90 which means you need a 10. Any combinations of the two still wouldn't give a 100. – alvinalvord Dec 29 '19 at 17:32
Does checking ``x > 0 && x < a && x < b && x < c`` necessary here? – Robur_131 Aug 07 '20 at 22:51
Yes, because there should be no leftovers. – alvinalvord Aug 09 '20 at 07:20

score 1 · Answer 2 · answered Dec 29 '19 at 14:32

1

0xACCE97ED means "ACCEPTED" in the 1ee7 speech. nothing else specific about this value.

answered Dec 29 '19 at 14:32

lenik

23,228
4
34
43

Is 0xACCE97ED a defined constant string for C++ language? And if so, how does it solve the issue? – Tapasvi Bhatt Dec 29 '19 at 14:42
@TapasviBhatt it's not a defined constant. it could be anything like 0xC001BABE or whatever you like. you wanted to know why it's being returned -- I'm telling you there's nothing particular about this constant. you may use any other you like. – lenik Dec 29 '19 at 14:44
But the question demands some other output. In the given test-case, expected output is 4000 then, how does returning "accepted" or any other constant solve the problem? – Tapasvi Bhatt Dec 29 '19 at 14:59

score 0 · Answer 3 · answered Dec 29 '19 at 14:36

0

What is the need of the if statement that returns 0xACCE97ED for the test case: 4000 1 2 3

if (x < 0 || (x > 0 && x < a && x < b && x < c)) 
    return 0xACCE97ED;                              // <- **I have doubt here**

because the function f is recursive, in the next line it calls itself:

if (!dp[x]) dp[x] = MAX(f(x-a),f(x-b),f(x-c)) + 1;
    return dp[x];

with a smaller values for x so presumable it will eventually make that if statement true and will return "accepted" (0xACCE97ED).

answered Dec 29 '19 at 14:36

Paul Evans

27,315
3
37
54

This is the first time I've come across this ```0xACCE97ED```. Can you please tell me why is the output ```4000``` if the function returns "accepted" because I think the function ends when it encounters the first return statement so it must not move to the next line once it encounters : ```return 0xACCE97ED```. – Tapasvi Bhatt Dec 29 '19 at 14:48

Solving a dp problem from codeforces - Cut Ribbon

3 Answers3