Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Gol_D's blog

Codeforces Round #805 (Div. 3)

By Gol_D, history, 2 years ago, In English

Hello! Codeforces Round 805 (Div. 3) will start at Jul/10/2022 17:35 (Moscow time). You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

take part in at least five rated rounds (and solve at least one problem in each of them),
do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Vladosiya, Aris, senjougaharin and me Gol_D.

Also many thanks to turmax, ivanz, antonis.white, Ronnie007, okwedook, oversolver, Kavaliro, antoshkin, omikad, yorky, Jostic11, Ziware, Kniaz, andrey.starodubtsev, Spaggetti and aniervs for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

Full text and comments »

Announcement of Codeforces Round 805 (Div. 3)

contest, 805

+236

Gol_D
2 years ago
443

Codeforces Round #780 (Div. 3) Editorial

By Gol_D, history, 3 years ago, In English

1660A - Vasya and Coins

Idea: MikeMirzayanov

Tutorial

Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int it = 0; it < t; ++it) {
        int a, b;
        cin >> a >> b;
        cout << (a == 0 ? 1 : a + 2 * b + 1) << '\n';
    }
    return 0;
}

1660B - Vlad and Candies

Idea: Vladosiya

Tutorial

Solution

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    if n == 1:
        if a[0] > 1:
            print("NO")
        else:
            print("YES")
        continue
    if a[-2] + 1 < a[-1]:
        print("NO")
    else:
        print("YES")

1660C - Get an Even String

Idea: MikeMirzayanov

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;
int sz = 26;
 
void solve(){
    string s;
    cin >> s;
    int m = 0, n = (int)s.size();
    vector<bool>prev(sz, false);
    for(auto &i : s){
        if(prev[i - 'a']){
            m += 2;
            for(int j = 0; j < sz; j++) prev[j] = false;
        }
        else prev[i - 'a'] = true;
    }
 
    cout << n - m << endl;
}
 
int main(){
    int t;
    cin >> t;
    while (t--){
        solve();
    }
}

1660D - Maximum Product Strikes Back

Idea: Aris

Tutorial

Solution

#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()
 
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
 
    forn(i, n) 
        cin >> a[i];
    int ans = 0;
    int ap = n, as = 0;
    for(int i = 0, l = -1; i <= n; i++) {
        if (i == n || a[i] == 0) {
            int cnt = 0;
            bool neg = false;
            int left = -1, right = -1;
            int cl = 0, cr = 0;
            for (int j = l+1; j < i; j++) {
                neg ^= a[j] < 0;
                if (a[j] < 0) {
                    right = j;
                    cr = 0;
                }
 
                if (abs(a[j]) == 2) {
                    cnt++, cr++;
                    if (left == -1) cl++;
                }
 
                if (a[j] < 0 && left == -1) {
                    left = j;
                }
            }
            if (neg) {
                if (cnt - cl > cnt - cr) {
                    right = i;
                    cnt -= cl;
                } else {
                    left = l;
                    cnt -= cr;
                }
            } else {
                left = l, right = i;
            }
            if (ans < cnt) {
                ans = cnt;
                ap = left + 1, as = n - right;
            }
 
            l = i;
        }
    }
    cout << ap << ' ' << as << endl;
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

1660E - Matrix and Shifts

Idea: myav, MikeMirzayanov

Tutorial

Solution

#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
 
const int INF = INT_MAX >> 1;
 
void solve() {
    int n; cin >> n;
    int cnt1 = 0;
    vector<int> cnt (n, 0);
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0, k = (n - i) % n; j < n; j++, k = (k + 1 == n ? 0 : k + 1)) if (s[j] == '1') {
            cnt1++;
            cnt[k]++;
        }
    }
    int ans = INF;
    for (int i = 0; i < sz(cnt); i++) {
        ans = min(ans, cnt1 - cnt[i] + (n - cnt[i]));
    }
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

1660F1 - Promising String (easy version)

Idea: MikeMirzayanov

Tutorial

Solution

tst = int(input())
for _ in range(tst):
    n = int(input())
    s = input()
    b = [0 for i in range(n+1)]
    bal = n
    b[0] = bal
    ans = 0
    for i in range(1,n+1):
        if s[i-1] == '+':
            bal += 1
        else:
            bal -= 1
        b[i] = bal
        for j in range(i):
            if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0:
                ans += 1
    print(ans)

