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

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

Hello, Codeforces.

Please, welcome c++20 support on Codeforces. Yes, it is 64-bit. Thanks to Brecht Sanders: I used his distribution GCC-11.2.0-64 from https://winlibs.com/.

If you have installed PBOX, you can add this compiler with the line pbox install gcc11-64-winlibs. Probably, a good idea is to add C:\Programs\gcc11-64-winlibs\bin into the PATH. More about PBOX you can read here.

I use the compilation command line similar to other GCC installations: g++ -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++20 <source>. The only differences are -std=c++20 and -Wall -Wextra -Wconversion (I plan to use somehow such warnings in Polygon to suggest fixes in uploaded files).

Now you can use c++20 in your solutions. I'm not sure there are many features useful in competitive programming. Probably, I'm wrong. For example, now you can write vector v{vector{1, 2}}; instead of vector<vector<int>> v{vector<int>{1, 2}};. What else is useful? Please, if you are good with modern C++ then write.

You might be interested in looking at such a table. Before implementation, I always test every C++ distribution for the efficiency of reading and writing large amounts of data. For example, the latest GCC compiler from MSYS2 is terribly slow in some cases. I don't want to use it here. Also, it happens that some specifiers like lld or Lf work unexpectedly. In the table by reference, the second line is the added compiler. The columns correspond to different tests. The cell contains the time of the test execution. If I have time, I will someday publish scripts for testing c++ compiler installations.

Bye for now,
— Mike

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

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

Wow, yesterday I've just said this, and today I meet the release of GCC 11! That's great!!! Yay!!!

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

What is the advantages?

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

Wow, latest gcc and c++20 support! Can't wait to try ;)

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

Seems like C++20 doesn’t introduce a lot for CP. Most useful probably are 3-way comparison shorthand and easier struct initialization.

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

Funnily enough, you can't actually write vector v{vector{1, 2}}; instead of what you said, it's equivalent to vector<int> v{vector{1, 2}}; which is the same as vector{1, 2}

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +99 Проголосовать: не нравится

I'm not sure there are many features useful in competitive programming

std::midpoint for example. Now your binary search implementation will never overflow

  auto a = numeric_limits<int32_t>::min();
  auto b = numeric_limits<int32_t>::max();
  cout << midpoint(a, b) << '\n';

Oh, also there are a lot of bit manipulation functions. std::has_single_bit — whether x is power of 2, std::popcount — you know what, etc.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    Is binary search overflow actually an issue? The sum of lo+hi would have to be greater than int max which I'm not sure if occurs in CP problems. Also if you knew to use midpoint, then you could just rewrite the binary search to not overflow.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Last spring or summer, during some workshop, we had this exact bug in our code. On the other hand, it was the only time in my experience when this mattered

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Or, you can also learn to use long long

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

Wow!!!That's great!!!

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

what is the function of operator <=> ? the operator can use for two values that can compare but < or == or > is return true. I can't think any uses of it.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +126 Проголосовать: не нравится

    It is more useful for implementing custom types. If you implement <=>, the compiler will generate <, >, <= and >=.

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

i love codeforces be cause it is always up to date thanks mike for this update

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

1 min silence for those who still uses C++ 14

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

That's really good!

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

Does anyone know if ranges is good for competitive programming?

»
3 года назад, # |
Rev. 5   Проголосовать: нравится +403 Проголосовать: не нравится

Thanks for the update to C++20!

