Топ постов
Автор Supermagzzz, история, 45 часов назад,

1538A - Каменная игра

Автор задачи: MikeMirzayanov

Разбор
Решение

1538B - Друзья и конфеты

Автор задачи: MikeMirzayanov

Разбор
Решение

1538C - Количество пар

Автор задачи: MikeMirzayanov

Разбор
Решение

1538D - Еще одна задача про деление чисел

Автор задачи: MikeMirzayanov

Разбор
Решение

1538E - Смешные подстроки

Автор задачи: MikeMirzayanov

Разбор
Решение

1538F - Интересная функция

Автор задачи: Supermagzzz, Stepavly

Разбор
Решение

1538G - Подарочный набор

Автор задачи: MikeMirzayanov

Разбор
Решение

Полный текст »

Разбор задач Codeforces Round #725 (Div. 3)

• +37

Автор gavy_pole, история, 19 часов назад,

For the Codeforces Round #725 (Div. 3), check these two submissions: 119070732 and 119073742. These two codes are 99% similar. My question is how come these same submissions (template aside) didn't get skipped? MikeMirzayanov, please look into this.
Anyway, these guys are new type of cheaters. They cheat by exchanging codes and this is not the first time. For further proof, check these two as well: 119047376 and 119057342 (the function is same and only variables are changed). They have plagiarised in Codechef contests as well (obviously) but that's another story for another time.
So would you like to explain your actions, lordgavy01 and south_pole? What do you gain from this?

Полный текст »

• +39

Автор kashyapriya754, 24 часа назад,

****I request the cheaters to please somehow let me know the rating of their real father whose code they copy , so that i can make a target to surpass him and won’t have to be bothered by such dumbfucks again?

Полный текст »

• +103

Автор regex0754, 3 дня назад,

Hello Codeforces,

RECursion, the coding community of NIT Durgapur, is organizing an ACM-ICPC style-based contest ALOHOMORA. The contest will be held on 11th June at 21:30 IST.

The contest will be held on the CodeChef platform. There will be 8 problems which are to be solved in 2 hours and 30 minutes.

Participants need to register themselves in teams of 3 (maximum).

Prizes:
Cash Prizes worth ₹5K and ₹3K for Top 2 Performing Teams
Cash Prize worth ₹2K for Top Performing Indian Team
250 CodeChef Laddus for Top 3 Performing Teams

Exciting Goodies from Digital Ocean for Top 3 Performing Teams from NIT Durgapur
100 CodeChef Laddus for Top Performing Team from NIT Durgapur

Certificates and Coupons worth ₹10K from AlgoZenith for all Top Performing Teams

For further information, contact:
Nikhil Vashistha: +91 9835274836
Anupam Singh: +91 7054394459

Полный текст »

• +113

Автор Radewoosh, история, 3 дня назад,

Hello Codeforces!

As all of you know, there are so many known algorithms named after people who invented them — from the easiest ones, like Dijkstra, to the harder ones, like Berlekamp–Massey algorithm. These algorithms were innovative when they were invented, so of course, it's good that they are named after their inventors.

But, today, I've seen a blog about the solution to the problem "compute LCS of two strings in time $O((n + k) \cdot \log(k))$, where $n$ is the sum of lengths of the strings, and $k$ is the number of pairs of matching positions in them". To be honest, it a bit pissed me off that even this algorithm is named after its creators. Is it ok to name the solution to every possible problem after its author? I won't judge it. Anyway, I want my very own Radecki algorithm, so let me give it a try. If anyone has ever heard about it — it's cool. Let me know, and it'll be just another helpful blog on Codeforces.

Let's imagine the following problem: there is a directed graph on $n$ vertices without any edges and a list of $m$ directed edges which we want to add to this graph one by one. After adding each edge, we want to have full information about the strongly connected components. Know the number of strongly connected components, be able to tell whether two vertices are in the same connected component or even make this information persistent. Critical condition: the list of edges is given in advance.

So, for a few years, I'm able to solve this problem, but people told me that it's rather boring and it's not worth to write a paper about it. Anyway, let me give it a try.

