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

diskoteka's blog

Button "hide problem tags"

By diskoteka, 8 months ago, translation, In English

Hi everyone! I know of two problem solving modes on Codeforces

Write a contest online or in a virtual competition mode. Then you can't open the solutions of other participants, look through the tests, watch the problem tags and all sorts of information that can help you figure out the task.
Solve problems from the archive, in free manner. This can be used for training, it is convenient to sort tasks by specific topics or rating.

So, when solving the problem in the second way, I ran into the problem that I see its tags. It gives me an advantage that I don't want to have. A kind of hint. To solve this problem, I can launch a virtual participation in the contest where the task was. However, then I will not be able to get additional information about the task before the end of the virtual. What if I want to think for an hour and then look at the tags, for example.

The "hide tags" button, which I did not find (maybe it already exists), would help me here. I think it would be a useful feature.

Full text and comments »

-6

diskoteka
8 months ago
0

Codeforces Round #894 (Div.3) Editorial

By diskoteka, 14 months ago, translation, In English

We would like to thank all the participants who helped us and Codeforces to overcome the 40.000 registered users for the first time

1862A - Gift Carpet

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<string> carpet(n);
        for (int i = 0; i < n; ++i) {
            cin >> carpet[i];
        }
        string vika = "vika";
        int fnd = 0;
        for (int i = 0; i < m; ++i) {
            bool check = false;
            for (int j = 0; j < n; ++j) {
                if (carpet[j][i] == vika[fnd]) {
                    check = true;
                }
            }
            if (check) {
                ++fnd;
                if (fnd == 4) {
                    break;
                }
            }
        }
        if (fnd == 4) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

Rate the problem

1862B - Sequence Game

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<int> a;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            if (i && a.back() > x) {
                a.push_back(1);
            }
            a.push_back(x);
        }
        cout << a.size() << "\n";
        for (int el : a)
            cout << el << " ";
        cout << "\n";
    }
    return 0;
}

Rate the problem

1862C - Flower City Fence

Idea: playerr17

Tutorial

Solution

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        if (a[1] != n) {
            cout << "NO" << '\n';
            continue;
        }
        vector<int> b;
        for (int i = n; i >= 1; i--) {
            while (b.size() < a[i]) {
                b.push_back(i);
            }
        }
        bool meow = true;
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[i - 1]) {
                cout << "NO" << '\n';
                meow = false;
                break;
            }
        }
        if (meow) {
            cout << "YES" << '\n';
        }
    }
    return 0;
}

Rate the problem

1862D - Ice Cream Balls

Idea: diskoteka, Ivang

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int l = 0, r = min<int>(2e9, 2 * n);
        while (r - l > 1) {
            int m = (l + r) >> 1;
            // m = x + y, answer = x + 2 * y
            if (m * (m - 1) / 2 + m < n) {
                l = m;
            } else {
                r = m;
            }
        }
        int y = n - r * (r - 1) / 2;
        if ((r + 1) * r / 2 <= n) {
            cout << min(r + y, r + 1 + n - (r + 1) * r / 2) << "\n";
        } else {
            cout << r + y << "\n";
        }
    }
    return 0;
}

Rate the problem

1862E - Kolya and Movie Theatre

Idea: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n, m, d;
        cin >> n >> m >> d;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        int ans = 0;
        set<pair<int, int>> s;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int cur = sum + a[i] - d * (i + 1);
            ans = max(ans, cur);
            if (a[i] > 0) {
                s.insert({a[i], i});
                sum += a[i];
                if (s.size() >= m) {
                    sum -= (s.begin()->first);
                    s.erase(s.begin());
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Rate the problem

1862F - Magic Will Save the World

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int w, f, n;
        cin >> w >> f >> n;
        vector<int> s(n);
        int sum_s = 0;
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
            sum_s += s[i];
        }
        vector<bool> dp(sum_s + 1);
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int w = sum_s; w - s[i] >= 0; --w) {
                dp[w] = dp[w] || dp[w - s[i]];
            }
        }
        int ans = 2e9;
        for (int i = 0; i <= sum_s; ++i) {
            if (dp[i]) {
                ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f));
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Rate the problem

