DP problem interesting doubt

general
1

You are given an Array of 2N positive integers.There are N rounds in total.You have to choose any 2 positive integers from an array and delete them.
Your score in each round will be gcd(num1,num2) * round_number where num1 and num2 are the. number you have chosen and round_number is the current round. Your total score will be the summation that you have obtained in every round.
Determine the total score.
Round starts from 1.

CONSTRIANT : 1<=N<=10
EXAMPLE

N=3
A=[8 5 6 25 6 16]

ROUND 1 = gcd(5,25) Round_number = 5 1=5
ROUND 1 = gcd(6,6) Round_number = 6 2=12
ROUND 1 = gcd(8,16) Round_number = 8 3=24

MAXIMUM= 5+12+24= 41

EXAMPLE 2

N=
A=[3 4 9 5]

ROUND 1 = gcd(4 ,5 ) Round_number = 1 1=1
ROUND 1 = gcd(3,9) Round_number = 3 2=6

MAXIMUM=1+6=7
…

I try greedy and brute force (maximum gcd * maximum round no.) but wrong ans on some test case. I finded out it was DP problem.
Eg: 6 5 6 30
gcd(30,6)*2+gcd(6,5) * 1
6 * 2+1 * 1= 13 (brute forca)

**But correct anser **
2 * gcd(6,6) + 1 * gcd(5,30)
2 * 6 + 1 * 5 = 17 (not brute force)

2

Can you share the link?

2 Likes
3

aree yaar kon ho tum log kaha se aate ho

copy and google, many link in googles avialable. past hiring test. how i send link of problem? test over. many peple i thinking wrote test and they can verify this qn is from past test. not live now
http://discuss.codingblocks.com/t/please-help-using-recursion/148241

https://brainly.in/question/37387083

https://www.sololearn.com/Discuss/2733551/number-game

4

why am asking the qn, i not see these kind DP problem anywhere. i will be happy if someone explain the DP sol.

5

What I actually need:

  • Constraints
  • Whether it is from any live contest or was asked in any…

Not so jobless dude

Every link you shared is redirecting to some discussion or forum.

Is that a DP problem :thinking:, I don’t think so.

1 Like
6

sorry i forgot constriant . 1<=N<=10. not live now. in past this qn asked in test

7

dude. greedy will fail. so DP

8

You missed the constraints for Array Elements. It looks like this.

  • 1 \le A_i \le 10^3 Or
  • 1 \le A_i \le 10^6 Or
  • 1 \le A_i \le 10^9
9

I second this. Make sure to give proper source and constraints to receive a response.

10

dude.
constraint for a[i]
1<=a[i]<=10^3 or 10^6 or 10^9
am not sure for contraint but sure 1<=N<=10.
the test is alredy over.
@cubefreak777 u want me to prove this qn not from live contest? sorry. i cant. bcoz in india test qns not public after test. but i speak thruth. u can ask anyone who give that contest in hackerrearth. this test already over long back.

these days in codechef proving a qn not from live contest become more tougher than prove correct solution for answer :sleepy:

11

i got 4 replies for post but no reply help me about problem. sorry to say @admin but am not getting any help by codechef discussion forum. only time waste. people reply to ask problem src but no one help to solve problem

12

i trust codechef but no vice versa

1 Like
13

Just hold on, when did any of us ask to prove anything. We just asked for problem source and constraints because without that problem is very hard to solve.

Stop cluttering the forum with this unproductive crap and tagging the admin unnecessarily. Feel free to leave if you think it’s a time waste no one is jobless here.

1 Like
15

Now let’s get down to business. Do you have any experience with bitmask dp? This problem can be easily solved in \mathcal{O}(N^22^N) given the constraints are small.

16

i know them seprately.
can u tell the approach? i will try and understand

17

Have you tried brute force?

18

What do you mean separately? I mean I don’t mind explaining but it would all be in vain if you don’t understand have a basic idea of bitmask dp.

19

I don’t think that would pass. since N=20 so 20! won’t be in the limits I think

20

It was 10
CONSTRIANT : 1<=N<=10

21

u mean grredy brute force? yes but greedy failed. else i think brute force not possible coz 1st 20C2 x 18C2 x 16 C2 … i think like this brute force will TL