1660F2 - Promising String (hard version)

Idea: MikeMirzayanov

Tutorial

Solution

tst = int(input())
for _ in range(tst):
    n = int(input())
    s = input()
    f = [0 for i in range(3)]
    cur_bal = n
    cnt_bal = [0 for i in range(2 * n + 1)]
    cnt_bal[cur_bal] += 1
    f[cur_bal % 3] += 1
    ans = 0
    for i in range(n):
        #print(f)
        #print(cur_bal, ans)
        new_bal = cur_bal
        if s[i] == '-':
            new_bal -= 1
            f[new_bal % 3] += cnt_bal[new_bal]
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        else:
            f[new_bal % 3] -= cnt_bal[new_bal]
            new_bal += 1
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        cur_bal = new_bal
    print(ans)

Full text and comments »

Tutorial of Codeforces Round 780 (Div. 3)

editorial, contest

Gol_D
3 years ago
26

Codeforces Round #762 (Div. 3) Editorial

By Gol_D, history, 3 years ago, In English

1619A - Square String?

Idea: MikeMirzayanov

Tutorial

Solution

#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) {
        string s;
        cin >> s;
        bool ok = true;
        if (s.length() % 2 == 0) {
            forn(i, s.length() / 2)
                if (s[i] != s[i + s.length() / 2])
                    ok = false;
        } else
            ok = false;
        cout << (ok ? "YES" : "NO") << endl;
    }
}

1619B - Squares and Cubes

Idea: MikeMirzayanov

Tutorial

Solution

#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;
        cin >> n;
        set<int> a;
        for (int i = 1; i * i <= n; i++)
            a.insert(i * i);
        for (int i = 1; i * i * i <= n; i++)
            a.insert(i * i * i);
        cout << a.size() << endl;
    }
}

1619C - Wrong Addition

Idea: MikeMirzayanov

Tutorial

Solution

#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
 
void solve(){
    ll a, s;
    cin >> a >> s;
    vector<int>b;
    while(s){
        int x = a % 10;
        int y = s % 10;
        if(x <= y) b.emplace_back(y - x);
        else{
            s /= 10;
            y += 10 * (s % 10);
            if(x < y && y >= 10 && y <= 19) b.emplace_back(y - x);
            else{
                cout << -1 << '\n';
                return;
            }
        }
        a /= 10;
        s /= 10;
    }
    if(a) cout << -1 << '\n';
    else{
        while (b.back() == 0) b.pop_back();
        for(int i = len(b) - 1; i >= 0; i--) cout << b[i];
        cout << '\n';
    }
}
 
int main(){
    ios_base ::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t){
        solve();
        t--;
    }
    return 0;
}

1619D - New Year's Problem

Idea: Vladosiya

Tutorial

Solution

//
// Created by Vlad on 17.12.2021.
//
 
#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
int n, m;
vector<vector<int>> p;
 
bool check(int x){
    vector<bool> abl(m);
    bool pair = false;
    for(int i = 0; i < n; ++i){
        int c = 0;
        for(int j = 0; j < m; ++j){
            if(p[i][j] >= x){
                abl[j] = true;
                c++;
            }
        }
        if(c > 1) pair = true;
    }
    if(!pair && m > 1) return false;
    bool ans = true;
    for(bool b: abl){
        ans = ans && b;
    }
    return ans;
}
 
void solve() {
    cin >> n >> m;
    p.assign(n, vector<int>(m));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> p[i][j];
        }
    }
    int l = 1, r = 2;
    while (check(r)) r *= 2;
    while (r - l > 1){
        int mid = (r + l) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}
 
bool multi = true;
 
signed main() {
    //freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

1619E - MEX and Increments

Idea: senjougaharin

Tutorial

Solution

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
const int MAX_N = 2e5;
 
int main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n), cnt(n + 1);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            cnt[a[i]]++;
        }
        sort(a.begin(), a.end());
        stack<int> st;
        vector<ll> ans(n + 1, -1);
        ll sum = 0;
        for (int i = 0; i <= n; ++i) {
            if (i > 0 && cnt[i - 1] == 0) {
                if (st.empty()) {
                    break;
                }
                int j = st.top();
                st.pop();
                sum += i - j - 1;
            }
            ans[i] = sum + cnt[i];
            while (i > 0 && cnt[i - 1] > 1) {
                cnt[i - 1]--;
                st.push(i - 1);
            }
        }
        for (ll x : ans) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

