Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

TheScrasse's blog

By TheScrasse, history, 13 days ago, In English

Hello everyone,

this blog is similar to 90744, but it's specifically about implementation.

Although practicing for around 2 years, I'm still very slow in implementation. For example, during olympiads I usually spend ~ 70% of the time writing the code, so I don't have much time to think.
In fact,

  • during CEOI 2021 Mirror (Day 2) I spent a lot of time writing ~ 220 lines of code for problem C (the logic of that solution was wrong, but that's another story)
  • I've just solved CEOI 2016/1 (submission), but my solution is 239 lines long.
  • I don't perform well on DMOJ (my contests: 1, 2, 3)
  • I spent 1:30 hours implementing 101597A, although my final code is only 81 lines long.

How to improve? Should I learn new C++ features? Should I start implementing something significantly longer than competitive programming problems?

Read more »

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

By TheScrasse, history, 3 months ago, In English

Hello everyone,
problems about swapping adjacent elements are quite frequent in CP, but they can be tedious. In this tutorial we will see some easy ideas and use them to solve some problems of increasing difficulty. I tried to put a lot of examples to make the understanding easier.
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.

Target: rating $$$[1400, 2100]$$$ on CF
Prerequisites: greedy, Fenwick tree (or segment tree)

Counting inversions

Let's start from a simple problem.

You are given a permutation $$$a$$$ of length $$$n$$$. In one move, you can swap two elements in adjacent positions. What's the minimum number of moves required to sort the array?

Claim

The result $$$k$$$ is equal to the number of inversions, i.e. the pairs $$$(i, j)$$$ ($$$1 \leq i < j \leq n$$$) such that $$$a_i > a_j$$$.

Proof 1

Let $$$f(x)$$$ be the number of inversions after $$$x$$$ moves.
In one move, if you swap the values on positions $$$i, i + 1$$$, $$$f(x)$$$ either increases by $$$1$$$ or decreases by $$$1$$$. This is because the only pair $$$(a_i, a_j)$$$ whose relative order changed is $$$(a_i, a_{i+1})$$$. Since the sorted array has $$$0$$$ inversions, you need at least $$$k$$$ moves to sort the array.
For example, if you have the permutation $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ ($$$16$$$ inversions) and you swap two adjacent elements such that $$$a_i > a_{i+1}$$$ (getting, for example, $$$[2, 3, 7, 6, 8, 9, 1, 4, 5]$$$), the resulting array has $$$15$$$ inversions, and if you swap two adjacent elements such that $$$a_i < a_{i+1}$$$ (getting, for example, $$$[3, 2, 7, 8, 6, 9, 1, 4, 5]$$$), the resulting array has $$$17$$$ inversions.

On the other hand, if the array is not sorted you can always find an $$$i$$$ such that $$$a_i > a_{i+1}$$$, so you can sort the array in $$$k$$$ moves.

Proof 2

For each $$$x$$$, let $$$f(x)$$$ be the number of inversions if you consider only the elements from $$$1$$$ to $$$x$$$ in the permutation.
First, let's put $$$x$$$ at the end of the permutation: this requires $$$x - \text{pos}(x)$$$ moves. That's optimal (the actual proof is similar to Proof 1; in an intuitive way, if you put the last element to the end of the array, it doesn't interfere anymore with the other swaps).
For example, if you have the permutation $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ and you move the $$$9$$$ to the end, you get $$$[2, 3, 7, 8, 6, 1, 4, 5, 9]$$$ and now you need to sort $$$[2, 3, 7, 8, 6, 1, 4, 5]$$$. Hence, $$$f(x) = f(x-1) + x - \text{pos}(x)$$$. For each $$$x$$$, $$$x - \text{pos}(x)$$$ is actually the number of pairs $$$(i, j)$$$ ($$$1 \leq i < j \leq x$$$) such that $$$x = a_i > a_j$$$. So $$$f(x)$$$ is equal to the number of inversions.

Counting inversions in $$$O(n \log n)$$$

You can use a Fenwick tree (or a segment tree). There are other solutions (for example, using divide & conquer + merge sort), but they are usually harder to generalize.
For each $$$j$$$, calculate the number of $$$i < j$$$ such that $$$a_i > a_j$$$.
The Fenwick tree should contain the frequency of each value in $$$[1, n]$$$ in the prefix $$$[1, j - 1]$$$ of the array.
So, for each $$$j$$$, the queries look like

  • $$$res := res + \text{range_sum}(a_j + 1, n)$$$
  • add $$$1$$$ in the position $$$a_j$$$ of the Fenwick tree

Observations / slight variations of the problem

By using a Fenwick tree, you are actually calculating the number of inversions for each prefix of the array.

You can calculate the number of swaps required to sort an array (not necessarily a permutation, but for now let's assume that its elements are distinct) by compressing the values of the array. For example, the array $$$[13, 18, 34, 38, 28, 41, 5, 29, 30]$$$ becomes $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$.

You can also calculate the number of swaps required to get an array $$$b$$$ (for now let's assume that its elements are distinct) starting from $$$a$$$, by renaming the values. For example,
$$$a = [2, 3, 7, 8, 6, 9, 1, 4, 5], b = [9, 8, 5, 2, 1, 4, 7, 3, 6]$$$
is equivalent to
$$$a = [4, 8, 7, 2, 9, 1, 5, 6, 3], b = [1, 2, 3, 4, 5, 6, 7, 8, 9]$$$

$$$a^{-1}$$$ (a permutation such that $$$(a^{-1})_{a_x} = x$$$, i.e. $$$(a^{-1})_x$$$ is equal to the position of $$$x$$$ in $$$a$$$) has the same number of inversions as $$$a$$$. For example, $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ and $$$[7, 1, 2, 8, 9, 5, 3, 4, 6]$$$ have both $$$16$$$ inversions. Sketch of a proof: note that, when you swap two elements in adjacent positions in $$$a$$$, you are swapping two adjacent values in $$$a^{-1}$$$, and the number of inversions in $$$a^{-1}$$$ also increases by $$$1$$$ or decreases by $$$1$$$ (like in Proof 1).

1430E - String Reversal (rating: 1900)

Hint 1
Hint 2
Hint 3
Solution

103148B - Luna Likes Love (EGOI 2021/2)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

arc088_e (rating: 2231)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

arc097_e (rating: 2247)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

IOI 2019/1
arc120_c (suggested by Ghassane)
Hackerearth — Swapping numbers (Arceus03)
Hackerearth — Make the strings equal (Arceus03)
1526D - Kill Anton (somil_jain_120)
JOI 2021/3 (Final Round) (you can submit here)

Conclusions

We've seen that a lot of problems where you have to swap adjacent elements can be tackled with greedy observations, such as looking at the optimal relative positions of the values in the final array; then, a lot of these problems can be reduced to "find the number of inversions" or similar.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you have to swap adjacent elements.

I hope you enjoyed the blog!

Read more »

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

By TheScrasse, history, 3 months ago, In English

Hello everyone,
here is a very simple idea that can be useful for (cp) number theory problems, especially those concerning multiples, divisors, $$$\text{GCD}$$$ and $$$\text{LCM}$$$.

Prerequisites: basic knowledge of number theory (divisibility, $$$\text{GCD}$$$ and $$$\text{LCM}$$$ properties, prime sieve).

Idea

Let's start from a simple problem.

You are given $$$n$$$ pairs of positive integers $$$(a_i, b_i)$$$. Let $$$m$$$ be the maximum $$$a_i$$$. For each $$$k$$$, let $$$f(k)$$$ be the sum of the $$$b_i$$$ such that $$$k | a_i$$$. Output all pairs $$$(k, f(k))$$$ such that $$$f(k) > 0$$$.

An obvious preprocessing is to calculate, for each $$$k$$$, the sum of the $$$b_i$$$ such that $$$a_i = k$$$ (let's denote it as $$$g(k)$$$). Then, there are at least $$$3$$$ solutions to the problem.

Solution 1: $$$O(m\log m)$$$

For each $$$k$$$, $$$f(k) = \sum_{i=1}^{\lfloor m/k \rfloor} g(ik)$$$. The complexity is $$$O\left(m\left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{m}\right)\right) = O(m\log m)$$$.

Solution 2: $$$O(n\sqrt m)$$$

There are at most $$$n$$$ nonzero values of $$$g(k)$$$. For each one of them, find the divisors of $$$k$$$ in $$$O(\sqrt k)$$$ and, for each divisor $$$i$$$, let $$$f(i) := f(i) + g(k)$$$.
If $$$m$$$ is large, you may need to use a map to store the values of $$$f(k)$$$ but, as there are $$$O(n\sqrt[3] m)$$$ nonzero values of $$$f(k)$$$, the updates have a complexity of $$$O(n\sqrt[3] m \log(nm)) < O(n\sqrt m)$$$.

Solution 3: $$$O(m + n\sqrt[3] m)$$$

Build a linear prime sieve in $$$[1, m]$$$. For each nonzero value of $$$g(k)$$$, find the prime factors of $$$k$$$ using the sieve, then generate the divisors using a recursive function that finds the Cartesian product of the prime factors. Then, calculate the values of $$$f(k)$$$ like in solution 2.

Depending on the values of $$$n$$$ and $$$m$$$, one of these solutions can be more efficient than the others.

Even if the provided problem seems very specific, the ideas required to solve that task can be generalized to solve a lot of other problems.

1154G - Минимально возможный LCM

Hint 1
Hint 2
Hint 3
Solution

agc038_c - LCMs

Hint 1
Hint 2
Hint 3
Solution

Implementation (C++)

abc191_f - GCD or MIN

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

1493D - НОД массива (suggested by nor)
1436F - Сумма по подмножествам (nor)
Codechef — Chefsums (nor)

Conclusions

We've seen that this technique is very flexible. You can choose the complexity on the basis of the constraints, and $$$f(k)$$$ can be anything that can be updated fast.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems that can be solved with this technique.

I hope you enjoyed the blog!

Read more »

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

By TheScrasse, history, 8 months ago, In English

1485A - Add and Divide

Author: TheScrasse
Preparation: MyK_00L

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232596

1485B - Replace and Keep Sorted

Author: TheScrasse
Preparation: Keewrem

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 107232462

1485C - Floor and Mod

Authors: isaf27, TheScrasse
Preparation: Keewrem

Hint 1
Hint 2
Solution

Official solution: 107232416

1485D - Multiples and Power Differences

Author: TheScrasse
Preparation: MyK_00L

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232359

1485E - Move and Swap

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232216

1485F - Copy or Prefix Sum

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232144

Read more »

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

By TheScrasse, history, 9 months ago, In English

It's quite weird that $$$11$$$ submissions are still running from at least $$$20$$$ minutes, while hundreds of submissions (even with long execution times) are usually evaluated in a few seconds. It seems that the last tests run much more slowly than the other tests. Does anyone know why it happens?

Image

Read more »

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

By TheScrasse, history, 10 months ago, In English

As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2).

1438A - Specific Tastes of Andre

Hint 1

1438B - Valerii Against Everyone

Hint 1

1438C - Engineer Artem

Hint 1

1438D - Powerful Ksenia

Hint 1

I wasn't able to solve E and F. If you did, you may want to add your hints in the comments.

Also, please send a feedback if the hints are unclear or if they spoil the solution too much.

Read more »

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

By TheScrasse, history, 11 months ago, In English

Hello everyone,

inspired by Looking for a Challenge, I was thinking about publishing periodically (maybe every month) a selection of about 10 problems of various difficulties (from 1500 to 2400) from the Codeforces problemset, with hints and a detailed explanation of the solution. I will try to:

  • choose "good" problems: avoid putting too many ad-hoc problems, avoid putting problems that require lengthy data structures;
  • write the tutorial as accurately as possible: of course I won't copy-paste the official editorial, instead I will try to follow the thinking process "problem -> solution".

Do you think this is a good idea? (or is it "yet another editorial"?) How should I publish the problems? (pdf? blog on codeforces?) Do you have any suggestions?

UPD1: I would like to put problems that you've not solved yet. If you're interested, please compile this form with your Codeforces handle. By using the Codeforces API, I will minimize problems that you've already solved.

UPD2: after reading the comments, I thought for a long time about what to do and I asked myself if my idea makes sense. In particular:

  • selection of good problems: most problems in recent contests are good, most good problems are in recent contests.
  • editorials: sometimes the order of the ideas can appear confusing but, if the problem isn't much harder than your current level, you should come up with the solution by using the editorial + the comment section + solutions by other people.

So I'm not sure about the usefulness of writing new editorials to past problems.

Instead, I will write nested hints (of the problems that I have solved) after the end of each contest, and I will try to publish them immediately after the contest: I think they are much more useful, in fact they are often asked in the comment section.

Read more »

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

By TheScrasse, history, 14 months ago, In English

Hello,
I'm just curious to know if you have ever failed a system test, and what was the problem in your code.
I have failed a system test twice.

1) 1312C - Adding Powers, submission 72808639 (wrong answer on test 44)
Here is part of my code:

cin >> t;
while (t--) {
    s = 0;
    // [...]
    while (s != 0) {
        c = 0;
        // [...]
    }
    if (c == 2) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

What's the reason of my wrong answer? If at the end of a testcase c is equal to 2 and in the next testcase s == 0, I don't enter the second while loop and c remains equal to 2! Instead, I should have reset c before entering the second while.
In fact, my solution got wa on the test

2
2 9
0 18
4 100
0 0 0 0

In the second testcase, output should have been YES, but my code printed NO because the sum s of the given integers was equal to 0 and c remained equal to 2.

2) 1334D - Minimum Euler Cycle, submission 76160539 (wrong answer on test 19)
My code was really messy, I still don't know what's the reason of the wrong answer.

And you? Have you ever failed a system test (or have you been hacked) because of some silly reason?

Read more »

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

By TheScrasse, history, 15 months ago, In English

Hi everyone,

many people are a bit disappointed because, for example, while the most difficult problems of Div. 3 contests are still interesting for Div. 2, Div. 3 contests are unrated for higher divisions. The same argument is valid for Div. 2 and Div. 4 contests.

An idea could be make contests rated for everyone, but that's not the best solution because, to reach a $$$\geq 1900$$$ rating, solving Div. 3 and Div. 4 problems very fast would be enough.

An improvement could be make contests partially rated for higher divisions, that is, the rating variation is multiplied by a $$$k$$$ factor ($$$0 \leq k \leq 1$$$) that depends on the target division of the contest and on the initial rating of the contestant (i. e. the relevance of that contest for that contestant). An example: there's a Div. 2 contest, then $$$k$$$ could be $$$1$$$ for a $$$1900$$$ rated contestant, $$$0.8$$$ for a $$$2100$$$ rated contestant, $$$0.5$$$ for a $$$2200$$$ rated contestant, etc.

Read more »

 
 
 
 
  • Vote: I like it
  • -33
  • Vote: I do not like it

By TheScrasse, history, 16 months ago, In English

Hello,
I noticed that I often overcomplicate problems, hence my codes are often very long and I lose precious time during contests.
Some examples:
70077990 I wrote a sliding window minimum, but it wasn't necessary since $$$O(n^2)$$$ is fast enough with those constraints.
79841706 I found a solution that required too much memory. My "optimization" is 90 lines long. That problem can be solved in 30 lines.
79880987 I used a dfs and a 0-1 bfs (120 lines), a single bfs was enough.
Overall, I find difficult to improve a solution that seems already feasible.
Could you give some advice about how to stop overcomplicating problems?

Read more »

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

By TheScrasse, history, 16 months ago, In English

I can't submit solutions to any problem. This error appears: HTTP Status 403 – Forbidden
UPD: nvm, now I can submit, but there is a long queue

Read more »

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

By TheScrasse, history, 17 months ago, In English

Hello, I think 1343E - Weights Distributing wasn't a very difficult task, and now it's been solved by almost 2000 people. So, why is it worth 2400 points on the Problemset? How is the difficulty of a problem calculated?

Read more »

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

By TheScrasse, history, 17 months ago, In English

Hello everyone,
I have just tried to execute this code:

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

long long n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ifstream cin("output.txt");
    ofstream cout("output.txt");

    cout << 0 << endl;
    while (cin >> n) {
        cout << n + 1 << endl;
    }

    return 0;
}

(note ifstream cin("output.txt");)
The output is

0

Shouldn't this code enter an infinite loop? cin >> n should be always true because the code has written a new line on output.txt.

Read more »

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

By TheScrasse, history, 18 months ago, In English

Hi everyone, I have just tried to solve the problem 161D.
If I use a matrix dp[50010][510], I get a tle verdict, even if the time complexity of the solution is $$$O(nk)$$$, $$$nk < 10^8$$$ and the constant factors are quite small. But if I use a matrix dp[510][50010] and I swap the indices, I get ac with a time of 498 ms (much less than the time limit).
Why does it happen?
Thanks

Submission with tle verdict: 73781168
Submission with ac verdict: 73781989

Read more »

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