Привет! В 18.02.2024 15:05 (Московское время) начнётся Codeforces Round 927 (Div. 3) — очередной Codeforces раунд для третьего дивизиона.

В раунде используются задачи JetBrains Academy Youth Challenge. Если вы участвовали в нем, не участвуйте в этом раунде.

Задачи подготовлены denk, step_by_step, goncharovmike, ikrpprppp, pashka, Vladosiya и MikeMirzayanov.

Большое спасибо awoo, BledDest, buyolitsez, EgorUlin, Gojova, GrandFruit, Hello_zoka, petyb, scanhex, senjougaharin, shnirelman, SomethingNew, Toy_mouse, Zandler за тестирование раунда.

Как обычно для раундов третьего дивизиона:

• в раунде будет 6-8 задач
• длительность раунда 2 часа 15 минут
• раунд проходит по правилам ICPC, штраф за неверную попытку 10 минут
• раунд рейтинговый для участников с рейтингами до 1600
• после раунда будет 12-часовая фаза открытых взломов

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

• принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
• не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Всем удачи!

UPD: Разбор

1921A - Square

Идея: goncharovmike, разработка: pashka

t = int(input())
for _ in range(t):
    a = [[int(x) for x in input().split()] for i in range(4)]
    x = [p[0] for p in a]
    dx = max(x) - min(x)
    print(dx * dx)

1921B - Arranging Cats

Идея: pashka, разработка: ikrpprppp

t = int(input())

for _ in range(t):
    n = int(input())
    start = [int(x) for x in input()]
    finish = [int(x) for x in input()]
    pairs = list(zip(start, finish))
    add_amnt = sum(int(a < b) for a, b in pairs)
    rmv_amnt = sum(int(a > b) for a, b in pairs)
    print(max(add_amnt, rmv_amnt))

1921C - Sending Messages

Идея: step_by_step, разработка: step_by_step, Vladosiya

t = int(input())
for _ in range(t):
    n, f, a, b = map(int, input().split())
    m = [0] + [int(x) for x in input().split()]
    for i in range(1, n + 1):
        f -= min(a * (m[i] - m[i - 1]), b)
    print('YES' if f > 0 else 'NO')

1921D - Very Different Array

Идея: Vitaly503, разработка: pashka

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

struct test {
   void solve() {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector<int> b(m);
        for (int i = 0; i < m; i++) cin >> b[i];
        sort(a.begin(), a.end());
        sort(b.rbegin(), b.rend());
        vector<int> c(n);
        long long s = 0;
        for (int i = 0; i < n; i++) {
            c[i] = b[m &mdash; n + i];
            s += abs(c[i] &mdash; a[i]);
        }
        long long res = 0;
        for (int k = 0; k <= n; k++) {
            res = max(res, s);
            if (k < n) {
                s -= abs(c[k] &mdash; a[k]);
                c[k] = b[k];
                s += abs(c[k] &mdash; a[k]);
            }
        }
        cout << res << "\n";
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }
    return 0;
}

1921E - Eat the Chip

Идея: ikrpprppp, разработка: ikrpprppp

def solve():
    h, w, xA, yA, xB, yB = map(int, input().split())

    if (xA - xB) % 2 == 0:
        winner = "Bob"
        if xA >= xB:
            win = False
        elif yA == yB:
            win = True
        else:
            if yA < yB:
                n_turns = yB - 1
            else:
                n_turns = w - yB
            win = xB - 2 * n_turns >= xA

    else:
        winner = "Alice"

        xA += 1
        yA += 0 if yB - yA == 0 else 1 if yB - yA > 0 else -1

        if xA > xB:
            win = False
        elif yA == yB:
            win = True
        else:
            if yA < yB:
                n_turns = w - yA
            else:
                n_turns = yA - 1
            win = xB - 2 * n_turns >= xA

    print(winner if win else "Draw")


t = int(input())

for _ in range(t):
    solve()

1921F - Sum of Progression

