Codeforces Round #992 (Div.2) Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	158
2	adamant	152
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

2040A - Game of Division

Editorial

Solution C++

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector < vector <int> > b(k);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            b[x % k].push_back(i);
        }
        int res = -1;
        for (int i = 0; i < k; i++) {
            if ((int)b[i].size() == 1) {
                res = b[i][0];
                break;
            }
        }
        if (res == -1) {
            cout << "NO" << endl;
        }
        else {
            cout << "YES" << endl << res << endl;
        }
    }
    
    return 0;
}

Solution Python

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = [[] for _ in range(k)]
    for i in range(0, n):
        x = a[i]
        b[x % k].append(i + 1)
    res = -1
    for i in range(k):
        if len(b[i]) == 1:
            res = b[i][0]
            break
    if res == -1:
        print("NO")
    else:
        print("YES\n" + str(res))

2040B - Paint a Strip

Editorial

Solution C++

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) {
            if (cur >= n) {
                cout << ans << '\n';
                break;
            }
        }
    }
    
    return 0;
}

Solution Python

tt = int(input())
for _ in range(tt):
    n = int(input())
    ans = 1
    cur = 1
    while True:
        if cur >= n:
            print(ans)
            break
        ans += 1
        cur = cur * 2 + 2

Notes

2040C - Ordered Permutations

Editorial

Solution C++

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        long long k;
        cin >> n >> k;
        vector <int> a, b;
        
        if (n <= 60 && (1ll << (n - 1)) < k) {
            cout << -1 << endl;
            continue;
        }
        k--;
        vector <int> d;
        while (k) {
            d.push_back(k % 2);
            k /= 2;
        }
        while (d.size() < n - 1) d.push_back(0);
        
        for (int i = n - 2, j = 1; i >= 0; i--, j++) {
            if (d[i] == 0) a.push_back(j);
            else b.push_back(j);
        }
        
        reverse(b.begin(), b.end());
        for (int i : a) cout << i << ' ';
        cout << n << ' ';
        for (int i : b) cout << i << ' ';
        cout << endl;
    }
 
    return 0;
}

Solution Python

tt = int(input())
for _ in range(tt):
    n, k = map(int, input().split())
    a, b = [], []
 
    if n <= 60 and (1 << (n - 1)) < k:
        print(-1)
        continue
    k -= 1
    d = []
    while k:
        d.append(k % 2)
        k //= 2
    while len(d) < n - 1:
        d.append(0)
 
    a, b = [], []
    j = 1
    for i in range(n - 2, -1, -1):
        if d[i] == 0:
            a.append(j)
        else:
            b.append(j)
        j += 1
 
    b.reverse()
    print(*a, n, *b)

2040D - Non Prime Tree

Editorial

Solution 1

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector < vector <int> > g(n);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        vector <int> res(n);
        int lst = 1;
        res[0] = lst;
        
        function <void(int, int)> dfs = [&](int v, int p) {
            for (int to : g[v]) {
                if (to == p) continue;
                res[to] = lst + 1;
                while (res[to] != res[v] + 1 && 
                      (res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) {
                    res[to]++;   
                }
                lst = res[to];
                dfs(to, v);
            }
        };
        
        dfs(0, 0);
        for (int i : res) cout << i << ' ';
        cout << endl;
    }
    
    return 0;
}

