When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

lizhiqing's blog

By lizhiqing, history, 10 months ago, In English

I recently came across a question that I thought about for a long time without any ideas. I read its solution, but I still didn't understand how to do it.

I've put the problem and part of the solution below in the hope that someone can answer my question.

Given integers $$$n,l,r,x$$$, find an integer sequence $$$a_1 \ldots a_n$$$ such that $$$a_i \in [l,r]$$$, and the XOR sum is $$$x$$$. Maximize $$$\sum_{i=1}^n a_i$$$. If there is a solution, output the largest possible $$$\sum_{i=1}^n a_i$$$. If there is no solution, output -1.

Multiple test cases. $$$1 \leq n \leq 10^9$$$, $$$0 \leq x,l,r \leq 10^9$$$, $$$T \leq 10^6$$$.

And there are some lemmas in the solution,but I can't prove it.

Lemma:

  1. If a solution exists, there are at most $$$\lceil\log_{2}{r}\rceil$$$ numbers $$$a_i$$$ which satisfy $$$a_i < r$$$;

  2. If a solution exists and the highest differing bit position between $$$l$$$ and $$$r$$$ is $$$t$$$, then in the optimal solution there are at most $$$3$$$ numbers $$$a_i$$$ which are less than $$$2^t$$$.

Tags math, dp
  • Vote: I like it
  • +20
  • Vote: I do not like it