Problem E originally meant a solution without a gready, but what are rich in :)

And in F you need to separately figure out when the first / second player wins if he starts at his top, because otherwise it hurts a lot)

any intuitive / formal proof to D ? i have a weird one that i'll write when i have time

why is cout.flush() not required in question C?

:< could someone explain why cout<<ceil(double(n) / min(x,y)); in A led to WA

My solution for problem C:

• First binary search to find maximum consecutive one and zero's. You can binary search over array such as [0, 1, 11, 111, 1111 ...] for 1 and when result of binary search is 0 for 1 that means there aren't any 1 in password.

• Now you can try both possible combination of max consecutive one and max consecutive zero. For ex let's say max_consec_one = 3, max_consec_zero = 4, so either 1110000 or 0000111 has to be a substring.

• From the above example if max_consec_one = 3 and 1110000 is valid substring that means on left of this substring there has to be some amount of zero's and same logic for right. To find this cnt of zero's for left and one's for right you can again binary search.

• You can repeat above step until string t reaches the size n of the original string.

I don't know how to prove that it is less than n * 2 queries, but I think it is. I don't know whether this approach is correct. I think my solution has some sort of implementation mistake. Here's my submission

Can someone help me to find out if my approach is incorrect or implementation?

can anyone explain problem D and E solutions for like why we did what we did . The intuition behind them.

You should add the binary search and prefix sum solutions to D as well.

As Sol2/Sol3.

So in D you literally said "here is the solution" no explanation to the logic or why it works

can someone explain the solution to problem D

can someone explain the solution to problem D

sub link Can someone tell me why this is wrong? It's the same as the editorial, only difference being i wrote a simulation for the checking part

Wait so long for the editorial

In problem C: What if there is a substring of the form both t+0 and t+1 in the original string?

Regarding E's time complexity as $$$O(n\log^2W)$$$ may be better.

In d question what is the binary search approach ?? minimize the maximum and find largest and smallest element and maximize the minimum and find the largest and smallest element and then compare both the difference whichever will be smaller will be our answer ??

In F1, I was trying a solution with simultaneous BFS (from 1 for Alice, and from u for Bob). It doesn't work, but I don't know why. I would appreciate if someone could point out the edge case. At each step, Alice goes to EVERY unseen node in her frontier, marking it as 'seen', after that the neighbours of each of these nodes become her next frontier. Then Bob does the same thing. If at any point a player's frontier is empty, or only have 'seen' nodes, and its that players turn, the player loses.

Wansur I have a practice submission for problem D which was accepted, but I believe it shouldn't, as it has $$$O(n^2)$$$ time complexity. Here's the submission 282154960, and here's a test generator that should make it TLE:

#include <iostream>
int main() {
  const int mx = 100000;
  std::cout << "1\n" << 2 * mx << '\n';
  for (int i = 1; i <= mx; i++) {
    std::cout << mx << ' ';
  }
  for (int i = 1; i <= mx; i++) {
    std::cout << i << ' ';
  }
}

I'm posting this here because there isn't a way to hack my own submission to a past contest.

For those of you who don't understand what the tutorial of E is saying:

We want to prove that $$$F(a_1,a_2,\cdots,a_n,x) \ge F(x,a_1,a_2,\cdots,a_n)$$$ where $$$F$$$ is the sum defined in the problem and $$$x$$$ satisfies $$$x < a_1$$$. If this is true, there always exists an optimal solution where is the smallest element is re-arranged to the first position. Here is the proof:

$$$F(a_1,a_2,\cdots,a_n,x) = (\color{red}{a_1}) + \gcd(a_1,a_2) + \gcd(a_1,a_2,a_3) + \cdots + \gcd(a_1,a_2,\cdots,a_n,x)$$$

$$$F(x,a_1,a_2,\cdots,a_n) = (\color{red}{x + \gcd(x,a_1)}) + \gcd(x,a_1,a_2) + \gcd(x,a_1,a_2,a_3) + \cdots + \gcd(x,a_1,a_2,\cdots,a_n)$$$

