The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+37 votes

The weight of a sequence $a_0,a_1, \dots, a_{n-1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}$. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the maximum possible weight of a subsequence of $a_o,a_1, \dots, a_{n-1}$ and $Y$ the maximum possible weight of a subsequence of $a_1,a_2, \dots, a_{n-1}$. Then $X$ is equal to

  1. $max(Y, a_0+Y)$
  2. $max(Y, a_0+Y/2)$
  3. $max(Y, a_0 +2Y)$
  4. $a_0+Y/2$
asked in Algorithms by Veteran (115k points)
edited by | 5.4k views
Take some -ve numbers in the sequence that will eliminate option D.

2 Answers

+61 votes
Best answer

&S = \langle a_0, S_1 \rangle\\
&S_1 = \langle a_1, a_2, a_3 \ldots a_{n-1} \rangle

Two possible cases arise:

  1. $a_0$ is included in the max weight subsequence of $S$:

            In this case, $X = \text{weight} \Bigl( \langle a_0, S_1 \rangle \Bigr) = a_0 + \dfrac Y 2$
  2. $a_0$ is not included in the max weight subsequence of $S$:

            In this case, $X = \text{weight}(S_1) = Y$

Since the value of $a_0$ can be anything (negative or $<\frac Y 2$ in general) $\{ \because a_i \in \mathbb{R} \}$, it is possible that $Y > a_0 + \frac Y 2$.

The maximum possible weight of a subsequence of $S$ is given by: $$X = \max \left ( Y, a_0 + \frac Y 2 \right )$$

Thus, option B is correct.

answered by Boss (21.8k points)
edited by
I could not understand why X = weight(<a0,S1>) = a0 + Y/2?could you please explain.
Because when a0 is included, then we have to half the weight of the remaining sequence as per the given definition of sequence weight.

For example consider S = 2 4 8 16, weight, w = 2 + 4/2 + 8/4 + 16/8 = 8.

Now, consider S' = 5 2 4 8 16, weight, w' = 5 + 2/2 + 4/4 + 8/8 + 16/16 = 5 + 4 = 9 = 5 + w/2.

@arjun sir and @pragy dont you think option "D" will be the right ans. here is the sequence to opt out option B.

0 2 4 8

X= 0+ (2/2) +(4/4) +(8/8)=3

for Y the sequence is 2 4 8 as it starts from a1

Y= 2+(4/2)+(8/4)=6

APPLYING  option B

X value will be max(6,3) which is 6 .But X value is 3.

It is only a0+Y/2 = 0+3=3

when the sequence starts from 0 it causes exception .

You are calculating the weight of the sequence. But in question X and Y are defined for sub-sequences.
can I take the sequence as 5,1,2,3 as a0,a1,a2,a3???
Taking an example sequence can help in eliminating options - it can say if one or more option is not possible. But it can never say if a given option is correct.
i didn't understand...can anyone explain with example...
@Arjun Sir,

If we take S = <-2, 2, 4, 8, 16>

Then option B) will be false and D) will be correct.

From the above sequence X = 2 and Y = 8.

if we take option B) it will be

X = $max(Y, a0+ Y/2)$

X = max(8, -2 + 4)

X = 8. but it is X = 2. which is false.
Shubhanshu and arjun. Brothers how can you verify the answer b as correct without checking correctly. Authenticity of gateoverflow is at check this way. Geeksforgeeks and made easy previous year also says its d. And d is the correct one.
@Mohit GO is for people with common sense. You can believe whatever you want as correct. Once GATE result comes you will know.
Brother check at the end. Ive sent a photo of proof too .actually the weight of subsequence is not depending on a0. Whatever the value of a0 .It will always be a0+Y/2 . Its not about believing. Check the simple induction of the given formula. It always fits a0+Y/2. Just give me one sample data where it violates this case and we have to use max(Y,a0+Y/2)
Example you have given already - I have replied there.
We do not have to compare a0+Y/2 may be <Y. We have here inequality as a0+Y/2 is always equal to X .And that is the answer its asking. What is X in terms of Y. Max function has no significance here. Take any data . Give just one data that makes the use of MAX.

