870A - Search for Pretty Integers Idea, preparation, editorial komendart

870B - Maximum of Maximums of Minimums Idea DPR-pavlin, preparation, editorial mHuman

870C - Maximum splitting Idea, preparation, editorial komendart

870D - Something with XOR Queries Idea, preparation, editorial mHuman

870E - Points, Lines and Ready-made Titles Idea, preparation, editorial komendart

870F - Paths Idea, preparation, editorial komendart

871E - Restore the Tree Idea MikeMirzayanov, preparation fcspartakm, editorial mHuman

Also many thanks to coordinator KAN, testers ifsmirnov, vintage_Vlad_Makeev, AlexFetisov and any other people who participates in preparation of contest.

Code (C++) 31365874

Code (Python) 31365844

Code 31366254

Code 31365909

Code 31366223

Code 31365959

Code 31366002

Code 31368704

Hi everyone!

I don't know, maybe this topis was discussed on Codeforces but google didn't help me.

It seems that standart hash function in gcc works badly (for Visual C++ all is good).

For 0 ≤ x ≤ 2³² - 1

std::hash<int>()(x) == x 
std::hash<long long>()(x) == x

For any other number

std::hash<long long>()(x + (1LL << 32)) == std::hash<long long>()(x)

For example code in spoiler works more than 10 seconds on Codeforces because hashes of all numbers are equal to zero.

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<long long> d;
    int n = 1e5;
    long long t = 1LL << 32;
    for (int i = 0; i < n; i++) {
        d.insert(i * t);
    }
    cout << d.size() << endl;
}

What can we do without writing our own hash function?

Someday I will arrange C and D correctly :)

675A - Infinite Sequence

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.

#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).

#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?

#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 .

#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.

#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';
}

Hello, everyone!

Codeforces Round #353 (Div. 2) will take place tomorrow on the 16th of May at 19:35 MSK. I tried to make interesting problems, hope you enjoy them.

I'd like to thank GlebsHP for his help in preparing problems and MikeMirzayanov for Codeforces and Polygon.

Good luck!

UPD Scoring 500-1000-1500-2000-2500

UPD Editorial

UPD Congratulations to winners!

Div. 2

1. mimirrow

2. Salvare008

3. orzchimo

4. student_hh

5. Pain_Konan

Div. 1

1. ksun48

2. sugim48

3. KrK

4. cgy4ever

5. nfssdq

617A - Elephant

It's optimal to do the biggest possible step everytime. So elephant should do several steps by distance 5 and one or zero step by smaller distance. Answer equals to

Solution 15550796

617B - Chocolate

We are given array which contains only ones and zeroes. We must divide it on parts with only one 1.

Tricky case: when array contains only zeroes answer equals to 0.

In general. Between two adjacent ones we must have only one separation. So, answer equals to product of values pos_i - pos_i - 1 where pos_i is position of i-th one.

Bonus: what's the maximal possible answer for n < 100?

Solution 15550806

617C - Watering Flowers

First radius equals to zero or distance from first fountain to some flower. Let's iterate over this numbers. Second radius equals to maximal distance from second fountain to flower which doesn't belong to circle with first radius. Now we should choose variant with minimal r₁² + r₂².

Bonus: It's O(n²) solution. Can you solve problem in O(nlogn)?

Solution O(n²) 15550812

Solution O(nlogn) 15550822

617D - Polyline

Answer equals to one if all coordinates x or y of points are same.

When answer equals to two? Let's iterate over all pairs of points. Let first point in pair is beginning of polyline, second point is end. Only one or two such polylines with answer two exist. If third point is on the polyline it belongs to rectangle with corners in first two points. We can just check it.

Else answer equals to three. We can build vertical lines which contains the most left and the most right point and horizontal line through third point. If we erase some excess rays we will get polyline.

Solution 15550843

617E - XOR and Favorite Number

We have array a.

Let's calculate array pref (pref[0] = 0, ).

Xor of subarray a[l...r] equals to .

So query (l, r) is counting number of pairs i, j (l - 1 ≤ i < j ≤ r) .

Let we know answer for query (l, r) and know for all v cnt[v] — count of v in a[l - 1...r]. We can update in O(1) answer and cnt if we move left or right border of query on 1. So we can solve problem offline in with sqrt-decomposion (Mo's algorithm).

Solution 15550846

Hi!

Tomorrow, on 23rd of January at 18:35 MSK Codeforces Round #340 (Div. 2) will take place. It's my first round, hope you enjoy the problems.

Thanks to GlebsHP for his help in preparing the problems, Delinur for translations of statements and MikeMirzayanov for Codeforces and Polygon.

Good luck!

UPD Scoring 500-1000-1250-1750-2750

UPD Editorial

UPD Congrats to winners!

Div. 2

1. AReesha

2. kpw29

3. I_love_Varechka

4. zhaoxinyi

5. thatday

Div. 1

1. anta

2. dreamoon_love_AA

3. uwi

4. Um_nik

5. I_love_Tanya_Romanova