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

2 Answers

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

+5
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})$   

+17 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.1k 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
0

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!

0
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.
0
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.
0
You can write a code to output the max value. Then you'll understand.
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

42,686 questions
48,650 answers
156,452 comments
63,961 users