Привет! В 12.09.2022 17:35 (Московское время) начнётся Codeforces Round 820 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение. Одна из задач интерактивная. Не забудьте прочитать инструкцию по интерактивным задачам.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: Kniaz, BledDest, Svyat, Be_dos, Timur2006, FelixDzerzhinsky, alphabet321, FedShat, vsinitsynav, Jostic11, erankyun, _Roma_, KKT_89, ABalobanov, lightseba, powergee101, DafuQ_o и AshrafEzz за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD 1:

Мы во время раунда (и мы скучаем по Gornak40 и Gol_D).

UPD 2: Разбор

1690A - Print a Pedestal (Codeforces logo?)

Идея: MikeMirzayanov

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
 
 
 
void solve() {
    int n; 
    cin >> n;
    for (int a = 3; a < n; a++) {
        int c = (n - a) / 2;
        int b = n - a - c;
        if (c > 1 && b+1 < a) {
            c--;
            b++;
        }
        if (a > b && b > c) {
            cout << b << ' ' << a << ' ' << c << endl;
            return;
        }
    }
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

1690B - Array Decrements

Идея: MikeMirzayanov

#include<bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
const int inf = 1e9 + 7;
 
bool equals(vector<int>&a, vector<int>&b, int n){
    int dif = inf;
    forn(i, n){
        if(b[i] != 0) dif = min(dif, a[i] - b[i]);
    }
    if(dif < 0) return false; 
    if(dif == inf) return true;
    forn(i, n){
        if(a[i] - b[i] > dif) return false;
        if(b[i] != 0 && a[i] - b[i] < dif) return false;
    }
    return true;
}
 
void solve(){
    int n;
    cin >> n;
    vector<int>a(n), b(n);
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];
    cout << (equals(a, b, n) ? "YES\n" : "NO\n");
 
}
 
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

1690C - Restoring the Duration of Tasks

Идея: MikeMirzayanov

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
 
void solve() {
    int n;
    cin >> n;
    int s[n];
    int f[n];
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
 
    for (int i = 0; i < n; ++i) {
        cin >> f[i];
    }
    int curTime = 0;
    int d[n];
    for (int i = 0; i < n; ++i) {
        curTime = max(curTime, s[i]);
        d[i] = f[i] - curTime;
        curTime = f[i];
    }
    for (auto now: d) {
        cout << now << " ";
    }
    cout << '\n';
}
int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        solve();
    }
}

1690D - Black and White Stripe

Идея: MikeMirzayanov

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<int> w(n + 1);
        for (int i = 1; i <= n; i++)
            w[i] = w[i - 1] + int(s[i - 1] == 'W');
        int result = INT_MAX;
        for (int i = k; i <= n; i++)
            result = min(result, w[i] - w[i - k]);
        cout << result << endl;
    }
}

1690E - Price Maximization

Идея: Vladosiya, Aris

#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
 
void solve(){
    int n, k;
    cin >> n >> k;
    vector<ll>a(n);
    ll sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i] / k;
        a[i] = a[i] % k;
    }
    sort(a.begin(), a.end(), [] (int x, int y){
        return x > y;
    });
 
    for(int i = 0, j = n - 1; i < j; i++, j--){
        while(a[i] + a[j] < k && i < j) j--;
        if(i == j) break;
        sum++;
    }
    cout << sum << endl;
}
 
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

1690F - Shifting String

Идея: MikeMirzayanov

def gcd(a, b):
    if b == 0:
        return a;
    return gcd(b, a % b)
    
    
def shift(s):
    for i in range(1, len(s) + 1):
        if s == s[i:] + s[:i]:
            return i
    
 
def solve():
    n = int(input())
    s = input()
    p = [int(x)-1 for x in input().split()]
    used = [False] * n
    ans = 1
    i = 0
    while i < n:
        ss = ''
        while not used[i]:
            ss += s[i]
            used[i] = True
            i = p[i];
        i += 1
        if len(ss) == 0:
            continue
        ln = shift(ss)
        ans = ans * ln // gcd(ans, ln)
    print(ans)
    
 
t = int(input())
for _ in range(t):
    solve()

1690G - Count the Trains

Идея: Aris

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        set<int> tmp;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {
                tmp.insert(i);
            }
        }
        for (int i = 0; i < m; i++) {
            int j, d;
            cin >> j >> d;
            j--;
            a[j] -= d;
            auto it = tmp.upper_bound(j);
            if (it != tmp.begin()) {
                it = prev(it);
                if (*it == j || a[*it] > a[j]) {
                    tmp.insert(j);
                }
            } else {
                tmp.insert(j);
            }
            while (1) {
                it = tmp.upper_bound(j);
                if (it != tmp.end() && a[*it] >= a[j]) {
                    tmp.erase(it);
                } else {
                    break;
                }
            }
            cout << (int) tmp.size() << " ";
        }
        cout << '\n';
    }
}

Привет! В 31.03.2022 17:35 (Московское время) начнётся Codeforces Round 780 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

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

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

Спасибо NEAR за поддержку этого раунда, подробности можно прочитать в этом посте.

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin и Vladosiya.

Также большое спасибо: arvindr9, hocky, lucasxia01, Evirir, Sorting, 244mhq, yorky, Jostic11, sansen, leaf1415, Masha237, amr_abdelazim, coderbd, gs17005, nebula за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

Привет! В 10.01.2022 17:35 (Московское время) начнётся Codeforces Round 764 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение. Одна из задач интерактивная. Не забудьте прочитать инструкцию по интерактивным задачам.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin и Vladosiya.

Также большое спасибо: itohdak, Yogi79, smtcoder, Ra16bit, Tlatoani, nigus, MrDindows, leaf1415, Kniaz, Alireza, mini4141, Jostic11, BitHashTech, An_yujin, oversolver и sodafago за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Вот фото нашего коллектива во время ответа на ваши вопросы во время раунда:

UPD 2: Разбор