Quiz Space

Advanced Algorithms · Quiz 1 · 7 Jul 2024 · May 2024 term

Question 4: There are 2n positive integers written on a whiteboard. H…

Question 4

+2 marksOne or more correct options

There are 2n2n positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly nn times:

  • Choose two integers xx and yy that are written on the whiteboard.
  • Add min⁡(x,y)\min(x, y) to your score.
  • Erase xx and yy from the whiteboard.

Note that after performing the move nn times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the nn moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the general strategy for solving this problem? Select all strategies that are correct.

Select all that apply.

  1. A

    Pick the two smallest available numbers in every step.

  2. B

    Pair the smallest and largest numbers in every step.

  3. C

    Pair the smallest number with the median element in every step.

  4. D

    Pair the largest number with the median element in every step.

  5. E

    Pick the two largest available numbers in every step.

Show answer

Correct answers

  • A

    Pick the two smallest available numbers in every step.

  • E

    Pick the two largest available numbers in every step.

Question 4 of 26 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 7 Jul 2024, in the May 2024 term (IIT M DEGREE AN EXAM QDB2 7 July 2024). It carries 2 marks.

More questions from this paper

  1. Q1There are 2n positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a …
  2. Q2There are 2n positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a …
  3. Q3There are 2n positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a …
  4. Q5Alice and Bob play the following game using an array a of n integers: Players take turns, Alice moves first. Each turn …
  5. Q6Alice and Bob play the following game using an array a of n integers: Players take turns, Alice moves first. Each turn …
  6. Q7Alice and Bob play the following game using an array a of n integers: Players take turns, Alice moves first. Each turn …
  7. Q8Alice and Bob play the following game using an array a of n integers: Players take turns, Alice moves first. Each turn …
  8. Q9Alice and Bob play the following game using an array a of n integers: Players take turns, Alice moves first. Each turn …
  9. Q10Alice and Bob play the following game using an array a of n integers: Players take turns, Alice moves first. Each turn …
  10. Q11Based on the above data answer the given subquestions.
  11. Q12Based on the above data answer the given subquestions.
  12. Q13Based on the above data answer the given subquestions.
  13. Q14There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  14. Q15There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  15. Q16There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  16. Q17There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  17. Q18There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  18. Q19There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  19. Q20There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  20. Q21There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  21. Q22There are N flowers arranged in a row. For each i(1 \leq i \leq n), the height and the beauty of the i-th flower from t…
  22. Q23How many cops are necessary and sufficient to catch the robber on a path?
  23. Q24How many cops are necessary and sufficient to catch the robber on a tree?
  24. Q25How many cops are necessary and sufficient to catch the robber on a cycle?
  25. Q26How many cops are definitely enough to catch the robber on a graph of treewidth k?