1862G - The Great Equalizer

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        if (n == 1) {
            int q;
            scanf("%d", &q);
            while (q--) {
                int pos, val;
                scanf("%d %d", &pos, &val);
                cout << val << " ";
            }
            cout << "\n";
            continue;
        }
        multiset<int> aset;
        for (int i = 0; i < n; ++i) {
            aset.insert(a[i]);
        }
        multiset<int> deltas;
        for (auto it = ++aset.begin(); it != aset.end(); ++it) {
            auto prev = it;
            --prev;
            deltas.insert(*it - *prev);
        }
        int q;
        scanf("%d", &q);
        while (q--) {
            int pos, val;
            scanf("%d %d", &pos, &val);
            auto it = aset.find(a[pos - 1]);
            auto nxt = it, prev = it;
            ++nxt; --prev;
            if (it == aset.begin()) {
                deltas.erase(deltas.find(*nxt - *it));
            } else if (it == --aset.end()) {
                deltas.erase(deltas.find(*it - *prev));
            } else {
                deltas.erase(deltas.find(*nxt - *it));
                deltas.erase(deltas.find(*it - *prev));
                deltas.insert(*nxt - *prev);
            }
            aset.erase(it);
            aset.insert(val);
            it = aset.find(val);
            nxt = it, prev = it;
            ++nxt; --prev;
            if (it == aset.begin()) {
                deltas.insert(*nxt - *it);
            } else if (it == --aset.end()) {
                deltas.insert(*it - *prev);
            } else {
                deltas.insert(*nxt - *it);
                deltas.insert(*it - *prev);
                deltas.erase(deltas.find(*nxt - *prev));
            }
            a[pos - 1] = val;
            cout << *--aset.end() + *--deltas.end() << " ";
        }
        cout << "\n";
    }
    return 0;
}

Rate the problem

Full text and comments »

Tutorial of Codeforces Round 894 (Div. 3)

diskoteka
14 months ago
142

Codeforces Round #894 (Div.3)

By diskoteka, 15 months ago, translation, In English

☀ ☀ ☀ Hey Codeforces ☀ ☀ ☀

Summer is ending, but my team and I are happy to invite you to participate in Codeforces Round 894 (Div. 3). The round will take place on Aug/24/2023 17:35 (Moscow time). You will be offered 7 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 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 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round 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.

Problems have been created and written by: diskoteka, pavlekn, playerr17. Ivang helped us with the idea of one of the tasks.

We would like to thank:

Vladosiya for coordinating the round
MikeMirzayanov for great Polygon and Codeforces platforms
feeder1, Xellos for red testing
michao, induk_v_tsiane, Phantom_Performer, vladmart, dmkz, LordVoIdebug, vrintle for yellow testing
kzyKT, celin for purple testing
segment_tea, Egorsa, MADE_IN_HEAVEN, Thost, BF_OF_Priety, mewnya, natalina, Serik2003 for blue testing
i_love_penguins, tnaito, akwa_blue, Zeyad_Hekal, NgJaBach for cyan testing
mkshh, myav for green testing

We wish you all good luck and a high rating!

UPD: Editorial published

Full text and comments »

Announcement of Codeforces Round 894 (Div. 3)

+370

diskoteka
15 months ago
259

Codeforces Round #885 (Div.2) Editorial

By diskoteka, 16 months ago, translation, In English

1848A - Vika and Her Friends

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        int x, y;
        cin >> x >> y;
        string ans = "YES\n";
        for (int i = 0; i < k; ++i) {
            int xx, yy;
            cin >> xx >> yy;
            if ((x + y) % 2 == (xx + yy) % 2) {
                ans = "NO\n";
            }
        }
        cout << ans;
    }
    return 0;
}