1619F - Let's Play the Hat?

Idea: MikeMirzayanov

Tutorial

Solution

#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, m, k;
        cin >> n >> m >> k;
        vector<int> p(n);
        forn(i, n)
            p[i] = i;
        if (tt > 0)
            cout << endl;
        forn(round, k) {
            int index = 0;
            forn(table, m) {
                int size = n / m;
                if (table < n % m)
                    size++;
                cout << size;
                forn(j, size)
                    cout << " " << p[index++] + 1;
                cout << endl;                        
            }
            rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
        }
    }
}

1619G - Unusual Minesweeper

Idea: Gol_D

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int k;
 
map <int, vector<int>> mx;
map <int, vector<int>> my;
map <pair<int ,int>, bool> used;
map <pair<int, int>, int> time_of;
 
int dfs(int x, int y) {
    used[{x, y}] = true;
    int _min_ = time_of[{x, y}];
 
    auto i = lower_bound(mx[x].begin(), mx[x].end(), y);
    auto j = lower_bound(my[y].begin(), my[y].end(), x);
 
    if (++i != mx[x].end() && !used[{x, *i}] && abs(*i - y) <= k) {
        _min_ = min(_min_, dfs(x, *i));
    }
    --i;
    if (i != mx[x].begin() && !used[{x, *(--i)}] && abs(*i - y) <= k) {
        _min_ = min(_min_, dfs(x, *i));
    }
 
    if (++j != my[y].end() && !used[{*j, y}] && abs(*j - x) <= k) {
        _min_ = min(_min_, dfs(*j, y));
    }
    --j;
    if (j != my[y].begin() && !used[{*(--j), y}] && abs(*j - x) <= k) {
        _min_ = min(_min_, dfs(*j, y));
    }
 
    return _min_;
}
 
void solve() {
    mx.clear();
    my.clear();
    used.clear();
 
    int n;
    cin >> n >> k;
    vector <pair<int, int>> a(n);
    int x, y, timer;
 
    for (int i = 0; i < n; ++i) {
        cin >> x >> y >> timer;
        a[i] = {x, y};
        time_of[{x, y}] = timer;
        mx[x].push_back(y);
        my[y].push_back(x);
    }
    vector<int> res;
 
    for (auto now: mx) {
        sort(mx[now.first].begin(), mx[now.first].end());
    }
    for (auto now: my) {
        sort(my[now.first].begin(), my[now.first].end());
    }
 
    for (auto now: a) {
        if (!used[now]) {
            res.push_back(dfs(now.first, now.second));
        }
    }
    sort(res.begin(), res.end());
 
    int ans = res.size() - 1;
    for (int i = 0; i < res.size(); ++i) {
        ans = min(ans, max((int)res.size() - i - 2, res[i]));
    }
    cout << ans << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int tests;
    cin >> tests;
    forn(tt, tests) {
        solve();
    }
}

1619H - Permutation and Queries

Idea: Brovko

Tutorial

Solution

#include <bits/stdc++.h>
//#define int long long
#define ld long double
#define x first
#define y second
#define pb push_back
 
using namespace std;
const int Q = 100;
 
int n, q, p[100005], r[100005], a[100005];
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> q;
 
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }
 
    for(int i = 0; i < n; i++)
        r[p[i]] = i;
 
    for(int i = 0; i < n; i++)
    {
        int x = i;
 
        for(int j = 0; j < Q; j++)
            x = p[x];
 
        a[i] = x;
    }
 
    while(q--)
    {
        int t, x, y;
        cin >> t >> x >> y;
 
        if(t == 2)
        {
            x--;
 
            while(y >= Q)
            {
                y -= Q;
                x = a[x];
            }
 
            while(y--)
                x = p[x];
 
            cout << x + 1 << "\n";
        }
        else
        {
            x--;
            y--;
 
            swap(r[p[x]], r[p[y]]);
            swap(p[x], p[y]);
 
            int ax = x;
 
            for(int i = 0; i < Q; i++)
                ax = p[ax];
 
            int x2 = x;
 
            for(int i = 0; i < Q; i++)
            {
                a[x] = ax;
                x = r[x];
                ax = r[ax];
            }
 
            swap(x, y);
 
            ax = x;
 
            for(int i = 0; i < Q; i++)
                ax = p[ax];
 
            x2 = x;
 
            for(int i = 0; i < Q; i++)
            {
                a[x] = ax;
                x = r[x];
                ax = r[ax];
            }
        }
    }
}

