I was practicing some questions on diophantine equation when I saw a classical jump problem where we had to determine if we can reach to point 'n' from point 0 by taking jumps of length 'a' or 'b' in either direction(i.e. left or right) on an infinite number line. However I was thinking for variation of this question where we have an additional constraint that at any point of time in our path, we should never go outside the range [0, m] where 'm'is any number greater than or equal to 'n'. Out of all the testcases that I was able to make, I observed that such constraint holds if n is divisible by gcd(a, b) (same as the normal variaton), but I am not able to prove it mathematically for this variation. Can anyone help me in this?

Formally: Can anyone give me a mathematical proof that if n is divisible by gcd(a, b) then there exists a way in which we can reach 'n' in such a way that we are always within the range [0, m] (m >= n), or if my assertion is wrong then I want to know about the flaw in this statement.

This blog entry is regarding a doubt in a problem from hackerearth.

Problem Link

I need help regarding my solution as I am getting wrong answer verdict for all testfiles(except one), I am unable to understand what is going wrong in my code, any sort of help is highly appreciated.

Problem description in brief:

Given an integer N denoting the number of elements, an integer W denoting the maximum capacity of the bag and a set of elements with their respective value and weights.

The problem is to find the maximum value that can be achieved by choosing some elements(if possible all), similar to the Knapsack problem, the only difference is that we can either multiply the value of any element by any of the first 10 prime numbers (Note: if a prime number is chosen once then it can not be chosen for any other number) or we don't.

For example:
Let N = 3(number of elements) and W = 4(maximum capacity of bag) and element's value and weight respectively are
1 1
2 1
3 1

then answer will be 152 i.e. (3 * 29) + (2 * 23) + (1 * 19) = 152

My approach :
My approach consisted of firstly sorting all the elements according to their given value in ascending order and then making a 3 state dp array i.e. dp[N][P][W] where dp [i][j][k] will denote the maximum value by using first i elements with first j primes and having a total weight equal to k.

Memory optimization:
To optimize memory I tried to toggle state of N between 0 and 1 as in knapsack we need the answers for previous state to compute the current state, therefore my dp array size became 2 * 10 * 2000.

Recurrence relation that I formulated:
Note: Here i, j and k are used for number of elements, number of primes and total weight till now respectively.

dp[i][j][k] = dp[i - 1][j][k];

if(k >= element[i].weight)
{
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - element[i].weight] + element[i].value);

dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - element[i].weight] + (element[i].value * primes[j])); 
}

In my code I am finding the answer of the current state by toggling the value of i(the index used for number of elements) between 0 and 1.

My C++ solution link

Can anyone help in telling what is the ambiguity in my code or where my logic is failing?