Because $$$x < a_1$$$ and gcd is always smaller or equal the the difference of two numbers, we have $$$\gcd(x,a_1) \le a_1 -x \implies x + \gcd(x,a_1) \le a_1$$$.

For the rest of the terms, it is easy to observe that the term below is always less than or equal to the corresponding term above since $$$x$$$ is added in the calculation.

someone kindly explain solution for problem D in a bit elaborate.The tutorial is of no use

Your proof for problem C seems incorrect to me.

In your proof, you mentioned However, after this iteration, we will make only 1 query. But what if that iteration does not exist? For example, you coincidentally reach a suffix of size $$$n - 1$$$ for $$$t$$$, which may take $$$2(n-1)$$$ queries. And after $$$2$$$ more queries, you realized that your $$$t$$$ has reached the end of $$$s$$$. So you need $$$1$$$ additional query to know whether the first character is '0' or '1'. In total, this is $$$2(n - 1) + 2 + 1 = 2n + 1$$$ queries.

In your reference implementation, this case does not actually happen but you may need to address it in your proof.

why is the problem D explained without explanation?

can someone give some elaborative solution to problem D.the tutorial doesn't explain anything imo

someone explain solution for task D in a bit elaborate manner.the tutorial is of no use

In case you still don't understand the tutorial of D:

The key observation here is: If two consecutive elements $$$a_i > a_{i+1}$$$, it is always not bad to "mix them up", i.e. assign $$$a_i := \lfloor{\frac{a_i+a_{i+1}}{2}}\rfloor$$$ and $$$a_{i+1} \to \lceil{\frac{a_i+a_{i+1}}{2}} \rceil$$$. For instance, (10,1) -> (5,6) and (8,4) -> (6,6). The reason is that: 1. The answer is not worsen since the range is smaller. 2. If in the optimal operation sequence the value of $$$a_i$$$ is transferred to some element of large index instead of $$$a_{i+1}$$$, it is always valid to transfer it from $$$a_{i+1}$$$(Why?).

Автокомментарий: текст был обновлен пользователем Wansur (предыдущая версия, новая версия, сравнить).

Problem C can also be solved with O( n + 2 * log(n) ) complexity. Use binary search to find the longest continuous string of 0's using queries. Then we can build the right side of the string with 1's and check with queries. If it's not a substring we replace the 1 with 0 and continue until we reach fill the string or we end up with more 0's consecutively than what we found to be the longest. Next we use binary search to query how many of the ending 0's are also apart of the confirmed substring we know from the last query section. This will finish constructing the right side of the string. To find the answer, we now add 1's to the front of the string and query, if it's not a substring then the answer is to replace the 1 with a 0.

• My solution for problem D :

Why the code of F1 can solve the problem in O(n)? Thank you!

Problem D. I saw a solution that we can binary search upper and lower bounds simultaneously. And I had tried this and got AC. But I'm very confused that how to prove this two independent operations is correct?

In the case of a buffed up C , how to get to the answer in less than 2*N queries?

I wrote a more detailed editorial for problem D, if anyone is interested https://codeforces.net/blog/entry/134292

In the D problem, in authors solution as we are putting any element in stack only if it is larger than the previous one, as result max is at the top of stack and min should be at bottom, so taking minimum of all elements of stack(first element) should also give minimum but it is giving wa on tc3. Also, since the tc is large i cant work it out, any idea as to what might be the problem. WA_solution

Thanks in advance

[DELETED]

Could anyone share the DP solution for E? Please brighten me :))

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
// #include "..\debugging.h"
#endif

#define int long long
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pi = pair<int, int>;
using vvi = vector<vector<int>>;
using vcb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using mi = map<int, int>;
using si = set<int>;


