ExplodingFreeze's blog

By ExplodingFreeze, history, 2 months ago, In English

First of all apologies if this is something that has been asked before, my searching ability appears to have failed me then.

While using printf with formatting for zero padding on CF (including custom invocation), I encountered this strange behavior:

WA — 109283810

AC — 109284812

The only difference between these two submissions in the language chosen (32bit vs 64bit C++17). Somehow in the 32-bit version, the second argument is always processed as zero.

In the 32-bit C++17 version, splitting the printf into 2 printfs also causes it to get AC — 109284259

  1. Does CF use a different compiler / environment for 64 bit that could explain this difference in behavior?

  2. Is there some undefined behavior in my code that is the source of this inconsistency?

Read more »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By ExplodingFreeze, history, 12 months ago, In English

Tl;dr — Assuming negligible cache misses, how many simple operations (reading/setting array values, comparing integers, addition, subtraction, multiplication) can you perform in a second on Codeforces?

So recently I was trying 1303E - Erase Subsequences and I realized that my code which appeared to be $$$ N^{4} $$$ ran extremely quickly in custom test for inputs with $$$ N = 400 $$$, so I ended up submitting it and got accepted in just 650ms — 79311246.

While at first glance it appears as if it the loop would run $$$ N^{4} $$$ times ($$$ 2.5 * 10^{10}$$$ times at worst), you can show it will run much faster than that, actually taking $$$ \sum_{i = 1}^{\left | t \right |} (i + 1)(\left | t \right | - i + 1)(\left | s \right | - \left | t \right | + 1) $$$ operations. Simplyifying this we get $$$ \frac{1}{6}(\left | s \right | - \left | t \right | + 1)(\left | t \right |^{3} + 6 * \left | t \right |^{2}) $$$.

Maximizing $$$ \left | s \right | $$$ and throwing this equation into Wolfram Alpha we get a maxima of a bit under $$$ 5 * 10^{8} $$$. A test which approaches this maxima is simply $$$ \left | s \right | = 400 $$$ and $$$ \left | t \right | = 300 $$$ with all characters of both the strings being the same.

However considering the if statements with character comparisons and dp array value assignments in each loop iteration, as well as the zeroing of the array, the number of simple operations performed easily approaches $$$ 4 * 10^{9} $$$.

So my question is — Assuming a fair amount of cache persistence, has anyone tested how many simple operations can run in a second on Codeforces?

The reason I mention cache persistance is it clearly plays a massive role in solutions like this, swapping the 2nd and 4th loops results in the runtime increasing from $$$750ms$$$ to nearly $$$3000ms$$$ for the max test.

Theoretically the limit on the number of operations would be $$$ \frac{\text{clock speed } * \text{ instructions per clock per core}}{\text{average clock cycles per operation}} $$$, which assuming Codeforces is running a fairly modern processor capable of around 8 instructions per clock per core, clocked at 4Ghz (unlikely if its a high core count processor), would yield somewhere around $$$ 8 * 10 ^ {9} $$$ instructions per second assuming an average operation requires 4 clock cycles. However in practice, I guess this limit would be a fair bit lower.

Read more »

  • Vote: I like it
  • +41
  • Vote: I do not like it