Блог пользователя LmuEmuLiberty

Автор LmuEmuLiberty, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Actually I don't need the help anymore. I found this: https://codeforces.me/blog/entry/72527[Your text to link here...](https://codeforces.me/blog/entry/72527)

»
3 года назад, скрыть # |
 
Проголосовать: нравится -24 Проголосовать: не нравится

Do problems that are at the same level as you

»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If you only apply the % MOD at the end of the problem you might get overflows. You should apply it after every product or sum. It seems like you already learned this.

In your latest submissions you are overdoing it though, you don't need (a%MOD+b%MOD)%MOD, just (a+b)%MOD is enough.

Additionally, a trick for making modulo slightly faster is doing something like this

sum = a + b;
if (sum >= MOD) sum -= MOD;
// alternatively
sum -= (sum >= MOD ? MOD : 0);

This only works on sums though (not products), and only if you've already taken the modulo of a and b.

Not sure why you're still getting WA though, maybe your idea is just wrong. I haven't read the problem.