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

karangreat234's gravatar image

5★karangreat234
-8639
accept rate: 0%

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

(21 Jan, 00:18) karangreat2345★

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.

link

answered 21 Jan, 00:18

mpsingh's gravatar image

1★mpsingh
693
accept rate: 100%

2

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

(21 Jan, 00:32) karangreat2345★
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) aryanc4035★
1

Tysm :-) @aryanc403

(24 Jan, 19:07) karangreat2345★
toggle preview
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