7.3k 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$

edited | 7.3k views
+1
Take some -ve numbers in the sequence that will eliminate option D.

\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. $\bf{a_0}$ is included in the max weight subsequence of $\textbf{S:}$

In this case, $X = \text{weight} \Bigl( \langle a_0, S_1 \rangle \Bigr) = a_0 + \dfrac Y 2$

2. $\bf{a_0}$ is not included in the max weight subsequence of $\textbf{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.

by Boss (22.9k points)
edited
+2
I could not understand why X = weight(<a0,S1>) = a0 + Y/2?could you please explain.
+71
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 .

+7
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.
0
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.
+3
@Mohit GO is for people with common sense. You can believe whatever you want as correct. Once GATE result comes you will know.
0
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)
0
Example you have given already - I have replied there.
0
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.
+6

@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})$

0
I could'nt get how u are taking X=2 and Y=8 ..please explain.. I am confused