The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+32 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 (101k points)
edited by | 4.1k views

2 Answers

+53 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 (20.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.
+14 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 (17k 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

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

39,529 questions
46,674 answers
57,594 users