JaroPaska's blog

By JaroPaska, 20 months ago, In English

A while ago the GNU G++ 11.2.0 (64 bit, winlibs) option was added to Codeforces to facilitate the use of C++20 on the platform. However, C++20 support is still being worked on and over the past year many features have been added. It would be nice to upgrade the GCC compiler to 12.2.0, which is also available via winlibs. There is also a "Clang++20 Diagnostics" option. Which version of clang does it use?

Neither compiler seems to support #include <ranges> currently, which includes functions such as std::views::iota. Also, the GCC compiler does not have support for constexpr std::string and constexpr std::vector (and this is probably also the case for the clang compiler, although I haven't tested it).

Full text and comments »

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

By JaroPaska, history, 2 years ago, In English

For some algorithms it is necessary to calculate the modulo of the product of two 64-bit integers (rho algorithm, polynomial rolling hash with a 64-bit modulo). This can be done easily on GCC and Clang using the built-in type __int128.

However, on MSVC this type is not available. This blog post explores the options for implementing fast modular multiplication across various platforms. The author presents several approaches to modular multiplication, but only two of those actually work properly on the MSVC compiler. Those implementations are fine, but one of them is somewhat slow while the other uses a Karatsuba-like approach and I found it too complex to be comfortable with simply copy-pasting it into my template.

I did a bit of googling and stumbled across the compiler intrinsics umul128 and udiv128, which can be used to implement modular multiplication in a way that is fairly straightforward.

Note that both __int128 and the MSVC compiler intrinsics are only supported on 64-bit architectures. They don't seem to be available on the Codeforces MSVC compiler, but they work fine for me locally. This is good enough for me as I have a cross platform coding environment and I want my code to work when on Windows machines with the Microsoft compiler.

Here is the snippet that I use for modular multiplication. Feel free to share any micro-optimizations you might have.

template <class T>
constexpr int sgn(T x) {
    return (x > 0) - (x < 0);
}

long long mod_mul(long long a, long long b, long long m = MOD) {
#ifdef _MSC_VER
    unsigned long long h, l, r;
    l = _umul128(llabs(a), llabs(b), &h);
    _udiv128(h, l, m, &r);
    return sgn(a) * sgn(b) >= 0 ? r : m - r;
#else
    long long r = a * static_cast<__int128>(b) % m;
    return r >= 0 ? r : r + m;
#endif
}

Full text and comments »

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

By JaroPaska, history, 3 years ago, In English

I am curious to know kinds of setups you guys use when working on projects outside of CP and what kind of features you look for.

The IDE I have been most satisfied with thus far is CLion. CLion is not a free IDE but students are qualified for free licenses. I am quite happy with it thus far except that it is a bit slow. Also, I would like to use a tool that is free to use even when I am no longer a student.

From what I know, Visual Studio is the industry standard, but I have always been drawn away from it because I am most comfortable with GCC and know next to nothing about MSVC. Also, as I understand a lot of nice features of Visual Studio come with the Visual Assist extension which is not free. It is also not available on Linux (I dual boot, so I could kind of live with this but it is not ideal).

I have also used VSCode for a while, but I found VSCode's autocomplete to be quite bad even with the C++ extension installed, and it was also really slow (especially the autocomplete).

Recently I started experimenting with QtCreator but I haven't had enough experience with it to say much. It feels snappier than CLion but the UI is a bit different most IDEs I have worked with and I get a bit lost looking for certain features.

Finally, I suppose Vim is always an option but I expect setting up refactoring features like moving function definitions from headers to source files and things like that would be painful to set up.

So yeah, in summary, I would love to hear what your preferences are, whether you would be willing to pay for an IDE, etc. or perhaps any advice on using the programs I mentioned (maybe they are good tools and I am just bad at using them?).

Full text and comments »

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

By JaroPaska, history, 4 years ago, In English

Hello, I am trying to make a website where I would be able to post my own problems. However, I am not too keen about implementing my own judge from scratch, when there are many good judges out there already with support for many languages.

My original idea was to use Codeforces to host my problems and create an account that would submit solutions to these problems and then check the verdicts.

However, the Codeforces API doesn't support submitting solutions, so I tried to use online-judge-tools to submit the solution and then use the Codeforces API to get the verdict of the submission. But the online-judge-tools submit command doesn't tell me which ID my submission is assigned, whereas the Codeforces API doesn't return the source code of a submission, which makes it hard to match which submission on Codeforces belongs to which submission on my website.

Would you happen to have any ideas on how to solve this, or would you happen to have experience with other APIs that might be more convenient? Should I just implement my own online judge?

Full text and comments »

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

By JaroPaska, history, 5 years ago, In English

Hello everyone,

I participated in the Educational Round 73 contest and solved problems A to E, but I had a bug in my solution to B and the round was unrated for me in the end. However, despite this I would still be looking at an increase in rating of about +25 (which is admittedly still quite disappointing compared to the +214 the CF-Predictor was claiming during the contest).

I don't think that it's particularly fair that the people that would have had positive deltas even with a 0 for problem B got denied their rating change. By my standards I had an outstanding contest yesterday, and while it sucks to get screwed over by the checker for B, it sucks even more to solve 4 other problems and be denied that only because I had a wrong submission on B (if I just skipped over B and didn't submit B at all I wouldn't have this problem). I'm sure this happened to some other people as well, and that sucks, because they were also probably having a really good contest and in the end got nothing for it.

To clarify, the purpose of this post is not to bash on the fact that there was a bug in the checker for problem B, I understand that things like that happen. I just don't like the way the rating changes were addressed afterwards. To finish on a lighter note, you can try and find the bug that cost me ~200 rating.

The code
A hint

Full text and comments »

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