Since it was asked in the post, here are some C++20 features I feel would be useful (and some making stuff merely easier to look at or type) in competitive programming in C++:

  1. Finally casting from unsigned to signed variables is defined. Contrary to popular belief, this has not always been the case (it has been implementation-defined behaviour for casting elements >= INT_MAX), and one important issue is that it might affect some implementations of custom hashes. This is because C++20 finally enforces signed integers to be represented in twos-complement.
  2. Formatted printing: You could do it using printf, but printf has severely limited functionality (more importantly, it doesn't deduce types and it doesn't work for user-defined types either). Using std::format, you can get Python-like printing, saving the formatted string to a buffer and so on.
  3. The <bit> header for bit-related operations, which eliminates most of the need for using the __builtin_* family of functions, and gives some more useful things like has_single_bit, bit_ceil, bit_floor.
  4. T::contains for T = std::map, std::set and family, which avoids pitfalls like using T::count for T = multiset.
  5. std::midpoint that will finally prevent any overflow/underflow in binary search. A related function is std::lerp which does linear interpolation between two values while minimizing errors.
  6. More attribute support for constant factor time and memory optimization.
  7. std::ranges library would help you do something like sort a vector like you would do in Python, and avoid using iterators (iterators are super-handy, but writing both iterators doesn't make sense if they're going to be begin() and end() anyway). There are quite a few use-cases of std::ranges that might help make code more concise and expressive.
  8. More stuff in the standard library/language is constexpr: If you like metaprogramming as much as (or more than) I do, this is probably the most exciting feature. Now that new is constexpr, it'll make life much easier to cheese problems by computing stuff at compile time, and you won't need to write your own constexpr allocators and stuff. This also means std::vector and std::string are constexpr, which will ease metaprogramming quite a bit too (even though there are a few limitations while using them in a constexpr context).
  9. Designated initializers: Now you can assign member variables values by name (and perhaps skip some of them if they're to be initialized as if they're initialized by an empty list. As pointed out below, the order needs to be the same as declaration order. If you're memory optimizing by changing your struct layout by moving around a member variable, you won't need to change all your struct declarations everywhere, if you only ever default initialize that variable (i.e., don't mention it anywhere in the initialization).
  10. Modules: This is not useful for competitive programming, but definitely, it looks much better IMO.
  11. Concepts: This takes a nice Rust-like (and sort of Haskell-like) approach to defining the behaviour of types in a nicer manner. No more tons of std::enable_ifs and use of SFINAE.
  12. 3-way comparison and default operator==: The first thing gets rid of having to declare multiple operators for the same order, and the second one eliminates the pesky compilation errors you get when you check for struct equality.
  13. auto parameters of functions: This is officially called abbreviated function templates (because type deduction for auto is equivalent to that for templates). Remember auto return types in C++17? You can even do something like auto add(auto x, auto y) { return x + y; } or something like this now, rather than having to write out long templates.
  14. std::ssize: Gives the signed size of a container. No more underflow errors while iterating with T::size if you replace it with T::ssize (and no more need to do typecasts either). This can also be used as ssize(container).
  15. std::span: Something analogous to std::string_view but for general types (and contiguously stored elements). Might not be useful that much in competitive programming, but this has a nice interface with std::ranges.
  16. Named constants in <numbers>: No more need to use acosl(-1.0) for pi, or exp(1) for e. They're defined (with many more constants) in this header.
  17. starts_with and ends_with: This makes prefix/suffix string matching simpler (better and faster than extracting a substring and checking for equality).
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    coroutine also looks interesting and seems to enable writing python-style generators with yield statements.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    init in foreach (like in c++17 if)

    for(int i=0; int x : vec)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +39 Проголосовать: не нравится

      Something like

      int n; cin >> n;
      vector<pair<int, int>> a(n);
      for(int i = 0; auto& [x, y]: a)
          cin >> x, y = i++;
      
      ranges::sort(a);
      
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    (it has been undefined behaviour for casting elements >= INT_MAX)

    I believe it was implementation-defined, not undefined, wasn't it?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Yeah, I somehow swapped that out mentally while writing that out. I'll edit that in, thanks a ton for the correction!

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

    It seems that designated initializers do not allow reordering (source) and work only for normal structs aka aggregates which std::pair is not.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Thanks for the correction! I had misremembered, and the correct thing that designated initializers allow that a normal aggregate initialization doesn't seem to allow is that you're allowed to skip out some variables in the initialization, and not reorder them. Fixed it now (hopefully).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    The fact that std::set didn't come with contains until now and I had to use find or count instead is mind-boggling to me. You would think the one operation a container modelling a mathematical set would have is checking set containment!

    https://en.cppreference.com/w/cpp/container/set/contains

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

I have done submit 132081784 and it had RE on first test. But when I have submitted same code 132085792 C++17 it got AC. So, it was because I have used non-standart allocator, without it, my code still works. I think that isn't right and I don't know how to fix it.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится -31 Проголосовать: не нравится

Did you add it specially before first Technocup qualification contest?)

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +47 Проголосовать: не нравится

When you have comparator function
auto cmp = [](const T&, const T&) -> bool { ... };,
you can now write
set<T, decltype(cmp)> s; instead of set<T, decltype(cmp)> s(cmp);

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

recently two of my solutions timed out/MLEd in C++ 17 64-bit but passed with a comfortable margin in C++17. Can anyone explain why is that the case? The difference was 100 MB for the MLE and ~0.2 sec for the TLE.

So why is 64 bit sometimes badder?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    There might be many reasons for that: generally speaking, 64 bit arithmetic is slower for obvious reasons (and was much slower in the past because processors were designed to handle 32 bits efficiently but it's not as problematic now), the memory allocations are larger, cache will have higher miss rate (objects are simply bigger), and so on.

    The performance depends on many factors and it might not be easy to predict: sometimes the 64 bit programs will realize variables only use 32 bits of space and downgrade some operations, sometimes 32 bit programs can pack two ops into 64 bits which is not possible when compiled with 64 bits and so on. The idea here is thar there are numerous compiler optimizations and it's virtually impossible to predict all the effects of these optimizations for a given program in advance even for very experienced compiler engineers. Finally, it depends on the processor a lot.

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

(I plan to use somehow such warnings in Polygon to suggest fixes in uploaded files)

This looks like a great idea! I would suggest to also include -Wshadow (mentioned here). At least for me, this is one of the most useful warnings.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +57 Проголосовать: не нравится

    I've seen some holy wars on -Wshadow because of constructors, e.g.:

    struct Point {
        int x, y;
        Point(int x, int y) : x(x), y(y) {}
    }
    
»
3 года назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится

Nice I need to keep switching between 4 versions xD

Codeforces - 20
Atcoder - 17
Codechef - 14
Topcoder - 11
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

Btw, MikeMirzayanov, would you please consider adding Clang not just for diagnostics?

  • Many enterprises have already made the switch to it, especially big tech companies such as Google and Apple, so there are a lot of C/C++ coders who use it as the primary compiler, along with the rest of the LLVM ecosystem.
  • It receives more attention from compiler engineering people, because its internals are much better organized compared to GCC, and also because it has more corporate-friendly license, allowing hardware companies such as Intel and AMD to maintain their own downstream versions and contribute hardware-specific optimizations.
  • For this reason, LLVM is becoming the default in compiler engineering courses in universities and preferred in other programming courses (not in Russia though, but I believe most US universities have already switched).
  • In my experience, it frequently beats GCC in terms of performance for algorithmic programming.

I'm working on a book about performance engineering with a lot of compiler-specific C/C++ examples, and the only reason I haven't ditched GCC for Clang/LLVM is that it isn't widely available in the competitive programming environment. Adding it to CodeForces will greatly catalyze the change.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    One small downside to using clang is that you won't have __gnu_pbds for order statistics tree.

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

      Not really. GNU C++'s "Policy-Based Data Structures" is just a library, meaning there is a bunch of C++ headers in the system when GNU C++ toolchain is installed. They can be included with Clang just like any other header/library.

      Moreover, using Clang does not imply or require using libc++. By default, Clang will use libstdc++ on Linux unless told otherwise.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится
  • What else is useful?

You can now not implement a binary search for problems with binary search over a function f, if for whatever reason you don't want to do it, like so:

namespace r = std::ranges;
namespace v = std::views;
auto rng = v::iota(min,max+1) | v::transform([f](auto a) {return make_pair(f(a),a);});
auto it = r::lower_bound(rng,make_pair(true,min));

edit: this can also be reduced to this:

auto it = r::lower_bound(v::iota(min,max+1),true,{},f);
»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
for (auto i : views::iota(0, n))
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    You can almost make it look like python now:

    const auto &range = views::iota;
    const auto &reversed = views::reverse;
    auto print = [](const auto &seq) {
      ranges::copy(seq, ostream_iterator<int>(cout, " "));
      cout << '\n';
    };
    
    int N = 10;
    print(range(0, N));
    print(reversed(range(0, N)));
    
»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Thanks for this!

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

Please, add common lisp

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

It is very convenient to use projection functions when sorting structures. For example sorting edges by weight:

struct edge{ int v, u, w; };
vector<edge> e;
//input
ranges::sort(e, {}, &edge::w);
»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

How about -Wshadow? Is it included in those?

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

When will release C++20 32-bit?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Is there a specific reason behind asking for a 32-bit version? The 64-bit version is almost always faster than the 32-bit version, so I'm just curious about some use-case that's not so rare but makes 32-bit strictly necessary.

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

      Pointers take two times less space. May result in better ML fit (especially for pointer-heavy data structures like self-balancing trees) and better cache fit, hence faster execution.

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

It seems that we can use chinese characters as variable names,is it?

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

my code in c++20 gives me TLE.

whereas the same code in c++17 gets accepted in 140ms.

can someone please tell the reason behind this.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Compiling your code with -fsanitize=undefined -fsanitize=address options and running it with the first testcase input data results in the following error: test.cpp:28:5: runtime error: execution reached the end of a value-returning function without returning a value

    Your pre() function needs to return void instead of int. Fixing this source of undefined behaviour makes your solution run fine at least in https://codeforces.net/problemset/customtest

»
21 месяц назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I have different answers too

problem: https://codeforces.net/contest/459/submission/193205657

TLE 17 using GNU C++ 20 64: https://codeforces.net/contest/459/submission/193205461 ACC using GNU C++ 14 : https://codeforces.net/contest/459/submission/193205657

can anyone explain why?