snowmanonahoe's blog

By snowmanonahoe, history, 11 months ago, In English

I have solved competitive programming. With my algorithm, you can solve any programming problem ever!

The reason a general algorithm for all algorithms does not exist is because of the halting problem. If you were to iterate through all programs, it is impossible to determine whether or not a program will halt, so you will hit a program that is an infinite loop with no deterministic way to continue.

But, this is cp, there's a time limit, so we can just cut it off at the time limit. No more halting problem.

The algorithm:

  1. Iterate through every writable ASCII string.

  2. Try to compile it.

  3. If it succeeds, run the sample case on it.

  4. If it gives the right answer, submit it.

  5. Continue until AC.

LGM has never before been so easy.

Full text and comments »

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

By snowmanonahoe, history, 12 months ago, In English

Many great functions offered by the C++ standard library go criminally underused. I've listed a few of my favorites here.

C++11

  • std::iota fills a data structure with incrementing values.

C++17

  • std::unique iterates through a sorted data structure and puts adjacent duplicate values at the end of the structure.
  • std::count counts values in a data structure that compare equal to an argument.
  • std::set_intersection finds the common elements in 2 sorted data structures.
  • std::rotate shifts elements, placing the rightmost elements at the beginning as necessary.

C++20

C++23 (Not supported by Codeforces)

  • std::unreachable marks unreachable code to enable compiler optimization and debug trapping. (Pre-C++23 alternatives: GCC/Clang: __builtin_unreachable() MSVC: __assume(false))

Miscellaneous

  • std::max and std::min take an initializer list, so you don't have to nest them within themselves.
  • Binary search on a monotonic function using std::partition_point and std::views::iota: See here

If I missed anything, comment it and I'll add it. I understand some of these functions are categorized in the wrong C++ version, but I can't figure out what the right one is for the ones that have been pointed out, such as partial_sum, accumulate, and adjacent_difference.

Full text and comments »

Tags c++, stl
  • Vote: I like it
  • +75
  • Vote: I do not like it

By snowmanonahoe, history, 13 months ago, In English
  • Vote: I like it
  • +23
  • Vote: I do not like it

By snowmanonahoe, history, 22 months ago, In English

It's well known that rand() is evil. The consensus appears to be to use the STL Mersenne twister, and the STL millisecond(?) precision clock as a seed. This is all fine and dandy, but there's a problem, as appears in the linked blog:

for (int i = 1; i < N; i++)
        swap(permutation[i], permutation[uniform_int_distribution<int>(0, i)(rng)]);

There's so many words. uniform_int_distribution is like, 2 really big words. And I hate big words. Fortunately, there's a solution:

#include <bits/stdc++.h>
#include <experimental/random>
// Note: experimental headers are not included by bits/stdc++.h
using namespace std;
int main() {
    experimental::reseed(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 0; i < 10; i++)
        cout << experimental::randint(0, 10) << '\n';
}

Try it

randint uses an STL PRNG to return a number in the range of the 2 arguments, inclusive. The PRNG used appears to be implementation-defined (meaning it might be the subtract-with-carry or linear congruential generator), but that's ok, because what we may lose in RNG quality is made up for by the fact that a hacker won't know which generator is being used. (Note: the documentation says the state of the "per-thread" RNG is unpredictable at the beginning of execution. This does not appear to be the case on Codeforces after some cursory testing. Calling reseed() is still necessary.)

Defined in the experimental/random header is also experimental::shuffle() and experimental::sample(), which both work like their non-experimental counterparts, using the implementation-defined RNG instead of having to make one to pass as argument.

This does have some drawbacks.

  • Isn't a function object, can't be passed to one of the couple of STL functions that want one

  • PRNG used is implementation-defined

  • Experimental header

For these reasons, I see it as a convenient middle ground to a Mersenne twister, when you really just need one number for, say, a hash function.

Documentation

Full text and comments »

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