1848B - Vika and the Bridge

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> c(n);
        for (int i = 0; i < n; ++i) {
            cin >> c[i];
        }
        vector<int> last(k, -1);
        vector<int> max_step(k), max2_step(k);
        for (int i = 0; i < n; ++i) {
            int step = i - last[c[i] - 1];
            if (step > max_step[c[i] - 1]) {
                max2_step[c[i] - 1] = max_step[c[i] - 1];
                max_step[c[i] - 1] = step;
            } else if (step > max2_step[c[i] - 1]) {
                max2_step[c[i] - 1] = step;
            }
            last[c[i] - 1] = i;
        }
        for (int i = 0; i < k; ++i) {
            int step = n - last[i];
            if (step > max_step[i]) {
                max2_step[i] = max_step[i];
                max_step[i] = step;
            } else if (step > max2_step[i]) {
                max2_step[i] = step;
            }
        }
        int ans = 1e9;
        for (int i = 0; i < k; ++i) {
            ans = min(ans, max((max_step[i] + 1) / 2, max2_step[i]));
        }
        cout << ans - 1 << "\n";
    }
    return 0;
}

1848C - Vika and Price Tags

Idea: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int gcd(int a, int b) {
    if (a == 0) {
        return 0;
    }
    if (b == 0) {
        return 1;
    }
    if (a >= b) {
        int r = a % b;
        int k = a / b;
        if (k % 2 == 1) {
            return gcd(b, r) + k + k / 2;
        } else {
            return gcd(r, b) + k + k / 2;
        }
    }
    return 1 + gcd(b, abs(a - b));
}
 