#define endl "\n"
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define fmap(name, x) mi name; for(auto it:x) ++name[it]
#define F first
#define S second
#define elif else if
#define PB emplace_back
#define MP make_pair
#define REPi(a, b) for (int i = a; i < b; i++)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define REPO(a) for (int i = 0; i < a; i++)
#define vvl(ab, r, c, v)  vvi ab(r, vector<int>(c, v))
#define dbg(v)  cout << #v << " = " << (v) << endl;

const long long mod = 1000000007ll, mod2 = 998244353ll;

int dist(vvi &tree, int p, int node, int p2 = -1) {
    int ans = 1;
    for(int c: tree[node])
        if(c != p && c != p2) {
            ans = max(ans, dist(tree, node, c )+1);
        }
    return ans;
}

void path(vvi &tree, int node, int target, int p, vi &ans) {
    for(int i: tree[node]) {
        if(i == p)
            continue;
        ans.PB(i);
        if(i == target) {
            return;
        }
        path(tree, i, target, node, ans);
        if(ans.back() != target)
            ans.pop_back();
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;

        vvi tree(n);
        for(int i=1; i<n; ++i) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            tree[u].PB(v);
            tree[v].PB(u);
        }

        int u, v;
        cin >> u >> v;
        --u, --v;

        vi adist(n, 0), bdist(n, 0), p = {-1, 0};
        path(tree, 0, u, -1, p);
        p.PB(-1);

        int m = p.size()-2;
        vi dp(m);

        for(int i=1; i<m+1; ++i)
            dp[i-1] = dist(tree, p[i-1], p[i], p[i+1]);


        vi a(m), b(m);
        for(int i=m-1; i>=0; --i) {
            a[i] = dp[i] + i;
            b[i] = dp[i] + m-i-1;
        }

        vi suffdp(m, b.back());
        vi predp(m,a.front());
        for(int i =1 ;i<m-1;i++){
            predp[i] = max(a[i],predp[i-1]);
        }
        for(int i=m-2; i>=0; --i)
            suffdp[i] = max(suffdp[i+1], b[i]);

        // dbg(p);
        // dbg(a);
        // dbg(b);
        // dbg(dp);
        // dbg(suffdp);
        // dbg(predp);


        int start = 0, end = m-1;
        int counter = 1;
        while(start < end){
            if(counter && a[start] > suffdp[start+1] || !counter && b[end] > predp[end-1] ){
                counter = !counter;
                break;
            }
            if(counter)
                start++;
            else
                end--;

            counter = !counter;
        }

        if(start == end)
            counter = !counter;
        cout << (counter?"Bob" : "Alice") << endl;
    }

    return 0;
}

can someone explain why this is wrong for F1.

Basically I tried to find the path from 1 to u. For every path value I found Dp(max depth not on path)

then I checked for early exit. If this makes sense

How to prove problem e in detailcc?