Solution 2 (zap4eg)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) {
    h[v] = h[p] + 1;
    for (int u : g[v]) {
        if (u == p)
            continue;
        dfs(u, g, h, v);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> h(n);
        dfs(0, g, h, 0);
        vector<vector<int>> hs(n + 1);
        for (int i = 0; i < n; i++)
            hs[h[i]].push_back(i);
        int l = 2, r = 2 * n;
        int cur = 0;
        vector<int> ans(n);
        for (int i = 1; i <= n; i++) {
           if (cur) {
               for (int v : hs[i]) {
                    ans[v] = r;
                    r -= 2;
               }
           } 
           else {
               for (int v : hs[i]) {
                    ans[v] = l;
                    l += 2;
               }
           }
           cur ^= 1;
        }
        bool found = false;
        for (int i = 0; i < n; i++) {
            for (int v : g[i]) {
                if (h[v] < h[i])
                    continue;
                if (abs(ans[v] - ans[i]) == 2) {
                    ans[v] = ans[i] - 1;
                    found = true;
                    break;
                }
            }
            if (found)
                break;
        }
        for (int i = 0; i < n; i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

Notes

2040E - Control of Randomness

Editorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    vector < vector <int> > g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    vector <int> depth(n);
    vector <int> d(n);
    vector <int> par(n);
 
    function <void(int, int)> dfs = [&](int v, int p) {
        if (depth[v] == 1) d[v] = 1;
        if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size();
        par[v] = p;
        for(int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v);
        }
    };
    
    dfs(0, 0);
    
    while (q--) {
        int v, p;
        cin >> v >> p;
        v--;
        int res = d[v];
        vector <int> cnt;
        while (v != 0 && par[v] != 0) {
            cnt.push_back((int)g[par[v]].size());
            v = par[par[v]];
        }
        sort(cnt.rbegin(), cnt.rend());
        for (int i = 0; i < min(p, (int)cnt.size()); i++) {
            res -= 2 * (cnt[i] - 1);
        }
        cout << res << '\n';
    }
}
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

Solution (Notes)

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    vector < vector <int> > g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    vector <int> depth(n);
    vector <int> d(n);
    vector < vector < pair <int,int> > > qrs(n); // <p, idx>
    vector <int> res(q);
    
    for (int i = 0; i < q; i++) {
        int v, p;
        cin >> v >> p;
        v--;
        qrs[v].push_back({p, i});
    }
    
    multiset <int> st[2]; // store negative number to be able to use usual foreach loop
    
    function <void(int, int, int)> dfs = [&](int v, int p, int pp) {
        if (depth[v] == 1) d[v] = 1;
        if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size();
        
        for (pair <int, int> qr : qrs[v]) {
            int p = qr.first, idx = qr.second;
            int ans = d[v];
            for (int i : st[1 - depth[v] % 2]) {
                if (p == 0) break;
                ans -= (-i - 1) * 2;
                p--;
            }
            res[idx] = ans;
        }
        
        if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size());
        
        for (int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v, p);
        }
        
        if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size()));
    };
    
    dfs(0, 0, 0);
    
    for (int i = 0; i < q; i++)
        cout << res[i] << '\n';
}
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

Notes

2040F - Number of Cubes

Editorial

Solution Phi

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N], phi[N];
 
int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        }
        else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}
 
int inv(int a) {
    return powmod(a, mod - 2);
}
 
void prepare() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    ifact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    }
 
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        phi[i] = i - 1;
    }
    for (int i = 2; i < N; i++) {
        for (int j = i * 2; j < N; j += i) {
            phi[j] -= phi[i];
        }
    }
}
 
int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
 
int MC(vector <int> &a) {
    int sum=0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) {
        res = (res * ifact[i]) % mod;
    }
    return res;
}
 
int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}
 
vector <int> all_divs(int x) {
    vector <int> d;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d.push_back(i);
            if (i * i != x) {
                d.push_back(x / i);
            }
        }
    }
    return d;
}
 
void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector <int> v(k);
    for (int &i : v) cin >> i;
 
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
 
    map <int, int> mp;
    for (int i : all_divs(a)) {
        for (int j : all_divs(b)) {
            for (int l : all_divs(c)) {
                int N = lcm(i, lcm(j, l));
                if (g % N == 0) {
                    mp[N] += phi[i] * phi[j] * phi[l];
                }
            }
        }
    }
 
    int sum = 0;
    for (pair <int, int> pr : mp) {
        int N = pr.first, cnt = pr.second;
        vector <int> u;
        for (int t : v) u.push_back(t / N);
        sum = (sum + (MC(u) * cnt) % mod) % mod;
    }
 
    sum = (sum * inv(a * b * c)) % mod;
 
    cout << sum << endl;
}
 
int32_t main() {
    prepare();
 
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

Solution DP

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N];
int pos[N];
 
int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        }
        else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}
 
int inv(int a) {
    return powmod(a, mod - 2);
}
 
void prepare() {
    fact[0] = 1;
    for (int i = 1;i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    ifact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    }
}
 
int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
 
int MC(vector <int> &a) {
    int sum=0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) {
        res = (res * ifact[i]) % mod;
    }
    return res;
}
 
int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}
 
vector <int> all_divs(int x) {
    vector <int> d1, d2;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d1.push_back(i);
            if (i * i != x) {
                d2.push_back(x / i);
            }
        }
    }
    reverse(d2.begin(), d2.end());
    for (int i : d2) d1.push_back(i);
    return d1;
}
 
