57417erlp2GPq9cYqEX's blog

By 57417erlp2GPq9cYqEX, 3 years ago, In English

The GNU C++ options available on Codeforces are:

  1. GNU G++11 5.1.0

  2. GNU G++14 6.4.0

  3. GNU G++17 7.3.0

  4. GNU G++17 9.2.0 (64 bit, msys 2)

The features in the newer C++ standards don't seem to matter for a competitive programmer but what does matter is whether the solution fits in the time limit. The variation in the running times can be over 50% for the exact same code and there is no option that always beats the others. Basically we have a rock paper scissors scenario.

If you average over say 50 rounds does any option perform better? Has anyone performed this kind of analysis?

Full text and comments »

By 57417erlp2GPq9cYqEX, history, 3 years ago, In English

Consider the following operation on strings: pick a subsequence, remove it and then append all the characters at the end in the same order. This operation preserves the length of the string.

  1. Given two strings S and T can you decide in quadratic time if you can get T by applying this operation once to S?

  2. Given two strings S and T can you decide in polynomial time if you can get T by applying this operation to S and then applying it once more to the result?

There is a algorithm in cubic time for the first one (for each suffix of T that is also a subsequence of S check if S is an interleaving of that suffix and the corresponding prefix).

Note that there are S and T such that you can get T from S in two operations but not one (e.g. S=abc and T=cba).

Full text and comments »