Hello Codeforces!

Two great announcements from our team for high school students.

First, very soon, on November 24, we will have the JetBrains Academy Youth Challenge. We will prepare some cool problems, come and participate!

Second, this winter we will have the Algorithm and Code Training School, the great place to master your skills for IOI and other olympiads. Top students from the Youth Challenge will be invited to the ACTS.

See you there!

The first contest of JetBrains Youth Coding Club has started.

If you want to join, register here.

See you!

Hello, Codeforces!

We start a new educational project: JetBrains Youth Coding Club.

In this club I will focus not on algorithms, but on real contest problem solving.

The plan is simple:

• Every week I will prepare a mashup contest from old Codeforces problems.
• You can solve it as a virtual contest at any time during the week.
• In the end of the week we will discuss the solutions and approaches.

I think I will mostly focus on div. 3 problems, but maybe will extend it to div. 2 (or even div. 1, who knows).

The first contest will start next week. If you are interested, register here. See you!

P.S. We also start Math Club and AI Club!

Привет! В 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 - Квадрат

Идея: 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 - Рассадить котов

Идея: 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 - Разослать сообщения

Идея: 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 - Сильно отличающийся массив

Идея: 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 - Съесть фишку

Идея: 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 - Сумма на прогрессии

Идея: 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 - Озорной стрелок

Идея: 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;
}

Привет! В 15.01.2024 17:35 (Московское время) начнётся 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!