Full text and comments »

Tutorial of Codeforces Round 762 (Div. 3)

#762 (div 3), editorial

Gol_D
3 years ago
85

Codeforces Round #756 (Div. 3) Editorial

By Gol_D, history, 3 years ago, In English

1611A - Make Even

Idea: MisterGu

Tutorial

Solution

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        string n;
        cin >> n;
        if((n.back() - '0') % 2 == 0) {
            cout << "0\n";
            continue;
        }
        if((n[0] - '0') % 2 == 0) {
            cout << "1\n";
            continue;
        }
        int count_2 = count(n.begin(), n.end(), '2');
        int count_4 = count(n.begin(), n.end(), '4');
        int count_6 = count(n.begin(), n.end(), '6');
        int count_8 = count(n.begin(), n.end(), '8');
        if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) {
            cout << "2\n";
            continue;
        }
        cout << "-1\n";
    }
    return 0;
}

1611B - Team Composition: Programmers and Mathematicians

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
void solve() {
    ll a, b;
    cin >> a >> b;
    cout << min(min(a, b), (a + b) / 4) << '\n';
}
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

1611C - Polycarp Recovers the Permutation

Idea: MikeMirzayanov

Tutorial

Solution

#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;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        if (a[0] != n && a[n - 1] != n)
            cout << -1 << endl;
        else {
            for (int i = n - 1; i >= 0; i--)
                cout << a[i] << " ";
            cout << endl;
        }
    }
}

1611D - Weights Assignment For Tree Edges

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> b(n + 1), p(n + 1), dist(n + 1, -1);
 
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    for(int i = 1; i <= n; i++)
        cin >> p[i];
 
    if (b[p[1]] != p[1]){
        cout << -1 << '\n';
        return;
    }
 
    dist[p[1]] = 0;
    for(int i = 2; i <= n; i++){
        if(dist[b[p[i]]] == -1){
            cout << -1 << '\n';
            return;
        }
        dist[p[i]] = dist[p[i - 1]] + 1;
    }
 
    for(int i = 1; i <= n; i++) {
        cout << dist[i] - dist[b[i]] << ' ';
    }
    cout << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while(t-- > 0) {
        solve();
    }
}

1611E1 - Escape The Maze (easy version)

Idea: Vladosiya

Tutorial

Solution

//
// Created by Vlad on 16.11.2021.
//
 
