Codeforces Round #353 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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