void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector <int> v(k);
    for (int &i : v) cin >> i;
 
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
    vector <int> divs_g = all_divs(g);
 
    set <int> divs;
    for (int i : all_divs(a)) divs.insert(i);
    for (int i : all_divs(b)) divs.insert(i);
    for (int i : all_divs(c)) divs.insert(i);
    for (int i : all_divs(g)) divs.insert(i);
    int D = divs.size();
    int i = 0;
    for (int j : divs) {
        pos[j] = i;
        i++;
    }
 
    int n = max({a, b, c}) + 1;
    vector < vector <int> > tmp(3, vector <int> (D));
    vector < vector <int> > cnt(3, vector <int> (D));
    for (int t = 0; t < 3; t++) {
        int x;
        if (t == 0) x = a;
        if (t == 1) x = b;
        if (t == 2) x = c;
        vector <int> divs_x = all_divs(x);
 
        for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
            tmp[t][pos[divs_x[i]]] += x / divs_x[i];
            for (int j = 0; j < i; j++) {
                if (divs_x[i] % divs_x[j] == 0) {
                    tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
                }
            }
            cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
        }
    }
        
    vector < vector <int> > dp(4, vector <int> (D));
    dp[0][0] = 1;
    for(int i = 0; i < 3; i++) {
        for (int t1 : divs_g) {
            for (int t2 : divs_g) {
                int new_pos = lcm(t1, t2);
                if (t2 < n) {
                    dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
                }
            }
        }
    }
 
    int sum = 0;
    i = 0;
    for (int j : divs) {
        if (g % j != 0) continue;
        int N = j, cnt = dp[3][pos[j]];
        vector <int> u;
        for (int t : v) u.push_back(t / N);
        sum = (sum + (MC(u) * cnt) % mod) % mod;
    }
 
    sum = (sum * inv(a * b * c)) % mod;
 
    cout << sum << endl;
}
 
int32_t main() {
    prepare();
 
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

(1, 2, 3, 4, 5) (1, 2, 3, 5, 4) (1, 2, 4, 5, 3) (1, 2, 5, 4, 3) (1, 3, 4, 5, 2) (1, 3, 5, 4, 2) (1, 4, 5, 3, 2) (1, 5, 4, 3, 2) (2, 3, 4, 5, 1) (2, 3, 5, 4, 1) (2, 4, 5, 3, 1) (2, 5, 4, 3, 1) (3, 4, 5, 2, 1) (3, 5, 4, 2, 1) (4, 5, 3, 2, 1) (5, 4, 3, 2, 1)

Comments (106)

Show archived | Write comment?

DivinePunishment

17 months ago, hide # |

+49

can someone hack my submission for D, it works purely on hopes and dreams. 295631816

→ Reply

HellDiver

17 months ago, hide # ^ |

+106

who are we to ruin ones hopes and dreams?

Jonhyer

why all of you say “hopes and dreams”？what is the meaning of it?

nguyenquocthao00

undertale reference

meta-circular

← Rev. 2 →

+13

My submission for D was literally hopes and dreams (I just chose random valid numbers until it was no longer possible.)

tramp3

Same

Muhammad_Aneeq

I thought i was the only doing this.

Go2Hell

Hey, can you tell me how did this even come to your mind to generate random numbers and then brute forcing all the available remaining numbers, did you not think that it may give TLE? Just curious to know why so many people applied such a random approach of generating random numbers.

I was running out of time and couldn't think of a sophisticated way of doing it, and the number of composite numbers >> the number of prime numbers so I'd figured I'd probably be able to allocate a number within a few tries. As for why random numbers instead of just iterating starting from the next number, I thought that there was a decent chance that I'd end up with a bunch of allocated numbers close together that I would have to iterate over and waste time, so random numbers were probably safer than that option. Plus, I always have a soft spot for cool approaches and randomization definitely qualifies. :) ~~In hindsight it was probably not necessary but it was fun nonetheless.~~

Sorry for rambling, but that pretty much exactly represents my thought process within the contest.

