2
$\begingroup$

Link to the problem: https://codeforces.com/problemset/problem/1221/A.

The problem:

You are playing a variation of game 2048. Initially you have a multiset $S$ of $n$ integers. Every integer in this multiset is a power of two.

You may perform any number (possibly, zero) operations with this multiset.

During each operation you choose two equal integers from $s$, remove them from $s$ and insert the number equal to their sum into $s$.

For example, if $s =\{1,2,1,1,4,2,2\}$ and you choose integers $2$ and $2$, then the multiset becomes $\{1,1,1,4,4,2\}$.

You win if the number $2048$ belongs to your multiset. For example, if $s=\{1024,512,512,4\}$ you can win as follows: choose $512$ and $512$, your multiset turns into $\{1024,1024,4\}$. Then choose $1024$ and $1024$, your multiset turns into $\{2048,4\}$ and you win.

You have to determine if you can win this game.

You have to answer $q$ independent queries.

Here's my code that got accpeted:

Define sum = 0;

For all elements x in S such that x <= 2^{11}:
    sum += x;

If(sum >= 2^{11})  Print "YES";
Else Print "NO";
     

I've already had a proof myself and I like to share it but I don't think it's formal enough. I'm looking for a proof that is more formal than mine or if you could spot any mistakes, please feel free to point it out for me.


The idea to this problem is simple: We don't care about elements that are greater than $2^{11} = 2048$. Instead, we sum up all the elements that are less than or equal to $2048$. Two obvious cases will happen:

  1. The sum $\geq 2^{11}$
  2. The sum $< 2^{11}$

It's easy to see why case 2 will lead to a NO answer: If we can pick some elements and can sum those up to $2^{11}$(nothing's repeated because we just keep merging elements) then why the sum $< 2^{11}$ at the very start ? So, by contradiction, we prove that case 2 leads to a NO answer.

Let us prove case 1 leads to a YES answer.

$\endgroup$
2
  • 1
    $\begingroup$ 1. Please edit your question to provide a self-contained statement of the problem, so that we can understand what your question is without clicking on links, and so that the question remains comprehensible even if the link stops working. 2. We are a question-and-answer site. We require you to articulate a specific question. What exactly is your question? I find it hard to tell. $\endgroup$
    – D.W.
    Commented Dec 29, 2021 at 6:32
  • 1
    $\begingroup$ Hi, we we prefer pseudocode over code in some specific programming language (since its more readable). I encourage you to edit the question and convert the c++ code into mathematical pseudocode :) $\endgroup$
    – nir shahar
    Commented Dec 29, 2021 at 14:15

1 Answer 1

2
$\begingroup$

Consider a multiset $A = \{ a_1, a_2, a_3,..,a_n\}$, each of which has the form of $2^{t_i}$ and $\leq 2^{11}$ where $1\leq i\leq n$.

Now we design an algorithm to prove the above fact.

Step 1: If $2^{11} \in A$. We stop.
Step 2: Pick two equal elements in $A$ and merge them. But how do we make sure there exists such two elements? Suppose the reverse.
If they're all distinct, because all elements are less than $2^{11}$(we've found no $2^{11}(s)$ in step 1), the largest sum we can get is: $2^0 + 2^1 + 2^2 + ... + 2^{10} = 2^{11} - 1$. Again, no matter how many iteration the algorithm's taken, the original sum remains the same(nothing repeats here). So, it cannot be less than $2^{11}$(Remember that we're in case 1 of the proof).

So, such two elements exist and in step 2, we merge them.

Step 3: Go to step 1


Without step 1, the number of elements decreases by one after each iteration. And at the end, we're left with a number $2^T \geq 2^{11}$. And after each iteration, some $t_i$ increases by one(no "sudden change"). So, it is true that with step 1 comes into play, the above algorithm will find a way to sum up to $2^{11}$. We're done.

I don't think this proof is formal enough but interesting and somewhat "close to formality". I would like to hear more formal proofs from you. Thank you for reading :D.

$\endgroup$
1
  • 1
    $\begingroup$ I would say this proof is formal enough ;) $\endgroup$
    – nir shahar
    Commented Dec 29, 2021 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.