Doubt related to a Dynamic Programming problem!

general
, ,
1

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

2

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

3

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[i] of B do binary search on A and find count of all values such that A[i][+B[j]<=S , so add j to ans each time.

3 Likes
4

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

1 Like
5

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

1 Like
6

Tysm :slight_smile: @aryanc403