### ilyakrasnovv's blog

By ilyakrasnovv, 6 months ago, translation,

# Thanks a lot!

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round #816 (Div. 2), which will be held on Aug/20/2022 17:35 (Moscow time). The round will be rated only for the second division. You will have 6 tasks and 2 hours to solve them. We recommend you read all the problems.

Round is completely set by winter SIS (Summer Informatics School) students. During the camp we did our best to prepare interesting and creative problems. You can check previous rounds prepared by SIS students: Codeforces Round #815 (Div. 2), Codeforces Round #694, Codeforces Round #612, Codeforces Round #530

We are very thankful to

Scoring distribution will be released before the contest begins

We hope that You will participate in our round, as well as in SIS!

Good luck and have fun!

UPD — Scoring distribution:

$500 - 1000 - 1750 - 2250 - 2750 - 3000$

The contest may contain interactive problems! Make sure to read this post.

UPD 2 — Editorial is out!

UPD 3 — Congratulations to the winners!

Official participants:

All participants:

• +703

By ilyakrasnovv, 7 months ago, translation,

Hello, Сodeforces!

We are very grateful for Your participation in our round.

Thanks to Qwerty1232 for the help with this editorial.

1715A - Crossmarket

Hint #1
Hint #2
Hint #3
Solution

1715B - Beautiful Array

Hint #1
Hint #2
Hint #3
Solution

1715C - Monoblock

Hint #1
Hint #2
Hint #3
Solution

1715D - 2+ doors

Hint #1
Hint #2
Hint #3
Solution

1715E - Long Way Home

Hint 1
Hint 2
Hint 3
Solution

1715F - Crop Squares

Hint #1
Hint #2
Hint #3
Solution

• +204

By ilyakrasnovv, 11 months ago,

Hello, codeforces!

We deeply apologize for the weak pretests in the problem 1642C - Great Sequence. Anyway, we believe that you liked at least one problem from the contest :)

Thanks to Mangooste for the problem 1641E - Special Positions!

Solution: 147513897

Solution: 147513934

Solution: 147513962

Vector solution: 147513974

$\mathcal{O}(2n^2)$ insertions solution: 147514019

$\mathcal{O}(n^2)$ insertions solution: 147514028

Solution: 147514055

Set solution: 147514064

Solution: 147514090

Bitset solution: 147514108

Solution: 147514167

Solution: 147662463

• +363

By ilyakrasnovv, 11 months ago, translation,

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round #773 (Div. 1) and Codeforces Round #773 (Div. 2), which will be held on Feb/23/2022 13:10 (Moscow time). Notice the unusual time! The round will be rated for both divisions. Each division will have 6 problems, and you will have 2 hours to solve them. We recommend you read all the problems!

Tasks are based on RocketOlymp, and were written and prepared by __silaedr__, Allvik06, alegsandyr, ilyakrasnovv, and isaf27.

We are very thankful to

Olympiad's participants cannot participate in codeforces rounds simultaneously.

Good luck and have fun!

UPD — Scoring distribution:

div2: $500 - 750 - 1250 - 2000 - 2000 - 2500$

div1: $500 - 1250 - 1250 - 1750 - 2250 - 3000$

UPDEditorial

• +53

By ilyakrasnovv, 21 month(s) ago, translation,

## Special case — 1-2-BFS

The task: we are given a weighted directed graph, where weight of every edge is in range $[1;2)$. We have to find shortest path from vertex $st$ to all the others.

Solution: for every integer in range from $0$ to $2n - 1$ we will store a queue of vertices (let the $i$-th queue be $q_i$). In $i$-th queue there will be all the vertexes, distance to which is $\lfloor i \rfloor$ (and some vertexes with smaller distance). To calculate this, we will do it layer-by-layer.

c++ realisation:

for (int i = 0; i < 2 * n; ++i) {
for (int v : q[i]) {
for (pair<int, double> e : g[v]) {
if (dist[e.first] > dist[v] + e.second) { // dist -- distance from st to all the others
dist[e.first] = dist[v] + e.second;
q[floor(dist[e.first])].push_back(e.first);
}
}
}
}


Proof:

Base: $q_0$ ans $q_1$ are calculated correctly.

Assumption: for $x \ge 1$ all the layers $q_0, q_1, ..., q_x$ are calculated correctly, and distances to vertices in them are also calculated correctly.

Transition: then layer $q_{x + 1}$ will be calculated correctly, and distances to vertices in it are also calculated correctly:

Let's choose any vertex v, so $\lfloor dist_v \rfloor = x + 1$. It couldn't appear in previous layers, but it will be in layer $x + 1$, because previous vertex on the path from $st$ to $v$ must be in layers $x - 1$ or $x$. They are calculated correctly, thus during one of relaxations our vertex will appear in layer $x + 1$ with correct distance to $st$.

Asymptotic: $\mathcal{O}(n + m)$, where n — is number of vertices, and m — is number of edges.

Comment: it is obvious, that you can do the same optimisation as in 1-k bfs and store only 3 layers, but the code provided is easier to understand.

## A-2A-BFS

The difference from previous task is that edges' weigths are in range $[A; 2A)$, where $A > 0$. But it is very easy to solve it using previous solution — we just have to divide all weights by A. Important notice is that errors may appear with calculations using doubles, so we should avoid them if it is possible. In that case we can multiply A and all weights by some number, so all of them are integers, and then simply add vertices to the layer dist[v] / A.

Code for case, where all the weights are integers:

for (int i = 0; i < 2 * n; ++i) {
for (int v : q[i]) {
for (pair<int, int> e : g[v]) {
if (dist[e.first] > dist[v] + e.second) {
dist[e.first] = dist[v] + e.second;
q[dist[e.first] / A].push_back(e.first);
}
}
}
}

We remember...

• +82