Let's use the divide and conquer technique on the list of the edges. We can also think about it like about divide and conquer over the timeline. So, let's assume that we have some function $rec(a, b, edges)$, where $a$ is the start of the time interval, $b$ is the end (we can assume that both are inclusive, doesn't matter, I'm still pissed a bit) and $edges$ is the list of edges together with the times when they're added. We start the process like $rec(0, m-1, everything)$.

Everytime we should look at the middle of the time interval, so let's compute $s=\lfloor \frac{a+b}{2} \rfloor$. Let's use the standard offline algorithm to calculate strongly connected components in the graph which consists only of the edges from $edges$ which were added before $s$ or exactly at $s$. We want to split recursively somehow, but how to do it to keep good complexity? It turns out that in the moments after $s$ all the SCC that we've just calculated will stay connected. So, we can merge whole components into single vertices and only pass to the right edges connecting vertices from different strongly connected components. Also, the edges that are now connecting different connected components were useless in the past, which means that we can pass to the left the rest of the edges. In this way, each edge will occur once at every level of the recurrence, there are $O(\log(m))$ levels, and in each level the overall complexity is linear, thus we have $O(m \cdot \log(m))$ complexity (if we implement it carefully enough to have no extra logs).

What should we take from the recurrence? The simplest idea: at each call of the $rec$ function, for each edge, push some information to some global data structure. My idea is to for each edge that connects vertices from the same strongly connected component push information "these two vertices are in the same strongly connected component at this time". This gives us something which we can interpret as a graph of undirected weighted edges. It's easy to see that we are only interested in its MST (the graph has $n$ vertices and $O(m \cdot \log m)$ edges with weights from $0$ to $m-1$, we can calculate it's MST in $O(m \cdot \log(m))$ time).

What can we do now with this information? We can answer queries like "What's the moment when vertices $a$ and $b$ start belonging to the same strongly connected component?" Yep, that's the maximum value on the path between these two vertices.

Clear? Clear.

Cool? As f**k.

Easy to implement? So so, easy to copy-paste and use. My implementation (without computing MST, just getting the list of undirected edges) has 72 lines.

New? That's a tough question. I know that it was on the prime new year contest 2018, which took place between 2018 and 2019, which tells that this problem was created in 2018. Even if the intended solution is the same as mine, here comes a twist: link. This is the problem authored by me in July 2017. I know, just a pdf is worth nothing, but it's possible to dig deeper and believe me: the solution implemented here is the same as described.

Lest thoughts: the resulting tree is really similar to Gomory-Hu tree (because of minimums/maximums on the paths).

Полный текст »

• +477

Автор Maksim1744, 47 часов назад,

Some time ago I read this post about calculating prime-counting function in $O(n^{3/4})$ (you have to solve problem 10 to access the post). And in the end author mentioned that there is $O(n^{2/3})$ solution. To my surprise I was not able to find any more or less relevant information on the internet about that. Maybe there is a beautiful blog describing all of this on 10-th page of google, but I decided to collect information I found in this post.

### $\tilde O(n^{3/4})$

Let's start with $O(n^{3/4})$ approach from Project Euler. We will need some definitions:

• $\pi(n)$ — prime counting function, i.e. number of primes which are not greater than $n$.
• $S(n, a)$ — suppose we take all numbers from $1$ to $n$ and sieve them with first $a$ primes. Then $S(n, a)$ is the number of numbers which are preserved after this. In particular, $S(n, 0) = n$ and $S(n, \infty) = \pi(n) + 1$ (we always count $1$).
• $p_a$ — $a$-th prime.

One can see that there is a recurrence relation for $S$: $S(n, a) = S(n, a - 1) - \left[S\left(\left\lfloor \frac{n}{p_a}\right\rfloor, a - 1\right) - a \right]$, since while sieving with $p_a$ we will mark all numbers which have $p_a$ as their smallest prime divisor, so we can divide them by $p_a$ and take value $S\left(\left\lfloor \frac{n}{p_a}\right\rfloor, a - 1\right)$. But now we are overcounting, because in this $S$ there are primes before $p_a$ (as well as number $1$), and we don't need to count them, so we are subtracting $a$.

