Thanks a lot!

for Your participation

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

• task authors and developers: Vasilyev daubi Alexey, Denis Kapt Mustafin, Ivan __silaedr__ Podvorniy, Ilya ilyakrasnovv Krasnov, Evgenii pakhomovee Pakhomov, Mikhail MadProgrammer Zaytsev.

• to the wonderful teachers who made this round happen: Pavel PavelKunyavskiy Kunyavskiy, Dmitriy cdkrot Sayutin, Alesya AlesyaIvanova Ivanova, Konstantin kokokostya Makhnev

• Monogon for the great coordination, valuable advice, and patience

• KAN for the help during preparation of the contest

• Qwerty1232 for the help with the editorial

• testers for good proposals and important feedback: glebustim, kclee2172, AndreyPavlov, generic_placeholder_name, nor, TheScrasse, qualdoom, AlperenT, FairyWinx, vdv09, NToneE, KseniaShk, prost_sasha, agrayush13, kartikeyasri23, SomethingNew, and especially mejiamejia

• MikeMirzayanov and geranazavr555 for codeforces and polygon platform

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:

1. william556
2. fursuit
3. huge_waxberry
4. lbwhangbeateveryone
5. Longiseta

All participants:

1. jiangly
2. kotatsugame
3. hitonanode
4. ksun48
5. Rubikun

Hello, Сodeforces!

We are very grateful for Your participation in our round.

Thanks to Qwerty1232 for the help with this editorial.

1715A - Crossmarket

• С++ code: 169161824
• Python code: 169161508
• Kotlin code: 169161674

1715B - Beautiful Array

• С++ code: 169162178
• Python code: 169161968

1715C - Monoblock

• С++ сode: 169162300

1715D - 2+ doors

• С++ сode: 169162393

1715E - Long Way Home

• С++ сode: 169162508

1715F - Crop Squares

• С++ сode: 169162576

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

Video-tutorial by ak2006

Solution: 147513934

Video-tutorial by ak2006

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

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__, daubi, alegsandyr, ilyakrasnovv, and isaf27.

We are very thankful to

• isaf27 for the great coordination, valuable advice, and patience.

• Renatyss, stepanov.aa, talant, Siberian, kirill.kligunov, arbuzick for the help during discussing and preparing problems.

• Our testers: AlperenT, ArtNext, EvgeniyPonasenkov, FedShat, Qwerty1232, TeaTime, TheEvilBird, ak2006, generic_placeholder_name, philmol, silvvasil, tox1c_kid for their feedback

• pakhomovee for the task, that didn't find its place in the final problemset.

• KAN for helping with round preparation

• MikeMirzayanov for codeforces and polygon platform

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$$$

UPD — Editorial

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);
            }
        }
    }
}