int calc(int a, int b) {
    if (a == 0) {
        return 0;
    }
    if (b == 0) {
        return 1;
    }
    return 1 + calc(b, abs(a - b));
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
        }
        set<int> cnt;
        for (int i = 0; i < n; ++i) {
            if (a[i] == 0 && b[i] == 0) {
                continue;
            }
            cnt.insert(gcd(a[i], b[i]) % 3);
        }
        if (cnt.size() <= 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

1848D - Vika and Bonuses

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int f(int s, int k) {
    // (s + 20x) * (k - 4x)
    // (-80)x^2 + (20k - 4s)x + (sk)
    // -b/2a = (5k-s)/40
    int x = (5 * k - s) / 40;
    x = min(x, k / 4);
    int res = s * k;
    if (x > 0) {
        res = max(res, (s + 20 * x) * (k - 4 * x));
    }
    x = min(x + 1, k / 4);
    if (x > 0) {
        res = max(res, (s + 20 * x) * (k - 4 * x));
    }
    return res;
}
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int s, k;
        cin >> s >> k;
        int ans = s * k;
        if (s % 10 == 5) {
            ans = max(ans, (s + 5) * (k - 1));
        } else if (s % 10) {
            if (s % 2 == 1) {
                s += s % 10;
                --k;
            }
            for (int i = 0; i < 4; ++i) {
                if (k > 0) {
                    ans = max(ans, f(s, k));
                }
                s += s % 10;
                --k;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

1848E - Vika and Stone Skipping

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int K = 1e6;
 
#define int long long
 
int mod;
 
int dp[K + 1];
int cnt[K + 1];
 
const int MM = 3e6 + 7;
 
int inv[MM];
 
int cc = 0;
 
int mul(int a, int b) {
    int bb = b;
    while (bb % mod == 0) {
        ++cc;
        bb /= mod;
    }
    return (a * (bb % mod)) % mod;
}
 
int dv(int a, int b) {
    int bb = b;
    while (bb % mod == 0) {
        --cc;
        bb /= mod;
    }
    return (a * inv[bb % mod]) % mod;
}
 
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int x, q;
    cin >> x >> q >> mod;
    inv[1] = 1;
    for (int i = 2; i < MM && i < mod; i++) {
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    }
    int y = x;
    for (int i = 3; i <= K; i += 2) {
        if (dp[i]) {
            continue;
        }
        for (int j = i; j <= K; j += 2 * i) {
            dp[j] = i;
        }
    }
    int ans = 1;
    while (x % 2 == 0) {
        x /= 2;
    }
    for (int i = 3; i <= K; i += 2) {
        while (x % i == 0) {
            ans = dv(ans, cnt[i] + 1);
            ++cnt[i];
            ans = mul(ans, cnt[i] + 1);
            x /= i;
        }
    }
    int f = 1;
    if (x > 1) {
        ans = mul(ans, 2);
    }
    x = y;
    for (int i = 0; i < q; ++i) {
        int d;
        cin >> d;
        while (d % 2 == 0) {
            d /= 2;
        }
        int k = d;
        while (dp[k]) {
            ans = dv(ans, cnt[dp[k]] + 1);
            ++cnt[dp[k]];
            ans = mul(ans, cnt[dp[k]] + 1);
            k /= dp[k];
        }
        if (cc) {
            cout << 0 << '\n';
        } else {
            cout << ans << '\n';
        }
    }
    return 0;
}

1848F - Vika and Wiki

Idea: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = (1 << 20);
 
int a[MAXN];
 
int solve(int n) {
    if (n == 1) {
        if (a[0] == 0) {
            return 0;
        } else {
            return 1;
        }
    }
    int fl = true;
    for (int i = 0; i < n / 2; ++i) {
        if (a[i] != a[i + n / 2]) {
            fl = false;
        }
    }
    if (fl) {
        return solve(n / 2);
    }
    for (int i = 0; i < n / 2; ++i) {
        a[i] ^= a[i + n / 2];
    }
    return n / 2 + solve(n / 2);
}
 
int32_t main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    cout << solve(n) << endl;
    return 0;
}

Full text and comments »

Tutorial of Codeforces Round 885 (Div. 2)

+149

diskoteka
16 months ago
207

Codeforces Round #885 (Div.2)

By diskoteka, 16 months ago, In English

(っ▀¯▀)つ Heeey Codeforces (っ▀¯▀)つ

I and pavlekn are glad to invite everyone to participate in Codeforces Round 885 (Div. 2). The round will take place on Jul/16/2023 17:35 (Moscow time).

This round is dedicated to an amazingly beautiful girl Vika that I love very much. Every problem will be about her and related to her life.

The round will be rated for participants with rating lower than 2100. We will be glad to see the participants with a higher rating to take part in our round unofficially as well!

You will be given 6 problems to solve in 2 hours.

We would like to thank everyone that makes this round possible:

Artyom123 for coordinating the round
MikeMirzayanov for great Polygon and Codeforces platforms
teraqqq, Be_dos, mibig, FairyWinx, princebelkovetz for red testing
Dominater069, mbolgov, I.Gleb, induk_v_tsiane, Alexdat2000, maomao90, irkstepanov, fishy15 for yellow testing
Serik2003, alwyn for blue testing
TkachDan, ak2006 for cyan testing
maksimb2008 for grey testing

Scoring distribution: 500 — 1000 — 1500 — 2000 — 2250 — 2750.

We wish you all good luck and a high rating!

UPD: Editorial published

Full text and comments »

Announcement of Codeforces Round 885 (Div. 2)

diskoteka
16 months ago
394

Codeforces Round #878 (Div.3) Editorial

By diskoteka, 17 months ago, translation, In English

1840A - Cipher Shifer

Idea: isosto, preparation: isosto

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        int i = 0;
        while (i < n) {
            int start = i;
            cout << s[i++];
            while (s[i++] != s[start]);
        }
        cout << endl;
    }
}

Rate the problem

1840B - Binary Cafe

Idea: diskoteka, preparation: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        k = min(k, 30);
        cout << min(n, (1 << k) - 1) + 1 << "\n";
    }
    return 0;
}

Rate the problem

1840C - Ski Resort

Idea: pavlekn, preparation: playerr17

Tutorial

Solution

testCases = int(input())
 