Another fact is that $S(n, \pi(\left\lfloor \sqrt n\right\rfloor)) = S(n, \infty) = \pi(n) + 1$, since we don't need to sieve with primes greater than $\sqrt n$.

You can see that if we just do this recursion, every call to $S$ will be of the form $S\left(\left\lfloor \frac {n}{k} \right\rfloor , a\right)$ where $k$ is an integer. And there are at most $2\sqrt n$ possible values of $\left\lfloor \frac {n}{k} \right\rfloor$, because either $k \leqslant \sqrt n$, or $\frac nk \leqslant \sqrt n$, let $V$ be the set of all possible values.

All this leads to dynamic programming solution: let's keep array $dp[m]$ for all $m \in V$. Initially we will store $dp[m] = S(m, 0) = m$, and after $i$-th iteration of our algorithm we will want to store $S(m, i)$ in $dp$. To recalculate $dp$ in-place, go from largest $m$ to smallest and apply recursive formula from above. But now we need to do around $\sqrt n$ iterations, each time update array $dp$ of size $\sqrt n$, seems like $\Theta(n)$. However, we don't need to update $dp[m]$ if $m < p_i^2$, so we just stop current iteration as soon as we meet that condition.

With this we can finally calculate the complexity. Let's fix some integer $y$ around $n^{1/4}$ (we will calculate it later). For $p_i < y$ there are $\pi(y)$ iterations which take $O(n^{1/2}\pi(y))$ time, which is the same as $O\left(n^{1/2}\frac{y}{\log y}\right)$. For other part, let's first rewrite stopping condition a bit: \begin{gather*} m < p_i^2, \,\, m = \left\lfloor\frac{n}{k}\right\rfloor \Rightarrow k < \frac{n}{p_i^2} \end{gather*}

So we will complete $i$-th iteration in $O\left(\frac{n}{p_i^2}\right)$ time, and when we add all of this: \begin{gather*} \sum_{\substack{y < p_i \leqslant n \\ \text{$p_i$ is prime}}} \frac{n}{p_i^2} \leqslant \sum_{y < p_i \leqslant n} \frac{n}{p_i^2} = \sum_{p = y}^{n} \frac{n}{p^2} \approx \int_{x=y}^n \frac{n}{x^2} dx = -\frac{n}{x}\Big|_{y}^n = O\left(\frac{n}{y}\right) \end{gather*}

Resulting complexity will be $O\left(n^{1/2}\frac{y}{\log y} + \frac{n}{y}\right)$, which is $O\left(\frac{n^{3/4}}{\log^{1/2} n}\right)$ with $y = n^{1/4}\log^{1/2}n$.

Implementation

As a bonus, you get array $dp$ which gives you $\pi\left(\left\lfloor\frac nk \right\rfloor\right)$ for any $k \geqslant 1$, which you can use later in some other dynamic programming on top of it.

### $\tilde O(n^{2/3})$

I will use the same definitions, except that I will modify $S$ a little bit:

• $\varphi(n, a)$ — number of integers in $[1;\,n]$ such that they are not divisible by any prime among first $a$ primes. The difference with $S$ is that $\varphi$ doesn't count primes (but still counts $1$).

For this function there is a similar recurrence relation: $\varphi(n, a) = \varphi(n, a - 1) - \varphi\left(\left\lfloor \frac{n}{p_a} \right\rfloor, a - 1\right)$.

Let's take some integer $\sqrt[3]{n} \leqslant y \leqslant \sqrt{n}$ (we will set it to $\sqrt[3]{n}\log^{?}n$ in the end). Let's write $\pi(n)$ as \begin{gather*} \pi(n) = \varphi(n, \pi(y)) + \pi(y) — F — 1 \end{gather*}

Here $F$ is the number of integers in $[1; n]$ which can be expressed as $pq$ for primes $p$ and $q$ with $p \geqslant q > y$.

