The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
4.1k views

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

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

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
0
I could not understand why X = weight(<a0,S1>) = a0 + Y/2?could you please explain.
+31
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.
0

@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 .

+4
You are calculating the weight of the sequence. But in question X and Y are defined for sub-sequences.
0
can I take the sequence as 5,1,2,3 as a0,a1,a2,a3???
+7
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.
0
i didn't understand...can anyone explain with example...
+1
@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
–1
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.
0
yes, sorry

B) is answer, as the numbers are real, So, a0 could be -ve too. Then max value of X=weight of Y
0
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
Answer:

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
139,824 comments
57,594 users