for testCase in range(testCases):
    n, k, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    
    ans = 0
    len = 0
    for i in range(n):
        if a[i] <= q:
            len += 1
        else:
            if len >= k:
                ans += (len - k + 1) * (len - k + 2) // 2
            len = 0
    
    if len >= k:
        ans += (len - k + 1) * (len - k + 2) // 2
    print(ans)

Rate the problem

1840D - Wooden Toy Festival

Idea: diskoteka, preparation: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        int l = -1, r = 1e9;
        while (r - l > 1) {
            int m = (l + r) >> 1;
            int i = 0;
            while (i + 1 < a.size() && a[i + 1] - a[0] <= 2 * m) {
                ++i;
            }
            int j = n - 1;
            while (j - 1 >= 0 && a.back() - a[j - 1] <= 2 * m) {
                --j;
            }
            ++i; --j;
            if (i > j || a[j] - a[i] <= 2 * m) {
                r = m;
            } else {
                l = m;
            }
        }
        cout << r << "\n";
    }
    return 0;
}

Rate the problem

1840E - Character Blocking

Idea: diskoteka, preparation: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int x;
    cin >> x;
    while (x--) {
        vector<string> s(2);
        cin >> s[0] >> s[1];
        int n = s[0].size();
        int bad = 0;
        for (int i = 0; i < n; ++i) {
            if (s[0][i] != s[1][i]) {
                ++bad;
            }
        }
        int t, q;
        cin >> t >> q;
        queue<pair<int, int>> unblock;
        for (int i = 0; i < q; ++i) {
            while (!unblock.empty() && unblock.front().first == i) {
                if (s[0][unblock.front().second] != s[1][unblock.front().second]) {
                    ++bad;
                }
                unblock.pop();
            }
            int type;
            cin >> type;
            if (type == 1) {
                int pos;
                cin >> pos;
                if (s[0][pos - 1] != s[1][pos - 1]) {
                    --bad;
                }
                unblock.emplace(i + t, pos - 1);
            } else if (type == 2) {
                int num1, pos1, num2, pos2;
                cin >> num1 >> pos1 >> num2 >> pos2;
                --num1; --pos1; --num2; --pos2;
                if (s[num1][pos1] != s[1 ^ num1][pos1]) {
                    --bad;
                }
                if (s[num2][pos2] != s[1 ^ num2][pos2]) {
                    --bad;
                }
                swap(s[num1][pos1], s[num2][pos2]);
                if (s[num1][pos1] != s[1 ^ num1][pos1]) {
                    ++bad;
                }
                if (s[num2][pos2] != s[1 ^ num2][pos2]) {
                    ++bad;
                }
            } else {
                cout << (!bad ? "YES" : "NO") << "\n";
            }
        }
    }
    return 0;
}

Rate the problem

1840F - Railguns

