ATSTNG's blog

By ATSTNG, history, 3 months ago, In English

Recently I was preparing some problems in Polygon. One of the problems required custom checker. I've implemented and set up my checker and it turned out that it gives verdict FL for all checker tests. I have tried alternating checker implementations, replacing it completely with standard wcmp.cpp code and simplifying logic into single line

quitf(_ok, "ok");

but none of that helped. Only thing that I managed to achieve is to get exit code 13131313 for roughly half of checker tests.

After messing around for a few hours I finally noticed red "Show warnings" label. (I'm not sure if this label was there when I first encountered this problem roughly a week ago.) Turns out there is that critical warning:

Turns out that I was unlucky choosing problem name set-diff-patch-notes and moving it into checker name. After renaming source file it worked just fine.

But how does this work? Are there any other bad substrings? Why there is a weird limitations for checker file names?

A friend of mine suggested that it has something to do with version control system used in Polygon. But if that's the case why any other source files (solutions, validators) have no problems with patch substring?

Read more »

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

By ATSTNG, history, 21 month(s) ago, In English

[This article is also available in Russian]

Hello, CodeForces.

I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming.

I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.)

Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only key points in whole theory, omitting a lot of intermediate results, logical steps and examples. In some article I’ve encountered this heavy-formula proof:

That was nowhere close to being clear for me. (Probably I’m not mathematician enough, yet.) But still, I’m sure there is a way to make this more clear and detailed.

I am sure, there are a lot of people in CP who will also like to get familiar with matroids. So, I’ve decided to review this topic from very beginning focusing more on explanations, logical steps and providing more examples. This is the goal of this article, and you do not need to know anything about matroids beforehand.

Read more »

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

By ATSTNG, history, 3 years ago, translation, In English

Hi, CodeForces.

Recently I decided to take a closer look at data structure called Fenwick tree or binary indexed tree.

In this blogpost I will only consider Fenwick tree for sum, but everything stated there can be easily generalized for any associative, commutative and inversable operation.

Some implementation

After reading articles about it on e-maxx.ru and neerc.ifmo.ru and asking friends I've got interested by this moment. Both articles (and my friends) use this algorithm to initialize Fenwick tree on given array:

  1. Fenwick tree for array of zeros is array of zeros, we will take it as a basis
  2. We will use tree queries to replace all elements of array with elements we need
void init_vector_classic (vector<int> a) {
    init_empty(a.size());

    for (int i = 0; i < a.size(); i++) inc(i, a[i]);
}

This will work in O(N * logN) where N is length of given array.

Can we do it faster? Definitely can!

By definition of the Fenwick tree each tree element is the sum of continious segment of initial array. Considering that we have no queries to change elements in initialization process, we can use prefix sums to calculate elements of our Fenwick tree. This will require O(N) preprocessing, but will allow to calculate tree elements in O(1). So initialization asymptotic improves to O(N) + O(1) * O(N) = O(N).

void init_vector_linear_prefix (vector<int> a) {
    init_empty(a.size());

    vector<int> prefix_sum;
    prefix_sum.assign(a.size(), 0);
    prefix_sum[0] = a[0];
    for (int i = 1; i < a.size(); i++) prefix_sum[i] = prefix_sum[i-1] + a[i];

    for (int i = 0; i < a.size(); i++) {
        int lower_i = (i & (i+1)) - 1;
        fenwick[i] = prefix_sum[i] - (lower_i >= 0 ? prefix_sum[lower_i] : 0);
    }
}

But in this implementation we get additional O(N) memory to store additional array.

Can we avoid this? Yes, we can!

We can notice that to initialize fenwick[i] we only require such elements of prefix_sum[j] where j ≤ i. This allows to use only one array and, starting from the end, change each element from prefix sum to Fenwick tree element.

void init_vector_linear (vector<int> a) {
    init_empty(a.size());

    fenwick[0] = a[0];
    for (int i = 1; i < a.size(); i++) fenwick[i] = fenwick[i-1] + a[i];

    for (int i = a.size()-1; i > 0; i--) {
        int lower_i = (i & (i+1)) - 1;
        if (lower_i >= 0) fenwick[i] -= fenwick[lower_i];
    }
}

This way we can improve initialization time of Fenwick tree to O(N) using O(1) additional memory.

Of course, in most of the problems amount of queries is not much less than the size of Fenwick tree, so improving initialization time will not improve final asymptotic of your solution. But this optimization gives as ability to improve constant of the part of your solution, that works with Fenwick tree (or trees) with just a few lines of code.

What do you think about this and how do you initialize your Fenwick trees?

UPD: There is another approach to this problem that leads to even shorter code! Thanks Jakube for mentioning this in comments and sdnr1 for creating blog about it.

Read more »

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

By ATSTNG, history, 4 years ago, translation, In English

Hi, CodeForces.

Today I tried to implement interactive problem 753B - Interactive Bulls and Cows (Easy) in Ruby. But all of my submissions (23586661, 23586795, 23586863, 23611181) got "Idleness limit exceeded on test 1".

Also this problem (and it's Hard version) has no Accepted submissions in Ruby.

Is CF bugged or am I doing something wrong?

UPD: Solved this question: the reason was my carelessness in reading problem samples, and because of that my solution was incorrect. Correct solution — 23649752.

Read more »

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