Codeforces Round #867 (Div. 3) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

#	User	Contrib.
1	Um_nik	164
2	-is-this-fft-	160
2	maomao90	160
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

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

Comments (49)

Show archived | Write comment?

LextyleO_o

17 months ago, # |

← Rev. 3 →

-7

G2 can be solved by going threw array from left to right and for every i get all divisors of a[i] and for perfect square divisors X increase answer by cnt[a[i] / X] * cnt[a[i] / sqrt(X)]. We just need to get divisors using prime factorization which we can get by going only threw prime numbers [1, sqrt(10^9)] (only ~3000).

→ Reply

cockatooo

17 months ago, # ^ |

+12

There are ~3000 primes in [1, 10^4.5] right, not 65?

-14

still fast

-8

Why are you downvoting? I just wrote my approach on that problem :)

VahanAbraham

← Rev. 2 →

IanISam

+18

Alternatively for g2, we can prime factorize the number to look for candidates for k. Apparently prime factorization can be done with pollard(although I didn’t do this) and the number of perfect squares can be found in logM (someone needs to prove this I suck at math). Essentially g2 can be solved in o(n*M^1/4).

For the log constant on m, you can notice that the number of perfect squares is the number of each p divided by 2 and choosing how much of each p exists. The number of terms is maximum 6 or approximately 2^6 operations. If someone has a better analysis of this it would be greatly appreciated.

camc

I was thinking we can do O(n*M^(1/6)) because we are only considering divisors of the SQRT(M), which is ~(M^(1/2))^(1/3) because the number of divisors of a number M doesn't exceed O(M^(1/3))

Ref: https://codeforces.net/blog/entry/13585?#comment-185136

How would you find factors with sqrt(M) I’m curious.

Imagine we are brute-forcing the largest value a[k], consider the divisors of a[k], we only need to consider divisors which are perfect squares because our value b will be the square root of the divisor. I think we can show the number of divisors which are perfect squares of some value is at most the sixth root of the value.

Does this answer your question?

The larger number could be a perfect square and not the smaller number? If you have implementation that would help.

Sure, here is my implementation: https://codeforces.net/contest/1822/submission/203467962

Hopefully this clears things up.

It does seem to be the right time complexity but it doesn’t have noticeably better performance compared with my previous algorithm. This may be due to a high constant factor.

-11

Yeah I bet that's related to the implementation.

ABalobanov

+14

Also we can solve G2 with pointers and achieve better complexity without unordered map.

Abito

Editorial for C missing last few characters

ishwarendra

Zooming out (from 125% to 100%) worked for me. It looks like overflowing content (on zooming in) are now made hidden instead of letting them go out of the box.

F can also be solved using rerooting dp.

Here is my submission.

Banis

Can someone hack this solution

It should get a TLE verdict.

gu76h

I don't know why my solution was not TLE. Could you help me? This is my g2 solution

KK_1729

nice div3

Jai-shri-ram-27