Idea: diskoteka, preparation: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        int r;
        cin >> r;
        bool free[n + 1][m + 1][r + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= r; ++k) {
                    free[i][j][k] = true;
                }
            }
        }
        for (int i = 0; i < r; ++i) {
            int t, d, coord;
            cin >> t >> d >> coord;
            if (d == 1) {
                for (int j = 0; j <= m; ++j) {
                    if (0 <= t - coord - j && t - coord - j <= r) {
                        free[coord][j][t - coord - j] = false;
                    }
                }
            } else {
                for (int j = 0; j <= n; ++j) {
                    if (0 <= t - coord - j && t - coord - j <= r) {
                        free[j][coord][t - coord - j] = false;
                    }
                }
            }
        }
        bool dp[n + 1][m + 1][r + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= r; ++k) {
                    dp[i][j][k] = !(i || j || k);
                    if (free[i][j][k]) {
                        if (i && dp[i - 1][j][k]) {
                            dp[i][j][k] = true;
                        }
                        if (j && dp[i][j - 1][k]) {
                            dp[i][j][k] = true;
                        }
                        if (k && dp[i][j][k - 1]) {
                            dp[i][j][k] = true;
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int t = r; t >= 0; --t) {
            if (dp[n][m][t]) {
                ans = n + m + t;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Rate the problem

1840G1 - In Search of Truth (Easy Version)

Idea: pavlekn, preparation: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int MAXN = 1e6 + 7;
 
int pos[MAXN];
 
int32_t main() {
    int num;
    cin >> num;
    int ans = 0;
    int cur = 1;
    pos[num] = 1;
    for (int i = 0; i < 1000; ++i) {
        cout << '+' << " " << 1 << endl;
        ++cur;
        cin >> num;
        if (pos[num]) {
            cout << '!' << " " << cur - pos[num] << endl;
            return 0;
        }
        pos[num] = cur;
    }
    while (true) {
        cout << '+' << " " << 1000 << endl;
        cur += 1000;
        cin >> num;
        if (pos[num]) {
            cout << '!' << " " << cur - pos[num] << endl;
            return 0;
        }
        pos[num] = cur;
    }
    return 0;
}

Rate the problem

1840G2 - In Search of Truth (Hard Version)

Idea: pavlekn, preparation: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int MAXN = 1e6 + 7;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int pos[MAXN];
 
const int K = 400;
const int T = 300;
 
int get() {
    return rng() % MAXN;
}
 
int32_t main() {
    int num;
    cin >> num;
    int start = num;
    int cur_delta = 0;
    int N0 = num;
    for (int i = 0; i < K; ++i) {
        int delta = get();
        cout << '+' << " " << delta << endl;
        cur_delta += delta;
        cin >> num;
        N0 = max(N0, num);
    }
    cout << '-' << " " << cur_delta << endl;
    cin >> num;
    cout << '+' << " " << N0 - 1 << endl;
    cur_delta = N0 - 1;
    cin >> num;
    pos[num] = N0;
    for (int i = 0; i < T; ++i) {
        ++cur_delta;
        cout << '+' << " " << 1 << endl;
        cin >> num;
        pos[num] = N0 + i + 1;
        if (num == start) {
            cout << '!' << " " << N0 + i << endl;
            return 0;
        }
    }
    cout << '-' << " " << cur_delta << endl;
    cin >> num;
    int ans = 0;
    while (true) {
        cout << '-' << " " << T << endl;
        ans += T;
        cin >> num;
        if (pos[num]) {
            cout << '!' << " " << ans + pos[num] - 1 << endl;
            return 0;
        }
    }
    return 0;
}

Rate the problem

Full text and comments »

Tutorial of Codeforces Round 878 (Div. 3)

diskoteka
17 months ago
130

Codeforces Round #878 (Div.3)

By diskoteka, 17 months ago, translation, In English

**Hey Codeforces (ﾉ◕ヮ◕)ﾉ*:･ﾟ✧**

My team and I are happy to invite you to participate in Codeforces Round 878 (Div. 3). The round will take place on Jun/06/2023 17:35 (Moscow time). You will be offered 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 8 problems and 2 hours and 15 minutes to solve them. One of the problems in this round is interactive. Don't forget to read the guide on interactive problems.

Note that the penalty for the wrong submission in this round 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.

Problems have been created and written by: diskoteka, pavlekn, playerr17, isosto.

We would like to thank:

Aris for coordinating the round
MikeMirzayanov for great Polygon and Codeforces platforms
step_by_step for red testing
Awesome3.14, I.Gleb, vladmart, dmkz, geospiza, phattd, fishy15 for yellow testing
KDZHR, D34D1NS1D3, JeffreyLC, NintsiChkhaidze, nickbelov, kamishogun, tolbi for purple testing
KoT_OsKaR, Gornak40, Serik2003, Nahian9696, Rudro25, ayhan23, Lyrically for blue testing
TkachDan for cyan testing
MODDI for green testing
midsho for grey testing

We wish you all good luck and a high rating!

UPD: Editorial published

Full text and comments »

Announcement of Codeforces Round 878 (Div. 3)

+329

diskoteka
17 months ago
249

Codeforces Round #867 (Div. 3) Editorial

By diskoteka, 18 months ago, translation, In English

1822A - TubeTube Feed

Idea: diskoteka, prepared: Vladosiya

Tutorial

Solution

def solve():
    n, t = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    bst = -2
    for i in range(n):
        if i + a[i] <= t and (bst == -2 or b[bst] < b[i]):
            bst = i
    print(bst + 1)
 
 
t = int(input())
for _ in range(t):
    solve()

Rate the problem

1822B - Karina and Array

Idea: playerr17, prepared: playerr17

Tutorial

Solution

t = int(input())
 
for testCase in range(t):
    n = int(input())
    a = list(map(int, input().split(' ')))
    a.sort()
    print(max(a[0] * a[1], a[-1] * a[-2]))

Rate the problem

1822C - Bun Lover

Idea: diskoteka, prepared: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        cout << ((n + 1) * n) + n + 2 << "\n";
    }
    return 0;
}

Rate the problem

1822D - Super-Permutation

Idea: isosto, pavlekn, prepared: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        if (n == 1) {
            cout << "1\n";
            continue;
        }
        if (n % 2) {
            cout << "-1\n";
        } else {
            for (int i = 0; i < n; ++i) {
                if (i % 2) {
                    cout << i << " ";
                } else {
                    cout << n - i << " ";
                }
            }
            cout << "\n";
        }
    }
    return 0;
}

