You are not logged in. Please login at www.codechef.com to post your questions!

×

# Doubt related to a Dynamic Programming problem!

 1 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 :) 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!:) 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 asked 20 Jan, 23:59 -863●9 accept rate: 0% Note: Is there a way other than dp to solve it, like some formula? (21 Jan, 00:18)

One Answer:
 4 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. answered 21 Jan, 00:18 1★mpsingh 69●3 accept rate: 100% 2 Thank-you so much :) I awarded you some of my reputation points. Stay blessed :) (21 Jan, 00:32) 2 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 :) ) . In case if you prefer video Meet in the Middle Algorithm - @gkcs (24 Jan, 06:55) 1 Tysm :-) @aryanc403 (24 Jan, 19:07)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×966
×157
×3

question asked: 20 Jan, 23:59

question was seen: 254 times

last updated: 24 Jan, 19:07