Can someone pls tell why I am getting TLE at test 16 For Problem G1 even though my idea is same as the official editorial. Link of submission: (https://codeforces.net/contest/1822/submission/203514583)

I_love_GSNQK

Use an array instead of a dictionary

islam15-14475

Can u give a test cases where this solution did not pass link of my solution https://pastebin.ubuntu.com/p/kVh39TVsk5/

kintakku

Input

Expected output

Your output

Explanation

mohithaakash

How does one solve D? Is it just finding the pattern? I could only figure out that there is no answer for odd (>1) and n would be the first number.

TsotneSV

the solution is kind of hidden in the last sample. one can construct the array on other even numbers and see if it works.

SunnyYuan

I think $$$a=[n, 1, n−2, 3, n−4, 5, …, n−1, 2]$$$ is wrong.

Isn't it $$$a=[n, 1, n−2, 3, n−4, 5, …, 2, n-1]$$$.

That's how your code is written.

ghost_1123321

Does 10 ^ 8 complexity passes in CF ?? asking becouse of editorial of G1

depends on time limit. Here we have 4s. it should pass.

Kavya2719

Alternative Solution for Problem F

Intuition and Solution

-> Code

icyalmond

thank you so much for the solution, it was way more simpler to understand

however i dont really get why we dont have to also DFS from the other end point of the diameter (which can be found in the process of DFS from A) but only from A to find the answer?

Let's dive in and Think of it.

oh i get it now, tysm

asupersalmon

+19

how to tell that the time complexity for G2 passes ? O(M^(1/3)nlogn) seems bigger than 10^8 for M = 10^9, n = 2*10^5

TsupaRoman

Where can I have a mistake?:

Problem F — Wrong answer on test 36.

But it works:

Problem F — Accepted.

cosenza

you put assign(n, 0), instead of assign(26, 0)

semicolonised

I should definitely stop complicating problems. I used Binary Lifting to solve F.

If anybody wants to check the stupid submission: 203630946.

a757403

Yet another solution for G2 using sqrt decomposition(excuse my English):

First,for each prime number in (1e9^(1/4),1e9^(1/2)],simply iterate over all multiples of its square.The time complexity is at most O(M^(1/2)lnM^(1/2)),and it is clear that each number <=1e9 can have at most one of these square numbers as its factor because (1e9^(1/4))^2*(1e9^(1/4))^2=1e9,so we can precalculate it using std::map in O(M^(1/2)lnM^(1/2)logM^(1/2)).

Next,for each number,iterate over all prime numbers in [2,1e9^(1/4)].It doesn't takes long since there are less than 100 primes in [2,1e9^(1/4)].Then check the map for its factor in (1e9^(1/4),1e9^(1/2)] (if exist) in O(logM).At last,iterate over all its factors.Since 2^2*3^2*5^2*7^2*11^2*13^2~=9e8,there are at most 2^6=64 factors to iterate over for a single number.The total time complexity is O(M^(1/2)log^2(M^(1/2))+(100+logM+64)n). Solution:203320262

Epilogue

For F you can dfs 3 times to find the maximum distance to the leaves.

leftover_19

I don't understand the tutorial of G1. Can someone explay it in newbie language? ∑ni=1(cnt[ai]−1)⋅(cnt[ai]−2) I don't know exactly what are we doing here

sahaun

sum = 0;
for (i = 1; i <= n; i += 1) {
  sum += (cnt[a[i]]-1) * (cnt[a[i]]-2);
}

What I don't get is the part inside the loop. Cnt[a[i]-1] * (cnt[a[i]] — 2); code is quite clear. I want to know what exactly is this .

We need to choose 3 numbers $$$x$$$, $$$y$$$, $$$z$$$ such that $$$x * b = y$$$ and $$$y * b = z$$$.

When $$$b = 1$$$, $$$x = y = z$$$. In this case, we need to select 3 of the same number.

Let's say the count of $$$x$$$ is $$$cnt_x$$$. In how many ways can you select 3 different $$$x$$$ from $$$cnt_x$$$?

nectarl

The key to question E is to figure out that if m*2>=k, the answer is m/2+m%2,isn't it? In other words,there must exist some way to match every two pairs that are not the same letter when m*2>=k. I probably know how to prove it through mathematical induction, it may seem unnecessary though.

_Aryan_

why is this not passing? code is in segfault function

https://codeforces.net/contest/1822/submission/205472462

vitosevskich

← Rev. 4 →

UPD: solved it.

The tutorial for G2 says the time complexity $$$O(n \cdot M^{\frac{1}{3}} \cdot \text{log } n)$$$ with the use of std::map will pass. Why does my solution TLEs then?

https://codeforces.net/contest/1822/submission/205547154

pavlekn what do you mean? I don't understand.

chidoring

deleted comment

Kami-Sama

16 months ago, # |

Another solution for G2, I believe is much simpler but is somehow getting tle. Can someone verify this?

*Time Complexity: O(n*pow(M,1/3)) *Idea:

Array a has distinct sorted numbers and hash map f stores the frequency of these.
Also, a[i]*b==a[j] and a[j]*b==a[k]
thus a[i]*b*b==a[k]
From the above equation, b should lie in range [1 , pow(a[k]/a[j],1/2)] or [1,pow(M,1/2)] here is M is max(a).
Now, for i>=pow(M,1/3) we have b in range [1,sqrt(M/pow(M,1/3))] = [1,sqrt(pow(M,2/3))] = [1,pow(M,1/3)] .
so we loop through this entire range of b if i>1000 ( as elements are distinct and sorted i>1000 means a[i]>1000 ). Hence, O(n*pow(M,1/3))
Also for i<pow(M,1/3) we can iterate through all j>i => O(n*pow(M,1/3))

so we have ensured that time complexity is O(n*pow(M,1/3)) submission

pavlekn Help Orz

kpeach

12 months ago, # |

For F:

Intuition

Essentially, we have that:

If v is the node we move root to, solution = max( k * maxdistance(v) - c * dist(root,v) ) over all nodes v.

where maxdistance(v) is the distance of the furthest node from v. It is pretty easy to get dist(root,v) in DFS/BFS.

Note we have two cases: if c >= k, then we will never move root (since we will lose profit). if k > c, then we will always want to move root to increase the maxdistance, which means v must be either a leaf, or the root itself. If it's the root, then maxdistance(root) is just height of root. So, let's now consider non-root v.

Suppose node u is the one whose distance dist(u,v) = maxdistance(v). u and v must share some ancestor, p. also u and v must be in separate subtrees of p, otherwise p would be a better choice than v.

So,

dist(u,v) = dist(u,p) + dist(p,v)
          = height of subtree u of p + height of subtree v of p + 2

where the height of a subtree x of p is the height of the child of p who contains node x.

the plus 2 is to include the extra edge from each child to p

my submission: https://codeforces.net/contest/1822/submission/227252588

diskoteka's blog