Rate the problem

1822E - Making Anti-Palindromes

Idea: pavlekn, prepared: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

void solve(int n, string & s) {
    if (n % 2 == 1) {
        cout << -1 << endl;
        return;
    }
    vector<int> cnt(26);
    for (int i = 0; i < n; ++i) {
        ++cnt[s[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
        if (cnt[i] * 2 > n) {
            cout << -1 << endl;
            return;
        }
    }
    int pairs = 0;
    vector<int> cnt_pairs(26);
    for (int i = 0; i * 2 < n; ++i) {
        if (s[i] == s[n - i - 1]) {
           ++pairs;
           ++cnt_pairs[s[i] - 'a'];
        }
    }
    for (int i = 0; i < 26; ++i) {
        if (cnt_pairs[i] * 2 > pairs) {
            cout << cnt_pairs[i] << endl;
            return;
        }
    }
    cout << (pairs + 1) / 2 << endl;
}

int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        solve(n, s);
    }
}

Rate the problem

1822F - Gardening Friends

Idea: playerr17, prepared: playerr17

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

struct Value {
    int64_t value = 0;
    int vertex = 0;
};

vector<vector<int>> nei;
vector<vector<int>> depth_vertex;
vector<int> depth;
vector<int> parent;

void dfs(int v, int p = -1, int cnt = 0) {
    depth_vertex[cnt].push_back(v);
    depth[v] = cnt;
    parent[v] = p;
    for (int u : nei[v]) {
        if (u == p) continue;
        dfs(u, v, cnt + 1);
    }
}

void solve() {
    int n, root = 1;
    int64_t k_wei, cost;
    cin >> n >> k_wei >> cost;

    nei.clear();
    nei.resize(n + 1);
    depth_vertex.clear();
    depth_vertex.resize(n + 1);
    depth.clear();
    depth.resize(n + 1);
    parent.clear();
    parent.resize(n + 1);

    for (int _ = 0; _ < n - 1; ++_) {
        int u, v;
        cin >> u >> v;
        nei[u].push_back(v);
        nei[v].push_back(u);
    }

    dfs(root);

    vector<pair<Value, Value>> down(n + 1);

    for (int tin = n; tin >= 0; --tin) {
        for (int v : depth_vertex[tin]) {
            for (int u : nei[v]) {
                if (u == parent[v]) continue;
                if (down[u].first.value + 1 > down[v].first.value) {
                    down[v].first.value = down[u].first.value + 1;
                    down[v].first.vertex = u;
                }
            }
            for (int u : nei[v]) {
                if (u == parent[v] || u == down[v].first.vertex) continue;
                if (down[u].first.value + 1 > down[v].second.value) {
                    down[v].second.value = down[u].first.value + 1;
                }
            }
        }
    }

    vector<int64_t> up(n + 1, 0);

    for (int tin = 1; tin <= n; ++tin) {
        for (int v : depth_vertex[tin]) {
            int p = parent[v];
            up[v] = up[p] + 1;
            if (down[p].first.vertex == v) {
                up[v] = max(up[v], down[p].second.value + 1);
            } else {
                up[v] = max(up[v], down[p].first.value + 1);
            }
        }
    }

    int64_t ans = -1'000'000'000'000'000'002;

    for (int v = 1; v <= n; ++v) {
        ans = max(ans, k_wei * max(up[v], down[v].first.value) - cost * int64_t(depth[v]));
    }

    cout << ans << endl;

}

