LmuEmuLiberty's blog

By LmuEmuLiberty, history, 3 years ago, In English

In the problem description of Codeforces Round 862 (Div. 2) F1. Survival of the Weakest (easy version), it describes the fact that the answer can be quite large and needs to be outputted modulo 10^9 + 7. While trying to get this answer, I ran into the problem that the answer itself was far too big to even fit in a long long, as codeforces threw an integer overflow error on test case 5. How can I keep the numbers small? Can this problem be done with long long, and is there just a problem with my code?

My solution is a faster version of brute force. Normally, one would think of brute forcing all pairs, but would cause the problem to run in N^3. My idea comes from the fact that in a vector sorted in non decreasing order, for any given index,f, as you move the index you pair with it ,s, forward, the sum of the two will naturally get larger. So I added to a priority queue every index and the one index after each one(excluding the very last one index). Then I extracted the two indices that had the smallest sum and added it to a new vector, and then moved the second indice forward, which was repeated the size of the vector-1 times.

Code is below in the failed submission.

212001851

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it