The Gateway to Computer Science Excellence

+50 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

- $max(Y, a_0+Y)$
- $max(Y, a_0+Y/2)$
- $max(Y, a_0 +2Y)$
- $a_0+Y/2$

+77 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:**

- $\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$

- $\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.**

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

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.

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

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,355 answers

198,481 comments

105,249 users