int main()
{
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

Rate the problem

1822G1 - Magic Triples (Easy Version)

Idea: pavlekn, prepared: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAX_VAL = 1e6;

int cnt[MAX_VAL + 1];

int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            ++cnt[a[i]];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (cnt[a[i]] - 1) * (cnt[a[i]] - 2);
            for (int b = 2; a[i] * b * b <= MAX_VAL; ++b) {
                ans += cnt[a[i] * b] * cnt[a[i] * b * b];
            }
        }
        cout << ans << "\n";
        for (int i = 0; i < n; ++i) {
            --cnt[a[i]];
        }
    }
    return 0;
}

Rate the problem

1822G2 - Magic Triples (Hard Version)

Idea: pavlekn, prepared: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int K = 1e6;
const int MAX_VAL = 1e9;

int32_t main() {
    int t;
    scanf("%d", &t);
    for (int _ = 0; _ < t; ++_) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            ++cnt[a[i]];
        }
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (ll)(cnt[a[i]] - 1) * (cnt[a[i]] - 2);
        }
        for (auto el : cnt) {
            int num = el.first;
            int val = el.second;
            if (num > K) {
                for (int b = 2; b * num <= MAX_VAL; ++b) {
                    if (num % b == 0 && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
                        ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
                    }
                }
            } else {
                for (int b = 2; b * b <= num; ++b) {
                    if (num % b == 0) {
                        if ((ll)num * b <= (ll)MAX_VAL && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
                            ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
                        }
                        if (b * b != num) {
                            if ((ll)num * num / b <= (ll)MAX_VAL && cnt.find(b) != cnt.end() && cnt.find(num / b * num) != cnt.end()) {
                                ans += (ll)(cnt[b]) * (cnt[num / b * num]) * val;
                            }
                        }
                    }
                }
                if (num > 1 && (ll)num * num <= (ll)MAX_VAL && cnt.find(1) != cnt.end() && cnt.find(num * num) != cnt.end()) {
                    ans += (ll)(cnt[1]) * (cnt[num * num]) * val;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Rate the problem

Full text and comments »

Tutorial of Codeforces Round 867 (Div. 3)

diskoteka
18 months ago
78

Codeforces Round #867 (Div.3)

By diskoteka, 19 months ago, translation, In English

Hello! Codeforces Round 867 (Div. 3) will start at Apr/24/2023 17:35 (Moscow time). You will be offered 6-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 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round 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.

Thanks to MikeMirzayanov for the platform, and Vladosiya for coordination of our work. Problems have been created and written by: diskoteka, pavlekn, playerr17, isosto.

We would like to thank: pashka, purplesyringa, Alexdat2000, I.Gleb, Serik2003, TkachDan, maksimb2008, _--, 74TrAkToR, Gornak40, ut-k8g, Rudro25, Jostic11, yorky, tolbi, AhmetKaan, Splatjov, BF_OF_Priety, vrintle, KoT_OsKaR for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

Full text and comments »

Announcement of Codeforces Round 867 (Div. 3)

+204

diskoteka
19 months ago
242