Please read the new rule regarding the restriction on the use of AI tools. ×

ilyakrasnovv's blog

By ilyakrasnovv, 2 years ago, translation, In English

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

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

Full text and comments »

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

By ilyakrasnovv, 2 years ago, translation, In English

Hello, Сodeforces!

We are very grateful for Your participation in our round.

Thanks to Qwerty1232 for the help with this editorial.

1715A - Crossmarket

Advice #0
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

Advice #0
Hint #1
Hint #2
Hint #3
Solution

Full text and comments »

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

By ilyakrasnovv, 3 years ago, In English

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!

Tutorial is loading...

Solution: 147513897

Tutorial is loading...

Video-tutorial by ak2006

Solution: 147513934

Tutorial is loading...

Video-tutorial by ak2006

Solution: 147513962

Vector solution: 147513974

Tutorial is loading...

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

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

Tutorial is loading...

Solution: 147514055

Set solution: 147514064

Tutorial is loading...

Solution: 147514090

Bitset solution: 147514108

Tutorial is loading...

Solution: 147514167

Tutorial is loading...

Solution: 147662463

Full text and comments »

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

By ilyakrasnovv, 3 years ago, translation, In English

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

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

Full text and comments »

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

By ilyakrasnovv, 3 years ago, translation, In English

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

Full text and comments »

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