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[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:

  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

Comments
  • Not related to your question: Why should I not #include <bits/stdc++.h>?
  • 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)}).
  • Then why doesn't the code work for the given test case when this if statement is missing?
  • 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.
  • 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.
  • I tried to manually do the tree and 2 is correct. 100 > 50 > 0 = 2 ribbons.
  • 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.
  • Is 0xACCE97ED a defined constant string for C++ language? And if so, how does it solve the issue?
  • @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.
  • 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?
  • 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.