Edit: it turns out randomization was necessary for my approach. I submitted a solution without randomization, just using the fallback I had of iterating over all unused elements in order (using a set so it wasn't totally inefficient), and I TLE'd.

That's cool , thank you for replying and sharing :)

dimixo120

+19

fast editorial

tempturing

-72

Problems like C add nothing to the knowledge of the participants. They just test IQ.

Also, it is exactly same as this problem: https://mirror.codeforces.com/contest/513/problem/B2

Edit: I understand that many of you had fun solving the problem. But there are several participants who just recognized the pattern for smaller n's and hoped it work for larger values of n as well. Isn't it unfair to the people who really come up with and proved their solution?

I mean the testers create randomized cases just to ensure that makeshift solutions do not pass and here anyone who recognized the "pattern" for n <= 6 could get an AC!

Mehul_Gupta

Is this the reason for so many ACs on C?

+40

the fact that it already exists is cringe and they should've checked for that. But I struggled on it for an hour, and when I managed to solve it, I think it really did add to my knowledge, and I think it's a great problem. I believe I learned a lot more from it than from D, where I literally just guessed the solution without proving it actually works

That is because you are one of the few people who solved it like it should be. Many participants just observed the pattern for small n's and hoped that it will work for bigger values of n as well. Something similar happened for D also.

Noobish_Monk

Well, not "hoped", but it's much easier to prove a pattern than spot a pattern without seeing the permutationa

IAWNMW

Nahh man,I think apart from the fact that it was an existing problem I felt that it was a nice constructive algorithm problem which didn't rely on prior facts or knowledge.

nik_exists

Agree 100%, really annoying that it was a previously done problem, since I had a lot of fun solving it (and it's probably the hardest problem I've ever solved, so I'm happy about that)

Vladithur

Me, the author, and the testers didn't know about this problem, and it didn't come up in my searches :( (maybe because the formula is an image...)

akkafakka

I feel that getting the permutation even after knowing the fact (which can be easily verified by a brute force), the construction isn't trivial. The editorial seems incomplete without it.

123gjweq2

welp that's the average div. 2 C unfortunately

codeprover

← Rev. 3 →

+10

i think C is a pretty cute problem Tbf, aside from the fact that it existed before the contest

it felt much nicer solving C since i was able to see what was happening and wasn't making any guesses

-firefly-

+23

They just test IQ

If so, all constructive problems on arrays are testing IQ.

to an extent, yes

Leonardo_Paes

+12

Isn't competitive programming a huge IQ test? If someone doesn't like IQ tests, I would advise against CP...

I think recognizing the pattern is a good thing. It takes skills to be able to recognize the pattern and take advantage of the pattern to solve the problem. Dynamic programming is also about recognizing the pattern.

ashish1729

oh wow, super fast editorial before system testing, thank you.

LearningMachine

+27

Thanks for the really interesting problemset. It's satisfying to see that even E can be implemented so simply without need for advanced data structures.

nathanballman

E can be solved offline in O(Q log^3 N) by using parallel binary search and HLD.

what techniques/knowledge is required for E? i am clueless on how to even begin solving it

The easier solution to E does not need any of this. Naive O(NQlogN) works just fine.

Under the constraints, this approch is only a little faster than the official one.

This problem has the same general idea and requires this approach.

theSkeleton

isn't that a bit over kill?

yes, very much so.

jay_jayjay

You can also solve in O(Q log N) with PST walking

neal

No need for $$$\log^3$$$, you can get a simple offline $$$(N + Q) \log N$$$ using Fenwick trees: 295645729

aa2

everyone failed E because they misread the constraints

FallingRain

+32

And almost everyone missed E because they were stuck in C and D.

Aritro_

Bruh I had no idea how to solve B.

Then I remembered, "If nothing makes your solution work, put it in a binary search" — me

So, I tried binary searching on how many of 1st type operations would be used.

And I got wa. But I will try to solve it using binary search

sibashis_12

Binary search will work, so you're not trying in vain.

hxu10

← Rev. 6 →

Here is the 2e5 version of problem E for python. It passed the test, and run within 1s with randomly generated cases on my local machine.

295640041

malachi_toney_goat

this link is broken https://mirror.codeforces.com/blog/entry/13685

Igor_Parfenov

Fixed, thank You

ton

Now it says "You are not allowed to view the requested page".

woruo27

← Rev. 4 →

+15

My solution of D with the proof:

Find the center of the tree, do dfs that starts from it.
Sort all vertices by (depth, dfs_visit_time) descending order as $$$v_1, v_2, \cdots, v_n$$$.
Assignment $$$a_{v_i} = 2 \times (i + 1)$$$ for $$$v_1, v_2, \cdots, v_{n-1}$$$，and $$$a_{v_n} = 2$$$.
If there is a conflict that $$$v_1 (a_{v_1} = 4)$$$ is a neighbor of $$$v_n (a_{v_n} = 2)$$$，assignment $$$a_{v_1} = 1$$$.

Proof:

Lemma: Since we do dfs from the center, every layer has at least two vertices if the tree has two centers. Otherwise only the layer of the center has only one vertex.

$$$v_i$$$ must be not the neighbor of $$$v_{i+1}$$$ if they have same depth. In the case they have different depth, they can't be adjacent after the sort because the lemma (except $$$v_n$$$ when it's a center). So $$$v_1, v_2, \cdots, v_{n-1}$$$ must be a legal solution.

So we just need to care with $$$v_n (a_{v_n} = 2)$$$. It can only conflict with $$$v_1 (a_{v_1} = 4)$$$. If they are adjacdent, we just assignment $$$a_{v_1} = 1$$$ because $$$v_1$$$ is always a leaf and not about other vertices ($$$v_2, v_3, \cdots, v_{n-1}$$$).

Code: 295631636

I think another solution used bipartite graph is more interesting, really make me amaze.

Update: Sorry, it's like official solution 2.

Ahmad45123

make me amaze

read Project Hail Mary lol

_BoJack.Horseman_

B was nice!

Shyngys-K-003-27

ok i am dumb i forgot about last 1 after "1"

Place 1s at indexes 1 and 4

Fill the indexes 1 through 4

Place 1 at index 10

Fill the indexes 1 through 10 (This solves your second question)

Place a 1 at index 20

Fill the indexes through 1 through 20

3 from 10: initial: 0000000000 after 1: 1000000000 after 2: 1001000000 query type 2: 1111000000 after 3: 1111000001 query type 2: 1111111111

20 does the same steps up to there but adds one more initial (3 operations done): 11111111110000000000 after 4: 11111111110000000001 query type 2: 11111111111111111111

whiitex

Consider this string: 1001000001 Where the flipped bit are those set using first operation. Now, you can flip the first two bits in between (because there are a total of 4 bits, 2 of which are 1, so the constraint ceil(4/2) >= 2 is satisfied). Then the string becomes: 1111000001 Now, just choose the first and the last bit; l=1, r=10, the constraint ceil(10/2) = 5 >= 5 is satisfied, so we can flip all other bits. Just do it iteratively and you have the solution.

not_tryin

+14

E can be solved in O(n^2 + q). Link

NiGhT-h-MaRe

dreams are illusion or future

Ashwanth.K

Cannt problem E be solved with $$$Q \le 10^5$$$ also.

expertaq

Yes, you can precompute a 2d DP and answer all queries in O(1)

+35

For problem D my solution simply chooses values randomly for each node of the tree in DFS order, repeating until the difference with the node's parent isn't prime.

This works because when $$$n$$$ is large enough, $$$n \, » \, \frac{n}{\ln n}$$$ (or even $$$\frac{2n}{\ln n}$$$), which means there's always a significant fraction of the remaining numbers that would result in a non-prime difference. During the contest I added some logic to potentially restart from scratch and re-randomize if needed for small $$$n$$$, but it seems like you don't even need that: 295643399

Another benefit of this solution is it will work for smaller bounds such as $$$1.5n$$$ instead of $$$2n$$$.

NeverSpot

Can you please further show why it will work?

tr1ten

Hi, i did the same but used bfs, and for some reason it is giving TLE 296790454

can you please help?

You can't solve n = 3 with composite differences only (the only option is 4). You need to use 1 as a non-prime difference as well.

5imp

nice problems, finally reached pupil!

neat solution to problem C... I found the greedy strategy for problem C but couldn't find a way to implement it other than calculating 2^(n-2), which would not work with the constraints. sad that I could not solve it even after finding the correct logic ;(

Titan493ASST

Hey ladies and gentlemen, this is my code for verifying how the dynamics of the C's solution work https://www.ideone.com/fQB1zU

and following is the submission link of the AC verdict for the corresponding Que' https://mirror.codeforces.com/contest/2040/submission/295645589

hope you understand it, if not, ping me back freely!

JuicyGrape

+16

Alternative solution for problem E:

Let us solve the problem where $$$p=0$$$ for all queries. Consider two functions $$$A_v$$$ and $$$B_v$$$ where $$$A_v$$$ is the expected number of moves to reach $$$1$$$ if we are currently in $$$v$$$ and $$$i$$$ is odd and $$$B_v$$$ is the same as $$$A_v$$$ but $$$i$$$ is even. $$$A_1=B_1=0$$$, since we are already at $$$1$$$ so we require zero moves.

If $$$i$$$ is odd, then we move to the parent with probability $$$1$$$, hence $$$A_v=B_{\texttt{pr}}+1$$$, where $$$\texttt{pr}$$$ is the parent of $$$v$$$.

If $$$i$$$ is even, then we move to any neighbor vertex with the same probability, hence $$$B_v=\sum\limits_{u \in N(v)}\frac{A_u}{deg[v]}+1$$$. Let us simplify this formula as $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\sum\limits_{u \in \texttt{children}(v)}\frac{A_u}{deg[v]} + 1$$$. Notice, that $$$A_u=B_{\texttt{v}}+1$$$ from the $$$A_v$$$ recurrence, hence $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\sum\limits_{u \in \texttt{children}(v)}\frac{B_v+1}{deg[v]} + 1$$$ The sum does not depand on $$$u$$$ anymore, so we have $$$B_v=\frac{A_{\texttt{pr}}}{deg[v]}+\frac{deg[v]-1}{deg[v]}\cdot (B_v+1) + 1$$$.

Solving this equation for $$$B_v$$$ we have a formula $$$B_v=A_{\texttt{pr}}+2\cdot \texttt{deg}[v]-1$$$.

We have formulas for $$$A_v$$$ and $$$B_v$$$ that depend only on the parent of $$$v$$$, so can run a simple dfs to compute the values for all vertices. The answer for the query is $$$A_v$$$, since we start from the odd $$$i$$$.

But in the original problem we have some amount of coins. The solution doesn't change at all, we just add another parameter to our functions that responds to the number of coins we have, $$$A_{v,p}$$$ and $$$B_{v,p}$$$. The transitions are the same, but we can also spend a coin when updating $$$B_{v, p}$$$, so $$$B_{v, p}$$$ may be $$$A_{\texttt{pr}, p-1}+1$$$.

Precomputing $$$A_{v,p}$$$ and $$$B_{v,p}$$$ for all $$${v,p}$$$ takes us $$$O(n^2)$$$ and answering the queries $$$O(1)$$$.

Implementation: 295642233

Negationist

C was tragic for me, I actually found the "left or right " construction, I just couldn't get it to work properly, i need to work on constructives

Qumeric

Damn, in D I thought that 1 is considered to be a prime number...

PaciukZvichainyi

Hell nah. My master dreams are ruined by this fact. I almost went crazy not understanding why my solution wasn't working.

I need to retire from cf to save my hair and eyes :)

HungHot

Sorry, I laughed when I saw your rating

pajju04

I am failing to understand E, if anyone could help me understand it in easier way. Thanks before hand

problem E: I thought to build a vector of expected values $$$d$$$, where $$$d_N$$$ is the expected number of moves from a node with $$$N$$$ neighbors to go up (towards vertex 1) of exactly one step, so the parent, when the current counter parity is even. So:

$$$d_N = \frac{1}{N} + \frac{N-1}{N} (2 + d_N)$$$

the first term is the case in which the robot is lucky and goes up, that takes 1 step with probability 1/N; the second one is the probability of going down to one of the $N-1$ below standing children, than going up (2 moves) and the expected value $$$d_N$$$ itself. So, at the end the expression for $$$d_N$$$ is:

$$$d_N = N\frac{2N-1}{N-1}$$$

But it is not correct. Can someone explain me why please?

UPD: the first equation is correct, the final computation is not. As harshaa005 sais:

$$$d_N = 2N - 1$$$

harshaa005

$$$ d_N = \frac{1}{N} + \left(2 + d_N\right) \cdot \frac{N - 1}{N} $$$ $$$ d_N \cdot N = 1 + \left(2 + d_N\right)(N - 1) $$$ $$$ d_N \cdot N = 1 + 2(N - 1) + d_N \cdot (N - 1) $$$ $$$ d_N \cdot (N - N + 1) = 2(N - 1) + 1 $$$ $$$ d_N = 2N - 1 $$$

Your initial equal is correct. Somehow you must have done some mistake in calculation. I have used the same equation in my submission.

295662501

Oh, yes. Thank you!

waKey_waKey

On C I calculated the S(p) up to n = 8 to see the pattern. I did realize that the smaller numbers always ended up in one of the ends of the array and that they had a sort of logarithmic behaviour, like, the permutation changed based on powers of 2.

Though I had no idea how to enumerate them, and to realize afterwards that you can just decompose K into bits and just decide the position based on that is just crazy. Awesome problem, even if it costed me my Specialist.

literally same, i found the pattern, not by proof, but in a sort way where i was like, the more big stuff on one side the better, this is probably right and we cant make both sides big for each number, and in a notes document i wrote: "case on dropping to the left or the right, left makes smaller, right makes bigger." however, when I went to check it against samples for "4 6" i considered binary 6 instead of binary 5, so it wasnt right, I gave up on the idea, bricked my mental, and failed the contest

quater_nion

For Problem C I printed set of all permutations and tried to recognize a pattern. But Had a very difficult time imaplementing it, and also totally overlook that n is large and I cant use 1<<(n-1). That was my first experience handling such tricky constraints... Really learned so much in this single problem!!!!

Mostafa_Alaa99

Wow, I was just speaking about this point, but I think I handled it in a different way and yes I didn't have time to finish my work in the contest coz of this trick and another trick

I solved C in a different way, I just generated all of the permutations with the score of the maximum and the score of the maximum is the score of this permutation that you put the highest one in the middle then on its left the next maximum the on its right the next maximum and so on, so something like this will happen if n = 7

1 4 6 7 5 3 2

then this gave me this result when used n = 5

and from here I saw they are being repeated by powers of 2 until they reach n

look at the first item in the first 8 places it is 1 and then the others will be 2 in the next 4 perms

and so on, so I coded this pattern

then any number less than n will be printed by just looping from n to 1 and add any not-added-yet numbers

My Submission

theRealChainman

For problem E I can't figure out what is wrong with my approach. I see the editorial did something different, but I cam up with geometric distribution to solve it, and it gets till test case 4 and fails on the 138th query.

submission

You have a problem with dp. When you have several paths to the state, you set the value from the last path. Instead, assign the minimum value.

Change dp[u] = dp[v] + x to dp[u] = min(dp[u], dp[v] + x)

Also, you don't need modulo here, as the answer is always $$$\le$$$ n.

That worked, I was so close with my approach, instead of treating each movement as odd-even step, I just tracked the parity in the dp states, and the possible transitions based on the the current parity.

KisuraOP

In the Editorial of D：

$$$\text{We will write the values } n\cdot 2,n\cdot 2−1,n\cdot 2−2,\cdots \text{ to the vertices with odd depth in breadth-first order.}$$$

Maybe it is a mistake and should it be:

$$$\text{We will write the values } n\cdot 2,n\cdot 2−2,n\cdot 2−4,\cdots \text{ to the vertices with odd depth in breadth-first order.}$$$

CodeLegendX

YES, there is a mistake but in the code it is correct

sayglenn

Hi, could I check why in the first if block for C we must check for n <= 60? I'm unsure of the intuition behind it.

_ryomen_sukuna_

because for n>60 ,2^n will always be greater than k, so ans will always exist. So there is no need to compute 2^n for n>60 and also it will give integer overflow even in long long int.

k03495545

In B if n=11 and i make arr1=1 and then i make arr5=1 so for now two first type operations are needed and then i apply second type of operation(5/2<=2) and then applying in arr11=1 cant i get it in 3 operations only why the answer is 4 plz someone tell

djm03178

$$$\lceil$$$ and $$$\rceil$$$ represent ceil operator, so $$$\lceil {5 \over 2} \rceil$$$ is $$$3$$$, not $$$2$$$.

_Priyank

Here is how I solved problem C. Initially, I made some observations:- How will i get the max S(p)? -> By making the contributions of smaller numbers the least possible. How will i do this? -> starting with the current smallest no(which initially is 1) i can prove that it has to be placed either on the extreme left or to the extreme right of the current empty array. This can subsequently be done for the next current smallest values, all follow the same thing.

So getting the kth permutation:- When will the ans not exist? -> when k > no of perm which gives the max value (2 ^ n-1); As k<=1e12, this is only when n-1<40.

Now for each number in the permutation, we have two possibilities either place it in the first or last of the empty array. When right? -> temp = (1LL<<(n — cursmallest — 1)) if(k>temp) then cursmallest will be at the last and simultaneously update k = k — temp;

Elsewhere cursmallest goes to the left position.

Implementation 295706641

ascyrax_

The Editorial of problem D contains a typo in my opinion. The second solution should have "n.2, (n-1).2, (n-2).2,..." instead of "n.2, n.2-1, n.2-2,...". Please verify this once Igor_Parfenov

wasif2397

can someone explain C in more detail? i recognized the pattern but don't know how to generate the kth one. these are some first permutations for n = 5

permutations for n = 5

I might've missed some here...

Here are all the permutations that work for n = 5

Here are a couple of observations that I made, bolding the ones that were fairly important

A reversed permuation has the same score as the original
An element can only appear in the final equation at most (max_element-n+1) times, e.g if the permutation was of length 5, 5 could appear at most once, 4 could appear at most 2 times, etc. Therefore, in order to ensure that the sum is maximized, an element must appear the maximum amount of times that it is able to.
the first element from the back will be fixed for 1 permutation, the second element from the back will be fixed for 1 turn, third element 2 turns, fourth element 4 turns, and fifth element 8 turns (with fixed meaning up to that point, it's in the same position that it would be if the permutation was sorted)
An element will be a prefix or a suffix of the elements up to that point, e.g in the case where n = 5, 4 could either appear before or after 5, so the possible values of that subarray are 4 5 or 5 4, then once we get to 3, it can be 3 4 5, 3 5 4, 4 5 3, 5 4 3
Whether the nth element from the back is at the start or end of the elements up to that point depends on if the modulo value of k by 2^n is greater or less than 2^(n-1) (if it's less than 2^(n-1), it should be added at the front, otherwise at the back.

I hope this helped (sorry if it's hard to understand, I know I'm not the best at explaining)

really didn't understand the 5th point. i couldn't make the 4th observation but i had all the work done before that

I'll use the example of n = 5 and k = 9

Let's start with an empty list (I used a deque in my code, but a list will work to show how it works)

(I'll mention that I subtract 1 from k to perform the calculations, so k is equal to 8 in my calculations)

Now let's iterate from 5 to 1 and add the elements to the list

Since 5 is the first element from the back, we will check if k % 2^0 < 2^-1 (8 % 1 < 0.5). Since it's less than 0.5, we add it to the front, so the list is now [5]

Now let's go to 4, and check if k % 2^1 < 2^0 (8 % 2 < 1). Since this is true, we add it to the front, and the list is now [4, 5]

For 3, k % 2^2 < 2^1 (8 % 4 < 2) is true, so we add it to the front, and the list is now [3, 4, 5]

For 2, k % 2^3 < 2^2 (8 % 8 < 4) is true, so we add it to the front, and the list is now [2, 3, 4, 5]

For 1, k % 2^4 < 2^3 (8 % 16 < 8) is false, so we add it to the back, and the list is now [2, 3, 4, 5, 1]

Our final list is [2, 3, 4, 5, 1]

lightninGod100

Problem 2 — Can someone explain me the 4 cuts for n=20? My understanding says we require atleast 5 operations of type A performed on i=1,4,8,16,20.

hint: 3 cuts are enough for 5 <= n <= 10

fun fact: problem E can be solved without modulus operation.

Submission: 295789260

I learned something new from problem F

ckxian

can somebody explain c in detail

vstiff

16 months ago, hide # ^ |

Consider how many times each element appears in formula. For example, for n=9 it's [9, 16, 21, 24, 25, 24, 21, 16, 9]. This means that smallest number should be placed at the edges, to affect less segments. After you placed $$$x$$$, it will change number of segments $$$x+1$$$ will affect, so this can be viewed as placing numbers starting from $$$x+1$$$ in empty array of length $$$n-1$$$.

aijaz

16 months ago, hide # |

For problem B The tutorial/system gives answer = 3 for n = 5

But, Let's say I want to put 1 at the index 1 and 4. Means the intermediate array looks like [1,0,0,1,0]. Here because of the operation 2 the array will become [1,1,1,1,0], correct? and at last you choose R = 5 and L = 1. With this your entire array will become [1,1,1,1,1]

So total of 1st operations used is equal to 2, right? Instead of 3.

Can someone correct me where I am missing.

suyasht99

In order to apply operation of type 2, both a[l] and a[r] should be equal to 1. In your case, a[5] is 0, and hence you cannot apply the operation of type 2.

sneha_k

if you directly put a[1]=1 and a[5]=1 using first operation, i can apply second operation directly to get [1,1,1,1,1] (since 1+1=2=[(5-1+1)/2], and i assume [.] to be floor. shouldn't the answer be 2 then?

nvm it is ceil, question did not specify it

12 months ago, hide # ^ |

Apologies, I checked this notification after 5 months. I have completely forgotten about the question at this point of time. xD

T404

Late note: problem E can be solved in $$$\Theta(n + q)$$$ using the fact that $$$\sum d_u = \Theta(n)$$$.

Kcits970

How do you even think of C? I can understand the editorial and follow along, but the idea is just so unexpected.

10 months ago, hide # |

Why did problem F become pdf

https://mirror.codeforces.com/contest/2040/problem/F

Mr_Bald

10 months ago, hide # ^ |

It is a general issue, meaning not specific to this particular problem.

See this blog

For D, I solved it by finding the diameter of the tree. Say we got a diameter from node u to node v with $$$m$$$ vertices on it, then we just assign the values 1, 2, 3, ..., m to the vertices on the tree. After that, we loop through the diameter's vertices, explore all branches, and assign the remaining values (i.e., from $$$m + 1$$$ up to $$$n$$$) to vertices on those branches. The assignment is simple: at each vertex, we find the first remaining value that satisfies our condition and assign it to it.

Solution implementation: 325626482

Igor_Parfenov's blog