@Shubhanshu , you are assigning weight of the given sequence $<-2,2,4,8,16>$ to $X$

but in question , $X$ denotes the maximum possible weight of a subsequence of the given sequence.

According to definition of 'Y' , it will be $8$ here as you got because we have to include all the elements from $a_{1}$ to $a_{n-1}$ to get the maximum weight of the subsequence. we don't have any choice of excluding any element because we need maximum weight. So, $Y$ = $8$.

Now, to get the maximum weight of the subsequence of the given sequence  $<-2,2,4,8,16>$ ,

We have 2 choices either include element $-2$ in the maximum weight of the subsequence of the sequence  $a_{1}$ to $a_{n-1}$ which is $Y$ here  (or) exclude $-2$ to get the maximum weight.

If we include it , then according to the definition of weight of a sequence , it will be $-2 +\frac{Y}{2} = 2$

but if we exclude it , then it will be simply '$Y$' which is 8.

So, here maximum value of 'X' = 8 which is $max(Y,a_{0}+\frac{y}{2})$   

+19 votes
No doubts (B) is answer! how?

answers will be max( Y, X) we just need to find X in the terms of Y because we have two subsequences X and Y but X is not given inside MAX function in any options.

Suppose P = 20, 40, 32 hence Y = 20 + 40/2^1 + 32/2^2

= 20+20+8 = 48


Now we need to add a0 with our Y, a0 can be negative or positive because a is a real number can be -ve too. if a0 is -ve then

a0 + Y < Y // if a0 is -ve


lets calculate X now as a0 , a1/2^1, a2/2^2 ....... an-1/2^(n-1)

X = 30 + 20/2^1+ 40/2^2+ 32/2^3 = 30 + 10 + 10 + 4 = 54


X is 54, a0 is 30 and Y is 48

in the terms of Y, X will be = a0 + y/2 i.e. 30 + 48/2 = 54


hence MAX (Y, a0+ Y/2) is correct answer!
answered by Boss (17.3k points)
edited by
I think according to option D

when a0 will be negative then answer will be Y only but if we will do this then a0 which is the part of X will be lost.
yes, sorry

B) is answer, as the numbers are real, So, a0 could be -ve too. Then max value of X=weight of Y
while calculating Y, we r already adding a0, so in next line why it is again added and how r u taking the value of a0=30 when calculating x

Brother answer must be d) it cannot be b) even if a0 is negative the condition a0 + Y/2 is satisfying . See ive done for both data. Once for a0 as positive once for a0 as nevative. When a0 negative initial weight we get is 4. So a0 + Y/2 is also giving us 4. Why to max function then. So  answer must be D!

For the second part, answer must be the weighted sum of $\langle 4, 8, 16 \rangle = 4 + 4 + 4 = 12$ as $-2$ gets eliminated from the sequence. To understand this question you must be knowing Dynamic Programming.
Yeah lets say Y=12. Now add any a0 in the subsequence and find its weight. A0+Y/2 = X . It will never be greater than Y . EVEN IF We take a0 = Y. So X = Y + Y/2. Not the max of both.
You can write a code to output the max value. Then you'll understand.

@Mohit Saluja what's the case if a0 is greater than or equals to -(Y/2).eg - -6,4,8,16. Y = 4 + 8/2 +16/4 = 12.

now X = -6 +12/2 = 0 < Y.So in general,as our aim is to maximize the weight we take MAX(Y,a0+Y/2)

in the question it is states that that Y is the maximum possible weight of a subsequence of a1,a2.........a(n-1)

so according yo your example

Y should be 40+32/2=56

isnt it?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,886 questions
52,256 answers
67,672 users