Идея: Vitaly503, разработка: Vitaly503

#include <bits/stdc++.h>

using namespace std;

long long precalc[322][200322];
long long precalci[322][200322];

void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    int pivot = 1;
    while (pivot * pivot < n) {
        pivot++;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < pivot; i++) {
        for (int j = 0; j <= i; j++) {
            precalc[i][j] = 0LL;
            precalci[i][j] = 0LL;
        }
        for (int j = 0; j < n; j++) {
            precalci[i][j + i + 1] = precalci[i][j] + a[j] * (j / (i + 1) + 1);
            precalc[i][j + i + 1] = precalc[i][j] + a[j];
        }
    }
    while (q--) {
        int s, d;
        long long k;
        long long ans = 0;
        cin >> s >> d >> k;
        s--;
        if (d > pivot) {
            for (int i = s; i <= s + (k - 1) * d; i += d) {
                ans += a[i] * ((i - s) / d + 1);
            }
            cout << ans << " ";
            continue;
        }
        long long last = s + d * k - d;
        int first = s;
        cout << precalci[d - 1][last + d] - precalci[d - 1][first] -
                (precalc[d - 1][last + d] - precalc[d - 1][first]) * (first / d) << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
        if (tests) cout << "\n";
    }
    return 0;
}

1921G - Mischievous Shooter

Идея: Vitaly503, разработка: goncharovmike

//ciao_chill
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n, m, k;
vector<vector<int>> a;


bool prov(int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < m;
}

int ans() {
    int cnt = 0;
    int dp[n][m];
    int pref[n][m];
    int pref_up[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pref_up[i][j] = a[i][j];
            if (prov(i - 1, j))
                pref_up[i][j] += pref_up[i - 1][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            pref[i][j] = a[i][j];
            if (prov(i - 1, j + 1))
                pref[i][j] += pref[i - 1][j + 1];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = pref_up[i][j];
            if (prov(i - k, j))
                dp[i][j] -= pref_up[i - k][j];
            if (prov(i, j - 1))
                dp[i][j] += dp[i][j - 1];
            if (j < k) {
                int i1 = j - k + i;
                if (i1 >= 0)
                    dp[i][j] -= pref[i1][0];
            }
            else
                dp[i][j] -= pref[i][j - k];
            if (prov(i - k, j))
                dp[i][j] += pref[i - k][j];
            cnt = max(cnt, dp[i][j]);
        }
    }

    return cnt;
}

void solve() {
    cin >> n >> m >> k;
    k++;
    char c;
    bool st[n][m];
    a.resize(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(m);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
        {
            cin >> c;
            st[i][j] = (c == '#');
            a[i][j] = st[i][j];
        }
    }

    int mx = ans();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = st[n - i - 1][j];
        }
    }
    mx = max(mx, ans());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = st[i][m - j - 1];
        }
    }
    mx = max(mx, ans());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = st[n - i - 1][m - j - 1];
        }
    }
    mx = max(mx, ans());

    cout << mx << '\n';

}

signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    while (tt--)
        solve();

    return 0;
}

Привет! В Jan/15/2024 17:35 (Moscow time) начнётся Codeforces Round 920 (Div. 3) — очередной Codeforces раунд для третьего дивизиона.

Раунд скоординирован Vladosiya, и подготовлен мной и студентами Neapolis University Pafos: Vitaly503, goncharovmike, ikrpprppp, step_by_step.

Большое спасибо Alexdat2000, dan_dolmatov, fastmath, FBI, Nickir, nikhil97agra, pavlekn, PMiguelez, SashaT9, senjougaharin, Sergey140146659, Sparrow_Guo, Toy_mouse, vladmart за тестирование раунда.

Как обычно для раундов третьего дивизиона:

• в раунде будет 6-8 задач
• длительность раунда 2 часа 15 минут
• раунд проходит по правилам ICPC, штраф за неверную попытку 10 минут
• раунд рейтинговый для участников с рейтингами до 1600
• после раунда будет 12-часовая фаза открытых взломов

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

• принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
• не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Всем удачи!

UPD: Разбор

Here are the home tasks for the lecture, you can submit your solutions into this form.

Hello Codeforces!

The final semester starts this week! As usual, the live lectures will be on Twitch on Fridays at 18:00 MSK, and the recorded videos will be on Youtube.

Topics of the fourth semester:

• Matchings
  • Bipartite Matching
  • Non-bipartite Matching (blossoms)
  • Assignment Problem
• Network Flows
  • Maximal Flow
  • Minimal Cost Flow
  • Skew-Symmetric Flows
• Linear Programming
• Fast Fourier Transformation
• Plus something more :)

See you!

The last lecture will be tomorrow at 14:00 MSK

• Lecture 13. Suffix Tree
• Lecture 14. Y-Fast Trie

Better late than never...

• Lecture 9. Strings. Hashing. KMP. Z Algorithm
• Lecture 10. Finite State Automata
• Lecture 11. Aho Corasick Algorithm
• Lecture 12. Suffix Array

Here are the home tasks, you can submit your solutions into this form.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Here is the video of the lecture. Thanks to everyone who watched the live stream.

This week the lecture will be on Wednesday at 6pm MSK

Hello Codeforces!

The third semester starts this week! As usual, the live lectures will be on Twitch on Fridays at 18:00 MSK, and the recorded videos will be on Youtube.

Topics of the third semester:

• Graph Algorithms
  • DFS and its applications
  • MST
  • Shortest Paths
  • Games on Graphs
• String Algorithms
  • Substring Search
  • Suffix Trees
• Plus something more :)

See you!

На настоящий момент зарегистрированы следующие площадки (список пополняется)

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Добрый день. В этом году мы хотим возродить традицию проведения Турнира Архимеда по программированию.

Турнир Архимеда — это командный чемпионат по программированию для начинающих. Турнир проводится по правилам командных соревнований ICPC: засчитываются только верно решенные задачи, при подведении итогов учитывается количество решенных задач, а при равном количестве задач — штрафное время.

Задачи турнира рассчитаны на самый широкий круг участников. Большинство задач не требуют знаний алгоритмов, структур данных, или сложной математики. Возраст участников не ограничен, но имейте в виду, что турнир рассчитан на тех, кто только недавно начал заниматься олимпиадной информатикой. Если вы, например, прошли на ВКОШП, то это соревнование явно не для вас.

Турнир проводится на независимых площадках в разных регионах. Список площадок, а так же правила турнира и другая важная информация, будет в этой группе.

Если вы хотите организовать у себя площадку Турнира Архимеда, пожалуйста, заполните форму, и напишите мне.

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Tomorrow the lecture will be 1 hour earlier than usual, at 5pm MSK

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

See you next week!

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Last week I forgot to make the home tasks, please send me the message if this happens again.

Here are the home tasks for the lecture, you can submit your solutions into this form.

See you next week!

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

See you on Friday!

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form.

Last week home task discussion will be on Sunday at 17:00 MSK.

See you tomorrow!

Here is the video of the lecture. Thanks to everyone who watched the live stream.

Here are the home tasks for the lecture, you can submit your solutions into this form. Sorry for delay :)

See you tomorrow!

Hello Codeforces!

The second semester starts next week! As usual, the live lectures will be on Twitch on Fridays at 18:00 MSK, and the recorded videos will be on Youtube.

Topics of the second semester:

• Segment Trees and similar data structures
  • Segment Tree
  • Fenwick Tree
  • Sparse Table
  • 2D Trees
• Binary Search Trees
  • AVL Tree
  • Treap
  • Splay Tree
• Data Structures for Trees
  • Binary Lifting
  • LCA and LA problems
  • Heavy-Light Decomposition
  • Link-Cut Tree
  • Centroid Decomposition
• Plus something more :)

See you!