To calculate $F$ we can use linear sieve up to $\frac{n}{y}$ to find all primes and then calculate $F$ using two pointers. Using sieve we can also calculate $\pi(y)$.

We will calculate $\varphi(n, \pi(y))$ using recursion. But let's stop recursion when we call $\varphi(m, a)$ with $m \leqslant \frac{n}{y}$ and deal with this later. Now every other recursion call has a form of $\varphi\left(\left\lfloor \frac{n}{k}\right \rfloor , a\right)$ for $a \leqslant \pi(y)$ and $k < y$. So there will be no more than $O(y \pi(y))$ calls of this type, which according to the distribution of primes is the same as $O\left(\frac{y^2}{\log y}\right) = O\left(\frac{y^2}{\log n}\right)$.

For the other part first notice, that we don't actually have to pass result back through the recursion. Every time we go deeper into the recursion, it's enough to maintain current sign. In other words, this means that for any call $\varphi(m, a)$ with $m \leqslant \frac ny$ we can just save it as triple $(m, a, sign)$ and then add $\varphi(m, a) \times sign$ to the answer. To calculate it, notice that with linear sieve we can get smallest prime divisor for each number up to $\frac{n}{y}$. So if we store these prime divisors in array $mn[n]$, $\varphi(m, a)$ will be equal to the number of indices $i \in [1;\,m]$ such that $mn[i] > p_a$ (here we assume that $mn[1] = +\infty$). This can be easily done offline in $O\left(\frac{n}{y} \log\frac{n}{y}\right) = O\left(\frac{n}{y} \log n\right)$ with fenwick tree by sorting triples by $m$ and doing standard sum-in-a-rectangle queries.

Total complexity is $O\left(\frac{y^2}{\log n} + \frac{n}{y} \log n\right)$, which is optimal for $y = n^{1/3}\log^{2/3} n$, resulting in a total complexity of $O(n^{2/3}\log^{1/3}n)$.

Implementation

### Benchmarks

Both implementations are verified on Library-Checker

$n$ $10^{10}$ $10^{11}$ $10^{12}$ $10^{13}$
$\tilde O(n^{3/4})$ link 0.147s 0.763s 3.890s 20.553s*
$\tilde O(n^{2/3})$ link 0.045s 0.200s 0.914s 4.372s

* — this didn't fit in ideone limit, so I ran it locally and estimated time on ideone based on ratio on other tests.

### Bonus — sum of primes

It's easy to see that you can find sum of primes up to $n$ using same ideas, or even sum of squares of primes, or sum of cubes, etc. For $\tilde O(n^{3/4})$ I already implemented it here, for $\tilde O(n^{2/3})$ this is left as an exercise for a reader :)

### Practice problems

Thanks to sgtlaugh for the comment with practice problems!

P.S. If you notice any mistakes or typos, let me know

Полный текст »

• +310

Автор adnan_toky, история, 3 дня назад,

• +221

Автор Satwik_Mishra1, история, 37 часов назад,

This is to seek help from Experienced people on how to Improve,I have been regularly solving problrms from a long time now and I do try to appear In virtual contests almost daily. So is there some mistake in my practising strategy. If so please help me out. You may visit my profile for reference. thanks in advance.

Полный текст »

• +2

Автор sus, история, 3 дня назад,

I have set a reminder on my cloud (meaning if I get a new device I will still receive the reminder) to comment on this blog in 5 years, then 10 years. Doing so will bring it back up in recent actions and in turn create a time capsule of sorts. This means that the rankings for the top 30 rated and contributors will be different and we can compare the two. Unfortunately, this wasn't done in the past for CF during the early days 11-10 years ago and most of the information from that time period is just legend. I hope that this will bring some sort of reaction out of your future selves and prompt you to think back on the past. Comment something below so you too can be a part of this experience and cf history.

(also congrats Radewoosh for recently achieving top 1 on the site, something I heard you aimed to do from years ago)

Полный текст »

• +138

Автор maroonrk, история, 28 часов назад,

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2021（AtCoder Regular Contest 122).

The point values will be 400-500-600-700-800-1200.

We are looking forward to your participation!

Полный текст »

• +90