Doubt related to a Dynamic Programming problem!

I sincerely hope, that this question does not belong to any ongoing contest : D
@aryanc403

If it does, please donโ€™t answer this question :slight_smile:

We are given integers,namely, a,b,c and d. Also, 0<=a,b,c,d<=1000

We have to satisfy this equation : a+b^2+c^3+d^4<=S,

where , 0<=s<=10^18

We will be given an integer, โ€˜Sโ€™ as the input.

We have to find the no. of integral solutions which satisfy the above equation!:slight_smile:

I know the brute-force way, can anybody propose a nice dp-way to solve it? Thanks.

Link to the sequence :----> https://oeis.org/search?q=1%2C4%2C7%2C8%2C9%2C11%2C12%2C12&fmt=data

1 Like

I think no need of DP, for all c,d<=1000 find out all values of c^3+d^4 there will be around 10^6 values, store them and sort that array (A). Now for each a,b find out all possible values of a+b^2 similarly call it array B now for each element B* of B do binary search on A and find count of all values such that A*[+B[j]<=S , so add j to ans each time.

4 Likes

Note: Is there a way other than dp to solve it, like some formula?

Thank-you so much :slight_smile:
I awarded you some of my reputation points. Stay blessed :slight_smile:

2 Likes

Recently, I came across the above technique due to E. Helping Hiasat it is known as meet in middle.
Related problem - Chef and Subsequences( Editorial exists :slight_smile: ) .
In case if you prefer video Meet in the Middle Algorithm - @gkcs

2 Likes

Tysm :slight_smile: @aryanc403

1 Like