The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+37 votes
5.8k 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 (96.1k points)
edited by | 5.8k views
0
Take some -ve numbers in the sequence that will eliminate option D.

1 Answer

+61 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 $\textbf{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 $\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.

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

+6
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.
+1
@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.
0

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

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
49,535 questions
54,122 answers
187,321 comments
71,039 users