## Solving a dp problem from codeforces - Cut Ribbon

codeforce cut ribbon solution
cut ribbon codeforces solution in python
cut ribbon codeforces recursive solution
rod cutting problem
codeforces solved problems
cut ribbon - leetcode
codeforces problem set solutions
maximum ribbon cut

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;

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:

1. 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.

2. Why specifically `0xACCE97ED` is being returned? Because when I tried to return any other number (say 9999), then the output is `expected output + 9999`.

```    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.

Cut Ribbon || Codeforces Round #119 (Div. 2) || c++ solution, question link : http://codeforces.com/problemset/problem/189/A. 2) || c++ solution Duration: 6:43 Posted: 21 Apr 2020 Problem 189A — Cut Ribbon. The problem is to maximize x+y+z subject to ax+by+cz=n. Constraints are low, so simply iterate over two variables (say x and y) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions. Other approaches: Use dynamic programming with each state being the remainder of

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

'Cut Ribbon' problem in Codeforces?, Can you explain to me, please, the dynamic programming solution to the "Cut Ribbon" problem in Codeforces? http://www.codeforces.com/problemset/problem � Case-1: \$ g++ cut_the_ribbon.cpp \$ ./a.out Enter the length of ribbon 5 Enter the 3 values of lengths allowed 5 3 2 Maximum number of pieces in which the ribbon can be cut is 2 Case-2: \$ ./a.out Enter the length of ribbon 7 Enter the 3 values of lengths allowed 5 5 2 Maximum number of pieces in which the ribbon can be cut is 2 Case-3: \$ ./a.out Enter the length of ribbon 16 Enter the 3 values

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`).

Problem - 189A, Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions: After the cutting each ribbon piece should� 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

Cut Ribbon Problem - Dynamic Programming Solutions, n=5 a=5 b=3 c=2 Expected result=2 (5=3+2) n=7 a=5 b=5 c=2 Expected result=2 (7=5+2) n=16 a=7 b=5 c=3 Expected result=4 (16=7+3+3+3) Cutting Rod dynamic programming - Duration: 7:33. 0-1 Knapsack Problem (Dynamic Programming 9:21. Using The GCF To Solve A Word Problem - Duration: 3:17. mrmaisonet Recommended

Codeforces Solution 189A – Cut Ribbon – Solved Programing , Problem link—189A - Cut Ribbon /* Harun-or-Rashid CSEDU-23rd Batch */ By coder_87, contest: Codeforces Round #119 (Div. 2), problem:� Problem overviews. Keywords. solution codeforces 189A, codeforces solution 189A, codeforces solution Cut Ribbon, 189A tutorial codeforces, solution 189A codeforces

https://github.com/Waqar-107/Codeforces/blob/maste, This is the characteristics of DP problems. So we can apply DP. As top-down approach looks more natural let's first implement this solution. I'm� Codeforces. Programming competitions and contests, programming community Problems # Name ; 580A Kefa and First Steps Cut Ribbon . brute force, dp. 1300

• 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)})`.
• 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.
• 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`.