I wonder in problem E.Is there a dp in The right time complexity ? Like "wuhudsm"we can Note dpi,j as the max sum when gcd(a1,…,ai)=j.But at least it cost O(n*n),because enumerate i cost N,and State transition cost N. It is at least O(N*N）

So can we have a rigorous mathematical proof for the solution of problem B？

What does the $$$A$$$ and $$$B$$$ in the editorial of E actually mean? are they single element or sequence?

the $$$A$$$ and $$$B$$$ in E's editorial are sequences, or elements, or the gcd of a sequence?

Can anyone find the issue with my approach to Problem D?

https://pastecode.io/s/e7awhp5j

problem E is god tier. loved it

I really struggled to understand 2013F2, which I guess makes sense because it's rated 3500 for a reason.

tldr; the idea is, for each node $$$x$$$ Bob starts at, we can compute the earliest turn at which Alice beats Bob and Bob beats Alice. If Alice's "win turn" is <= Bob's "win turn" then Alice wins, otherwise Bob wins.

After studying the code and attempting it myself for several days I'd like to offer a somewhat different and more detailed explanation of F2 that I think is more direct. The $$$(l_j, r_j)$$$ stuff is correct but I think makes the logic look harder than it is.

F1 variant: the game simplifies to the following:

• there is a simple path connecting Alice and Bob, Alice at $$$1$$$ and Bob at $$$m$$$
• the graph is a tree and no backtracking is allowed
• therefore if Alice or Bob ever walks off the path at node $$$i$$$ into a subtree then they can't return. Therefore they have moves equal to the max height of that tree plus 1 moves remaining, and their opponent has free reign to explore the rest of the path. Alice can get up to $$$i-1$$$ and Bob can get down to $$$i+1$$$

Let's start with the F1 version where we only need to find the winner for a single start vertex. The solution proceeds as follows, let $$$m$$$ be the number of nodes in the $$$1$$$ to $$$u$$$ path:

• if Alice can walk off the path at $$$1$$$ and have more moves than Bob walking off anywhere in $$$2..m$$$ then Alice wins. Otherwise Alice steps forward
• if Bob can walk off the path at $$$m$$$ and have more moves than Alice walking off anywhere in $$$2..m-1$$$ then Bob wins. Otherwise Bob steps forward
• iterate this until someone wins by stepping off, or runs out of moves. Use a segment tree to make the max on the ranges fast.
• whichever player has the earlier "win turn" wins, if there is a tie then Alice wins because she moves first on each turn.

F2 variant: this one is harder because Bob can now be at any position on the simple path between $$$u$$$ and $$$v$$$. As the editorial says this path is a subset of the union of $$$1..u$$$ and $$$1..v$$$ so we can solve for all nodes on both of those paths, and then iterate over the $$$u$$$ to $$$v$$$ path at the end and print the answers.

The idea is the same as the F1 version, but this time we need to compute Alice and Bob's win turns for each of Bob's positions.

Alice win turns: if Alice turns off the path at $$$i$$$ then she has $$$t_i \equiv h_i + 1$$$ moves remaining. She will beat Bob at

• $$$i+1$$$ right now if $$$a_i > t_{i+1}$$$
• $$$i+2$$$ as well if $$$a_i > \max(t_{i+1}+1, t_{i+2})$$$, because Bob can go off the path at $$$i+2$$$, or can take one step to $$$i+1$$$ and then step off
• as noted in the editorial we can find the latest position $$$r$$$ using binary search because the right-hand side increases monotonically in $$$r$$$; $$$r+1$$$ increases the the moves at $$$i+1..$$$ and also adds a new option for Bob turning off
• given that Alice is at $$$i$$$ this means $$$i$$$ turns have elapsed; Bob's starting positions are at $$$2*i+1 .. i+1+r$$$
• and now we know that Alice will win at turn $$$i$$$ against Bob at those positions
• there will be multiple $$$i$$$ that win against each starting position $$$x$$$ for Bob. These positions are equivalent to turn numbers. Alice obviously wants to win as soon as possible so we'll record the minimum Alice "win index" $$$i$$$ for each Bob start position $$$x$$$

Bob win turns: similar logic to Alice's win turns. The idea is the Alice win turns are correct, but they assume that Bob has not already won. So we do another loop from Bob's perspective to find his earliest win turn at each index; if they're the same or lower then Bob wins. The idea of finding a win turn of ranges of Bob start positions is the same, but the details are a bit more complicated:

• if Bob turns off at $$$i$$$ then he'll win against Alice if $$$t_{i} \geq t_{i-1}$$$, this time it's $$$\geq$$$ because Alice must move first, e.g. if she has 1 move remaining, and Bob has one move remaining, then Alice loses at the top of turn 2.
• he'll also win against Alice if $$$\max(t_{i-2}, t_{i-1}+1) <= t_i$$$
• again this turns into a binary search on the left bound $$$l$$$ such that Bob, if he reaches $$$i$$$, will win against Alice if she's at $$$l..i-1$$$
• and again this means that $$$l..i-1$$$ turns elapsed for Alice to get there. So Bob turning off at $$$i$$$ means he started at $$$i+l-1 .. 2*i-2$$$ in $$$l-1..i-2$$$ turns, respectively
• the turn number varying over $$$l-1..i-2$$$ makes it hard to update an efficient structure later. Instead, we notice that the earliest turn number comes from the latest $$$i$$$ where Bob descends. If Bob descending at $$$i_1$$$ and $$$i_2$$$ both result in victory for Bob if he starts at $$$x$$$, then the earliest turn is $$$x - \max(i_1, i_2)$$$. So we record the maximum turnoff index $$$i$$$ for each starting position $$$x$$$.
• finally, having record the max $$$i$$$ for each starting position $$$x$$$, at the end we can compute the win turn from $$$x-i$$$. In other words, if Bob starts at $$$x$$$ and can win against Alice at positions $$$i_1, i_2, ..$$$ then he'll pick the latest one because that's the fewest moves, earliest turn.

This last point is where the mysterious fa[x] <= x-fb[x] comes from in the sample code (the code uses $$$i$$$ in place of $$$x$$$; I used separate symbols for current position $$$i$$$ versus starting position $$$x$$$ to hopefully reduce confusion).

The code uses an interesting multiset approach for finding the minimum win index. If an index is valid for a range of Bob start positions $$$x1..x2$$$ then $$$i$$$ is put in add[x1] and rem[x2]. These record when to add and remove candidate indices as we iterate over x values. The multiset makes it easy to find the min and max after doing the updates. At x we add all indices in add[x], find the min/max, then process rem[x] because the x1..x2 intervals are inclusive.

Instead of the clever multiset you can use a min segment tree for Alice's win turns and a max segment tree for Bob's win turns (technically Bob's win indices as discussed above). Same linearithmic runtime but easier copy-paste if you have a reference segtree implementation handy (I think copy-paste from a personal repo is acceptable here but idk for sure).

Hey, for the solution shared for 2013F1 — Game in Tree (Easy Version), the last paragraph mentions that it can be proven that instead of using a segment tree or sparse table, one can simply iterate through all vertices on the segment and terminate the loop upon finding a greater vertex. This approach will yield a solution with a time complexity of O(n).

I am unable to prove this, so was hoping if someone could help me out with it. Thanks!

I am curious about the trivial solution presented for question F1. It's claimed that the time complexity of trivial loop is $$$O(n)$$$, but I cannot see why. (Though I have to admit that, to me it really looks like the trivial solution has linear time complexity)

Another solution to D:
1) $$$max = max$$$ of all possible suffix average ceil.
2) $$$min = min$$$ of all possible prefix average floor.
3) $$$ans = max - min$$$.
ref: https://codeforces.net/contest/2013/submission/285605752

