Codeforces Round #353 (Div. 2) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Someday I will arrange C and D correctly :)

Firstly, in case c = 0 we should output YES if a = b else answer is NO.

If b belongs to sequence b = a + k * c where k is non-negative integer.

So answer is YES if (b - a) / c is non-negative integer else answer is NO.

Code

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
 
    if (c == 0) {
        if (a == b) cout << "YESn";
        else cout << "NOn";
    } else {
        if ((b - a) % c == 0 && (b - a) / c >= 0) cout << "YESn";
        else cout << "NOn";
    }
}

675B - Restoring Painting

x a y

b m c

z d w

Number in the center may be any from 1 to n because number in the center belongs to all subsquares 2 × 2. So, let's find answer with fixed number in the center and then multiply answer by n.

Let's iterate over all possible x. Sums of each subsquare 2 × 2 are the same so x + b + a + m = y + c + a + m and y = x + b - c.

Similarly, z = x + a - d and w = a + y - d = z + b - c.

This square is legal if 1 ≤ y, z, w ≤ n. We should just check it.

Also we can solve this problem in O(1).

Code

#include <iostream>

using namespace std;

int main() {
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;

    long long ans = 0;
    for (int x = 1; x <= n; x++) {
        int y = x + b - c;
        int z = x + a - d;
        int w = a + y - d;
        if (1 <= y && y <= n && 1 <= z && z <= n && 1 <= w && w <= n) {
            ans++;
        }
    }
    ans *= n;

    cout << ans << endl;
}

675C - Money Transfers

We have array a_i and should make all numbers in it be equal to zero with minimal number of operations. Sum of all a_i equals to zero.

We can divide array into parts of consecutive elements with zero sum. If part has length l we can use all pairs of neighbours in operations and make all numbers be equal to zero with l - 1 operations.

So, if we sum number of operations in each part we get ans = n - k where k is number of parts. We should maximize k to get the optimal answer.

One of the part consists of some prefix and probably some suffix. Each of other parts is subarray of a.

Let's calculate prefix sums. Each part has zero sum so prefix sums before each part-subarray are the same.

So we can calculate f — number of occurencies of the most frequent number in prefix sums and answer will be equal to n - f.

Bonus: how to hack solutions with overflow?

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    map<long long, int> d;
    long long sum = 0;
    int ans = n - 1;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        sum += t;
        d[sum]++;
        ans = min(ans, n - d[sum]);
    }

    cout << ans << endl;
}

675D - Tree Construction

We have binary search tree (BST) and should insert number in it with good time complexity.

Let we should add number x. Find numbers l < x < r which were added earlier, l is maximal possible, r is minimal possible (all will be similar if only one of this numbers exists). We can find them for example with std::set and upper_bound in C++.

We should keep sorted tree traversal (it's property of BST). So x must be right child of vertex with l or left child of vertex with r.

Let l hasn't right child and r hasn't left child. Hence lowest common ancestor (lca) of l and r doesn't equal to l or r. So lca is between l and r in tree traversal. But it's impossible because l is maximal possible and r is minimal possible. So l has right child or r has left child and we know exactly which of them will be parent of x.

That's all. Time complexity is $\text{[math]}$ .

Code

#include <iostream>
#include <set>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    set<int> numbers;
    map<int, int> left;
    map<int, int> right;

    int n, v;
    cin >> n >> v;
    numbers.insert(v);
    for (int i = 0; i < n - 1; i++) {
        cin >> v;
        auto it = numbers.upper_bound(v);
        int result;
        if (it != numbers.end() && left.count(*it) == 0) {
            left[*it] = v;
            result = *it;
        } else {
            it--;
            right[*it] = v;
            result = *it;
        }
        numbers.insert(v);
        cout << result;
        if (i == n - 2) cout << 'n';
        else cout << ' ';
    }
}

675E - Trains and Statistic

Let the indexation will be from zero. So we should subtract one from all a_i. Also let a_n - 1 = n - 1.

dp_i is sum of shortests pathes from i to i + 1... n - 1.

dp_n - 1 = 0

dp_i = dp_m - (a_i - m) + n - i - 1 where m belongs to range from i + 1 to a_i and a_m is maximal. We can find m with segment tree or binary indexed tree or sparse table.

Now answer equals to sum of all dp_i.

Code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1 << 18;
pair<int, int> tree[maxn * 2];

void build(const vector<int> &a, int n) {
    for (int i = 0; i < n; i++) tree[maxn + i] = {a[i], i};
    for (int i = maxn - 1; i > 0; i--)
        tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}

int get(int l, int r) {
    pair<int, int> ans{-1, -1};
    for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans = max(ans, tree[l++]);
        if (r & 1) ans = max(ans, tree[--r]);
    }
    return ans.second;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    a[n - 1] = n - 1;
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
        a[i]--;
    }

    build(a, n);
    vector<long long> dp(n);
    long long ans = 0;
    dp[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        int m = get(i + 1, a[i]);
        dp[i] = dp[m] - (a[i] - m) + n - i - 1;
        ans += dp[i];
    }

    cout << ans << 'n';
}

Rev.	By	When	Δ	Comment
en5	komendart	2016-05-17 16:06:41	131
ru4	komendart	2016-05-17 16:06:11	5100	Мелкая правка: 'ли $a = b$ иначе выв' -
ru3	komendart	2016-05-16 22:18:48	48	Мелкая правка: ' + 1$ to $n - 1$ and $a_m' -> ' + 1$ to $a_i$ and $a_m'
en4	komendart	2016-05-16 22:18:16	48	Tiny change: ' + 1$ to $n - 1$ and $a_m' -> ' + 1$ to $a_i$ and $a_m'
ru2	komendart	2016-05-16 22:05:51	3329
en3	komendart	2016-05-16 22:05:04	3289
en2	komendart	2016-05-16 21:36:25	0	(published)
en1	komendart	2016-05-16 21:35:55	3341	Initial revision for English translation
ru1	komendart	2016-05-16 21:33:45	3341	Первая редакция (сохранено в черновиках)

History