#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> color(n, -1);
    deque<int> q;
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        color[--x] = 0;
        q.push_back(x);
    }
    color[0] = 1;
    q.push_back(0);
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    while(!q.empty()){
        int v = q.front();
        q.pop_front();
        for(int u: g[v]){
            if(color[u] == -1){
                color[u] = color[v];
                q.push_back(u);
            }
        }
    }
    for(int v = 1; v < n; ++v){
        if(g[v].size() == 1 && color[v] == 1){
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

1611E2 - Escape The Maze (hard version)

Idea: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
vector<vector<int>> sl;
vector<int> nearest;
 
int count(int v, int dist, int p = -1){
    bool children = true;
    int s = 0;
    for(int u: sl[v]){
        if(u == p) continue;
        int c = count(u, dist + 1, v);
        if(c < 0) children = false;
        nearest[v] = min(nearest[v], nearest[u] + 1);
        s += c;
    }
    if(nearest[v] <= dist) return 1;
    if(s == 0 || !children) return -1;
    return s;
}
 
void solve() {
    int n, k;
    cin >> n >> k;
    sl.assign(n, vector<int>(0));
    nearest.assign(n, n);
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        --x;
        nearest[x] = 0;
    }
    for(int i = 1; i  < n; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        sl[u].emplace_back(v);
        sl[v].emplace_back(u);
    }
    cout << count(0, 0);
}
 
bool multi = true;
 
signed main() {
    //freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    /*ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);*/
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

1611F - ATM and Students

Idea: Gol_D, MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define forn(i, n) for (int i = 0; i < int(n); i++)

vector<ll> t, a;
ll s, tl;

const ll MAX = 1'000'000'000'000'000LL;

void build(int v, int l, int r) {
	if (l == r)
		t[v] = a[l];
	else {
		int m = (l + r) / 2;
		build (v * 2, l, m);
		build (v * 2 + 1, m + 1, r);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
}

void update(int v, int l, int r) {
	if (l == r)
		t[v] = MAX;
	else {
		int m = (l + r) / 2;
		if (tl <= m)
			update(v * 2, l, m);
		else
			update(v * 2 + 1, m + 1, r);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
}

int lower_bound_s(int v, int l, int r) {
	if (r < tl || (l == r && s < -t[v])) {
		return -1;
	}
    if (l == r || -t[v] <= s) {
        return r;
    }
	int m = (l + r) / 2;

	if (m < tl) {
        return lower_bound_s(2 * v + 1, m + 1, r);
	}
	if (s < -t[2 * v]) {
        return lower_bound_s(2 * v, l, m);
	}
	int res = lower_bound_s(2 * v + 1, m + 1, r);
	return (res == -1) ? m : res;
}


int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        int n;
        cin >> n >> s;
        t = vector<ll>(4 * n);
        a = vector<ll>(n);
        forn(i, n) {
            cin >> a[i];
        }
        for (int i = 1; i < n; ++i) {
            a[i] += a[i - 1];
        }
        build(1, 0, n - 1);
        int first = -1, second = -2;
        for (tl = 0; tl < n; ++tl) {
            int v = lower_bound_s(1, 0, n - 1);
            if (v != -1 && v - tl > second - first) {
                first = tl + 1;
                second = v + 1;
            }
            s -= a[tl];
            if (tl != 0) s += a[tl - 1];
            update(1, 0, n - 1);
        }
        if (first == -1) {
            cout << -1;
        } else {
            cout << first << " " << second;
        }
        cout << endl;
    }
}

1611G - Robot and Candies

Idea: MikeMirzayanov

Tutorial

Solution

#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()
 
const int N = 1e6 + 50;
string a[N];
 
int n,m;
int ans;
 
void solve(int sum0) {
    vector<int> v;
    for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) {
        vector<int> cur;
        int li = max(0, sum - m + 1), ri = min(n - 1, sum);
        if (li > ri) continue;
 
        for (int i = li; i <= ri; i++) {
            int j = sum - i;
 
            if (a[i][j] == '1')
                cur.emplace_back(i);
        }
 
        while (pref != sz(v) && v[pref] + ad > ri) {
            pref++;
        }
        for (int i = pref; i < sz(v); i++) {
            int new_val = v[i];
            while (!cur.empty() && cur.back() - ad >= v[i]) {
                new_val = max(new_val, cur.back() - ad);
                cur.pop_back();
            }
            v[i] = new_val;
        }
        if (!cur.empty()) {
            v.emplace_back(cur.back() - ad);
            ans++;
        }
    }
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        cin >> n >> m;
 
        forn(i, n) {
            string s; 
            cin >> a[i];
        }
 
        ans = 0;
        solve(0);
        solve(1);
        
        cout << ans << '\n';
    }
}

Full text and comments »

Tutorial of Codeforces Round 756 (Div. 3)

Gol_D
3 years ago
58

Codeforces Round #756 (Div. 3)

By Gol_D, 3 years ago, In English

Hello! Codeforces Round 756 (Div. 3) will start at Nov/25/2021 17:35 (Moscow time). You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

You will be given 7-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

take part in at least five rated rounds (and solve at least one problem in each of them),
do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Also many thanks to God_Of_Code, oversolver, FlakeLCR, Igorjan94, Jester, KHiMAeRA, KerakTelor, Loolo, MatheusMonteiro, Resende, teraqqq, dedlocc, doreshnikov, kbats183, kocko, vsinitsynav and pashka for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

Full text and comments »

Announcement of Codeforces Round 756 (Div. 3)

756, div3

+267

Gol_D
3 years ago
264