It was difficult for me to explain why the solution fits within 2n queries in problem C. So, I slightly modified the approach as follows: In the first query, I ask for two values ("00" and "11"). If both are false, I can determine that the answer is either 0101... or 1010...I proceed with the same method as explained in the solution.This reduces the number of queries by two.so 2n.

I tried to code for E but failed on Hidden Test Case .Can Anyone tell me what's wrong with solution //this is the codde ~~~~~ int n; cin >> n; vector vec(n); for (int i = 0; i < n; i++) { cin >> vec[i]; } sort(vec.begin(), vec.end());

// map<int, int> mpp;
    vector<pair<int, int>> sortedMap;
    for (int i = 1; i < n; i++) {
        int temp = __gcd(vec[i],vec[0]);
        int x=vec[i]/temp;
        int y=vec[0]/temp;
        sortedMap.push_back({vec[i],x%y});
        // mpp[vec[i]] = x % y;
    }



    sort(sortedMap.begin(), sortedMap.end(), sortByValue);
    // sort in descending order


    int ans = vec[0], temp = vec[0];
    for (const auto& it : sortedMap) {
        int gcd = __gcd(temp, it.first);  
        temp = gcd;
        ans += temp;
    }

    cout << ans << endl;

~~~~~

Wansur is GrandMaster now! orz

Wansur is now red hooray!