GATE CSE 2010 | Question: 34

Question

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

• A. $max(Y, a_0+Y)$
• B. $max(Y, a_0+Y/2)$
• C. $max(Y, a_0 +2Y)$
• D. $a_0+Y/2$

Comments

✅ Correct answer: B. max⁡(Y,a0+Y/2)

Explanation:

• If we don’t include a0, then max weight is just Y.

• If we do include a0, then all weights from Y shift one position right → divide by 2. So total becomes a0+Y/2

• Take the better of both:

X=max⁡(Y,a0+Y/2)

---

#include <bits/stdc++.h>
using namespace std;

int main() 
{
  int n; cin >> n;
  
  vector<double> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<double> dp(n + 1,  0.0);
  dp[n] = 0;

  for (int i = n - 1; i >= 0; i--) 
    dp[i] = max (dp[i + 1], a[i] + dp[i + 1] / 2.0);
  
  cout << fixed << setprecision(10) << dp[0] << endl;
  
}

 

---

Let

\[
X=\text{maximum weight of a subsequence of } a_0,a_1,\ldots,a_{n-1}
\]

and

\[
Y=\text{maximum weight of a subsequence of } a_1,a_2,\ldots,a_{n-1}.
\]

To compute \(X\), we have two choices:

\[
\textbf{Case 1: Exclude } a_0
\]

Then the best possible weight is simply

\[
Y.
\]

\[
\textbf{Case 2: Include } a_0
\]

Suppose the optimal subsequence of \(a_1,a_2,\ldots,a_{n-1}\) has weight

\[
Y=b_0+\frac{b_1}{2}+\frac{b_2}{2^2}+\cdots
\]

If we prepend \(a_0\), the subsequence becomes

\[
a_0,b_0,b_1,b_2,\ldots
\]

and its weight becomes

\[
a_0+\frac{b_0}{2}+\frac{b_1}{2^2}+\frac{b_2}{2^3}+\cdots
\]

\[
= a_0+\frac{1}{2}\left(b_0+\frac{b_1}{2}+\frac{b_2}{2^2}+\cdots\right)
\]

\[
= a_0+\frac{Y}{2}.
\]

Hence,

\[
X=\max\left(Y,\;a_0+\frac{Y}{2}\right).
\]

Therefore,

\[
\boxed{X=\max\left(Y,\;a_0+\frac{Y}{2}\right)}
\]

and the correct answer is

\[
\boxed{\text{Option B}}.
\]

Answer 1

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

Comments

@Pavankumar07

When $a_{0}$ is included then the weight of the subsequence is:

Let the weight is denoted by A:

A=  $a_{0}$ + $\frac{a_{1}}{2}$+ $\frac{a_{2}}{4}$ +  $\frac{a_{3}}{8}$+ …….......….+  $\frac{a_{n-1}}{2^{n-1}}$

When $a_{0}$ is not included then the weight of the subsequence is:

Let the weight is denoted by Y:

Y =  $a_{1}$ + $\frac{a_{2}}{2}$+ $\frac{a_{3}}{4}$ +  $\frac{a_{4}}{8}$+ …….......….+  $\frac{a_{n-1}}{2^{n-2}}$

A= $a_{0}$ + $\frac{Y}{2}$

So X= max(A, Y)

      X= max($a_{0}$ + $\frac{Y}{2}$, Y)

---

y starts with a1+a2/2 ......

but in x there is a1/2+a2/4 .....
​​​​​​​
in x we have to include y/2 not y

---

If $Y=$ maximum possible weight of a subsequence of $a_1,a_2, \dots, a_{n-2}$

then $X=max(Y,Y+a_{n-1}/2^{n-1})$

Answer 2

The weight of a sequence $a_{0},a_{1} , ............. , a_{n-1}$ of real numbers is defined as $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$.

$X$ denote the maximum possible weight of a subsequence of  $a_{0},a_{1} , ............. , a_{n-1}$ and

$Y$ the maximum possible weight of a subsequence of $a_{1} , ............. , a_{n-1}$

As the weight of the sequence  $a_{0},a_{1} , ............. , a_{n-1}$ of real numbers is defined as $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$. . 

so similarly for  the subsequence   $a_{1} , ............. , a_{n-1}$  the weight can be defined as ($a_{1}+\frac{a_{2}}{2}+.......... + \frac{a_{n-1}}{2^{n-2}}$)… 

CASE 1: Now suppose the maximum possible weight of the subsequence  is $Y$ only then it will be also maximum weight for the subsequence $a_{0},a_{1} , ............. , a_{n-1}$.

                          i.e     $X=weight(Y)$

CASE 2: if the weight $Y$ is not the maximum then we have to also include $a_{0}$ in it. and as it is given in the question that the maximum weight of the sequence $a_{0},a_{1} , ............. , a_{n-1}$ is  $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$.  .

but we have the weight $Y$ as   ($a_{1}+\frac{a_{2}}{2}+.......... + \frac{a_{n-1}}{2^{n-2}}$)…  so before adding $a_{0}$ to it we have to divide this weight by $2$ . so after dividing by $2$ we will get ( $\frac{a_{1}}{2}+ .......... + \frac{a_{n-1}}{2^{n-1}}$).

now after including $a_{0}$ we will get the maximum weight of subsequence $X$ = $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$. where $\frac{a_{1}}{2}+ .......... + \frac{a_{n-1}}{2^{n-1}}$  = $Y$

                           i.e   $X = a_{0} +\frac{Y}{2}$ 

which is the maximum weight in this case.

so from both CASE 1 and CASE 2 we can conclude that  $X$ will be

                                                            $X  = max( Y, a_{0} + \frac{Y}{2})$

ANS is $option$ $B$ !!

Comments

nice explaination

---

Great work @Pranavpurkar.

---

Clear and precise

Answer 3

✅ Correct answer: B. max⁡(Y,a0+Y/2)

Explanation:

• If we don’t include a0, then max weight is just Y.

• If we do include a0, then all weights from Y shift one position right → divide by 2. So total becomes a0+Y/2

• Take the better of both:

X=max⁡(Y,a0+Y/2)

Answer 4

OPTION B