Auto comment: topic has been updated by FelixArg (previous revision, new revision, compare).

Auto comment: topic has been updated by FelixArg (previous revision, new revision, compare).

Auto comment: topic has been updated by FelixArg (previous revision, new revision, compare).

Another solution for div1 D is to just simulate the brackets until you fail. At that moment change this bracket to something else (because you don't know what to change it to, keep all (at most 3) possibilities. At the end the one closest to (0, 0) will give you the minimum changes required.

362523300

Truth be told, I did not manage to prove that this is correct. It is mostly intuition from the simplified problem of only one type of paranthesis (only change when prefix is negative and resolve the end). Would be great if someone could prove/disprove/hack this solution

We can do Div1E in $$$O((n+m)\log (n+m))$$$ time (with no factors of $$$k$$$).

We want to find the maximum $$$d$$$ where:

• Given $$$p_t$$$ , $$$p_s$$$ , and $$$\ell \geq 1$$$ . We can assume $$$s_{p_s}s_{p_s+1}\dots s_{p_s+\ell-1}=t_{p_t}t_{p_t+1}\dots t_{p_t+\ell-1}$$$ .
• There exists a substring of $$$s$$$ which matches to the pattern : ($$$t_{p_t}t_{p_t+1}\dots t_{p_t+\ell-1}$$$) + (an arbitrary character) + (the following $$$d$$$ characters)

Consider all the positions $$$q$$$ of substrings of $$$s$$$ such that $$$s_{q-\ell}\dots s_{q-2}s_{q-1} = t_{p_t}t_{p_t+1}\dots t_{p_t+\ell-1}$$$ . These positions form a segment in the suffix array of the reversed $$$s$$$ . Associate the suffix of the reversed $$$s$$$ ($$$s_{q-1}s_{q-2}\dots$$$) with a suffix of $$$s$$$ ($$$s_{q+1}s_{q+2}\dots$$$). Now we just need to find the maximum LCP between the following characters in $$$t$$$ and $$$s_{q+1}s_{q+2}\dots$$$ , but the value $$$q$$$ must be taken from the corresponding segment of the suffix array of the reversed $$$s$$$ .

Eventually, the task is reduced to a typical query: find the minimum element in a subarray $$$(a_l, a_{l+1}, \dots , a_r)$$$ but no less than $$$x$$$ (and also the maximum but no greater than $$$x$$$). This can be solved using a wavelet matrix.

362520685

FelixArg Please fixed the given code for div2A. I think it was written for div2B.

brute force has passed div2 D: https://mirror.codeforces.com/contest/2197/submission/362486786

2196C2 is a wonderful problem!

really a bad contest for me can't debug the div 2 B . can anyone one help me to find the test case where this code not working 362482618. my idea is that all the same elements should be consecutive in array a,and there should not be any diagonal intersection ie- p=1,2 a=2,1 and after storing the index of all the same elements. I will check if the p[i]->index of i in the permutation is in the range of min(i)-1 and max(i)+1,where min(i) is the minimum index of i in the array a and max(i) is the maximum element in the array a. because we can copy one forward and one backward . if i is not present in the array leave it.

I found a binary search solution for div2A. The idea is that suppose an infinite sequence of integers where $$$i$$$^th element of the sequence is $$$i - d(i)$$$ where $$$d(i)$$$ equals to the sum of the digits of $$$i$$$. Then this sequence will be non-decreasing. So we can binary search for $$$x$$$ in this sequence taking the lower bound and upper bound in a way such that any $$$x$$$ in the given range $$$1≤x≤$$$$$$10$$$^$$$9$$$ can be found if present. If $$$x$$$ is present, then the answer is $$$10$$$, otherwise $$$0$$$. You can see my submission 362438894 for implementation. In this code, I have also utilized the fact that $$$x$$$ must be divisible by $$$9$$$ to be in the sequence, which i guess was not necessary to check.

My idea for div2 D was to speedup the bruteforce method and avoid recalculation. When iterating over k for $$$j = i + k \cdot a_i$$$, for a given $$$i$$$, we will do the calculations considering the pair $$$(a_i, i \ mod \ a_i)$$$. This means that for any index $$$j$$$ that we encounter in further iterations in which $$$(a_j, j \ mod \ a_j) = (a_i, i \ mod \ a_i)$$$ we can skip it, as we have previously calculated its pairings. The idea behind that is that for all indices with this pairing, they would go through the same $$$j$$$'s and have the same value for contributing to the equation.

When finding such a pair which has not been calculated previously, we can maintain a set with all indices $$$j$$$ where $$$a_j=a_i$$$ and incrementing the answear if $$$j-a_i \cdot a_j$$$ is in the set.

My code: 362526064

The complexity is roughly $$$O(n \sqrt{n} log(n))$$$, i feared receiving a tle but then i noticed that it would be fast enough with 5 minutes for the contest ending and got AC.

I believe the memory limit of E2(div1) is too small. You will immediately get MLE if you build two SAMs.

void solve(){
    //for div2D
    int n;
    cin>>n;
    vector<int> a(n);
    int ans=0;
    forn{cin>>a[i];}
    forn{
        int c=a[i];
        int j=i-c;
        int count=1;
        while(j>=0&&count<a[i]){
            if(a[j]==count){
                ans++;
            }
            j-=c;
            count++;
        }
        j=i+c;
        count=1;
        while(j<n&&count<=a[i]){
            if(a[j]==count){
                ans++;
            }
            j+=c;
            count++;
        }
    }
    print(ans);
}

There's a $$$O(m\sqrt{n\Sigma})$$$ for div1E, where $$$\Sigma = 26$$$ is the size of alphabet. For a string with length $$$L$$$, there's at most $$$L\Sigma$$$ different possible strings, and we maintain all of their positions in SAM. When the length $$$L$$$ exceed a threshold $$$B$$$, do the bruteforce in $$$O(n)$$$ mention in the solution for E1.

Here the time complexity is $$$\frac{m}{B}\cdot \Sigma \cdot B^{2} + \frac{m}{B} \cdot n$$$, which is $$$O(m\sqrt{n\Sigma})$$$ when $$$B = \sqrt{\frac{n}{\Sigma}}$$$. The first part of the solution is not full and the solution is easy to squeeze.

I wrote a brute-force for div1 E1. The time complexity is O(n*m) and I passed by making constant number small.

362519663

Can this be hacked?

In the Div2A editorial, why do we need to check the range from x to x + 83? The problem states that x is between 1 and 10^9, so shouldn’t we only need to check i in the range from x to x + 81?

ConstraintForces

Tried hell a lot to debug div2B, pls help

my approach: in a map i store, the indices where each element appeared in the permutation array. an integer pivotIndex, indicates, till now, which was the last element from which we copied values. [to be precise, if I am at some index i, then pivotIndex represents the index of the element used to correct the p[i].] i iterate through the permutaion array, there will be three possibilities

1. p[i] = a[i], then pivotIndex = i; i++;
2. p[i] != a[i], then a. mp[a[i]] < i and mp[a[i]] >= pivotIndex, then we can copy required value, new pivotIndex = mp[a[i]]; i++;

b. mp[a[i]] > i, then check if till required index, all elements are a[i] only, if yes, very nice new pivotIndex = mp[a[i]];

else not possible

// my soln code
void solve()
{
    num n; cin >> n;
    vector<num> p(n);
    map<num, num> mp;
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        mp[p[i]] = i;
    }
    int pivotIndex = 0;
    vector<num> a(n); for(auto& x : a) cin >> x;
    bool solved = true;
    for(int i = 0; i < n; i++)
    {
        if(p[i] == a[i]) {pivotIndex = i; continue;}
        else
        {
            if(i > 0 && mp[a[i]] < i && mp[a[i]] >= pivotIndex) {p[i] = a[i]; pivotIndex = mp[a[i]];}
            else if(i < n-1 && p[i+1] == a[i]) {p[i] = a[i]; pivotIndex = i+1;}
            else if(i < n-1 && mp[a[i]] > i)
            {
                int j = i+1;
                bool possible = true;
                while(j!=mp[a[i]])
                {
                    if(a[j] != a[i]) {possible = false; break;}
                    else {p[j] = a[i]; j++;}
                }
                if(possible) {p[i] = a[i]; i=j-1; pivotIndex = mp[a[i]];}
                else {solved = false; break;}
            }
            else {solved = false; break;}
        }
    }
    cout << (solved ? "YES\n" : "NO\n");
}

I tried C) fraction by say let say we start with 10,14 now its not 2/3 so we find next 2/3 ratio which is 8 and 12, now alice wants to make it 7 ( 8-1) as soon as possible, while Bob only has to made 14 to 12, so Bob needs 2 Alice needs 3, thats not possible even if Alice plays first, so Bob wins, this approach was not working for this big sample test case, 7000000000000000 10487275715782582, as I was not able to find which is the next closest p/q=2/3 ratio values of p and q are, so I used a loop for it but that loop is not stopping so I took some help from claude but still its not working this is my https://mirror.codeforces.com/contest/2197/submission/362586660

code const fs = require('fs');

const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let w = 0;

const T = Number(data[w++]);

for (let t = 0; t < T; t++) {

    const p = BigInt(data[w++]);
    const q = BigInt(data[w++]);

    const half = p / 2n;

    if (q === half * 3n) {
        console.log('Bob');
        continue;
    }

    if (p >= q) {
        console.log('Alice');
        continue;
    }

   // let count = (half * 3n > q) ? half - q / 3n : 0n;

    let count = (half * 3n > q) ? (half * 3n - q + 2n) / 3n : 0n;

    const req1 = (half - count) * 2n;
    const req2 = (half - count) * 3n;

    const diff1 = (p - req1) + 1n;
    const diff2 = q - req2;

    if (diff2 < 0n) {
        console.log('Alice');
        continue;
    }

    if (diff1 + 1n <= diff2)
        console.log('Alice');
    else
        console.log('Bob');
}

Loved the contest but its sad that Div2D, people got their n^2 sol passed.

This is my thought process when writing Div1 D:

We can obviously think of a wrong simple greedy approach: remove all legal bracket matches, and it is easy to find that the remaining ones need to be paired up, so we can directly divide the number of remaining ones by 2

We can find an obvious counterexample to prove the approach is incorrect: when the sequence of parentheses we remove is )(, no matter what, we need to perform two operations to make it valid.

However, we found that this situation is very rare, and the approach only goes wrong when the parenthesis sequence grows into a pattern like )))(((. Therefore, after special handling, this problem can be solved

My Div2 A solution:

Let's think about denoting $$$y$$$ in the decimal notation. If $$$y = 100 a_2 + 10 a_1 + a_0 \; (0 \le a_i \le 9)$$$, then $$$d(y) = a_2 + a_1 + a_0$$$, so $$$x = y - d(y) = 99 a_2 + 9 a_1$$$.

More generally, if $$$y$$$ is denoted as: $$$\displaystyle y = \sum_{i=0}^n 10^i a_i \; (0 \le a_i \le 9)$$$, then $$$\displaystyle x = \sum_{i=1}^n (10^i - 1) a_i$$$. Note that $$$a_0$$$ does not appear in $$$x$$$, because $$$(10 ^ 0 - 1)a_0 = 0$$$. Since $$$x \le 10^9$$$, having $$$n = 9$$$ is sufficient.

Therefore, for every $$$a = [a_1, a_2, \ldots, a_9]$$$ such that $$$\displaystyle x = \sum_{i=1}^9 (10^i - 1) a_i$$$, you have $$$10$$$ different numbers of $$$y$$$ that satisfies $$$y - d(y) = x$$$ (you have $$$10$$$ here because you can choose $$$a_0$$$ freely).

It turns out the representation of $$$a$$$ is unique for $$$x$$$ that can be denoted in the above way.

Proof. The maximum value that can be represented in $$$m$$$ digits is:

The minimum unit of the $$$(m+1)$$$-th digit is $$$\displaystyle 10^{m+1} - 1$$$, which is larger than $$$M$$$. This means that you can greedily determine the values of $$$a_i$$$ from the higher digits $$$(a_9, a_8, \ldots, a_1)$$$ without negative consequences. So, you can consider this $$$a$$$ as some form of positional notation system, where only some set of numbers can be represented.

So, the final answer is $$$10$$$ if you can find a suitable $$$a$$$ with the above greedy method. Otherwise the answer is $$$0$$$.

B is a great problem

I am so consufed about Div1E1. With the limitations as they are a light-weight $$$O(nm)$$$ solution passes with flying colors: 362473782.

Can someone help me with div2.E? I just can't find the mistake. WA on test 7.

For the div2D, why is it enough to check upto k < sqrt for a[i] < sqrt? Isn't it possible that there are some answer where k >= sqrt?

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define srt(a) sort(a.begin(), a.end())
    #define srtr(a) sort(a.rbegin(), a.rend())
    #define cyes cout<<"YES"
    #define cno cout<<"NO"
    #define pii pair<int,int>
    #define deb(a) for(int x:a) cout<<x<<" "
    #define rev(a) reverse(a.begin(), a.end())

    vector<int> qry(int k){
        cout<<"? "<<k<<endl;
        int q; cin>>q;
        vector<int> a;
        if(q==0) return a;
        for(int i=0; i<q; i++) {int x; cin>>x; a.push_back(x);}
        return a;
    }

    void solve(){
        int n;
        cin>>n;
        
        vector<int> path_len(n+1);
        path_len[1]=1;
        vector<pii> adj;
        int k=2;
        while(1){
            vector<int> p=qry(k);
            int q=p.size();
            if(q==0) break;
            if(q>=2) adj.push_back({p[q-2], p[q-1]});
            for(int i=0; i<q-1; i++){
                path_len[p[i]]++;
            }
            if(path_len[p[q-1]]==0) path_len[p[q-1]]++;
            k+=path_len[p[q-1]];
        }
        
        cout<<"! "<<adj.size()<<endl;
        for(auto [u,v] : adj) cout<<u<<" "<<v<<endl;
    }

    int32_t main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int tc;
        cin>>tc;
        while(tc--){
        solve();
        //cout<<endl;
    }

        return 0;
    }

Can anyone help me find where i am going wrong and a counter example would be really appreciated where my code takes more than (n+m) queries. My logic may be entirely or partially incorrect. Thanks!

Loved the problem Div2/E2 :3

Can someone tell me why my same solution for Div2D is giving tle when using map 362858481 but passes when using set 362858833 ?

Edit: I found the problem.

In div2D, isn't it a typo?

"If $$$a_i \geq B$$$ and $$$a_j \lt B$$$, then the pair will be counted when we iterate through candidates for j;" — shouldn't it be "candidates for i"?

I assume i < j and for $$$a_j \lt B$$$, when j is fixed, only indices i>j would be considered (according to strategy "iterate through candidates only forward"). If i would be fixed instead, we're guaranteed there won't be more than $$$\lceil\sqrt{n}\rceil$$$ checks (total for both sides, forward and backward) for j ("it is $$$\frac{n}{B}$$$") and that mentioned pair would be covered.

can someone please explain div2 D in simpler terms

Another solution for B div1:

let d be the the distance j — i (d = j — i), x = a[i], y = a[i].

x * y = d.

let x = min(x, y), y = max(x, y).

we know that x <= sqrt(d) and y >= sqrt(d) ==> y ^ 2 >= d.

we also know that d % y = 0, i.e. d = c * y where c is some constant. Hence, y <= d.

since d is the difference of the indices, it's max value is n — 1, we can write it as d <= n for the sake of simplicity.

y <= d <= min(n, y ^ 2), but d = c * y

y <= c * y <= min(n, y ^ 2), dividing by y we get

1 <= c <= min(n / y, y), that worst case for min(n / y, y) is y = sqrt(n). Hence, 1 <= c <= sqrt(n).

we can iterate through the elements of the array supposing the current element is the max between the elements in the pair (i.e. y in the explanation), and brute forcing the value of c to get every possible value of d as d = c * y.

void solve(){

    int n;
    cin >> n;

    vector<int> arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        int y = arr[i];
        if(arr[i] >= n)
            continue;
        
        int lim = min(n / y, y);
        for(int c = 1; c <= lim; c++){
            int d = c * y;
            if(i + d < n && arr[i + d] * y == d)
                ans++;
            if(i - d >= 0 && arr[i - d] * y == d && arr[i - d] != y)
                ans++;
        }
    }

    cout << ans << endl;

}

I'm afraid not even the problem writers know what is going on on C2 — Interactive Graph. Evidence of this is the fact that, on their solution, they compute the longest common prefix of the vectors $$$prev$$$ and $$$cur$$$, but that is not needed because the longest common prefix always has length $$$cur.size()-1$$$. Also, they talk about "connected components" on the editorial, which doesn't help much, because the exercise doesn't have connected components.

My take on their solution is the following:

The sequence of paths in lexicographical order simulates a lexicographical DFS traversal of the DAG. Indeed, when you do a query $$$k$$$, the interactor returns the call stack at the moment $$$k$$$.

With this, we sketch the general idea: we will do a DFS over the DAG, but we will try to avoid visiting a vertex twice (this way we get linear complexity).

Let's do queries from $$$k = 2$$$, then $$$k+1$$$, $$$k+2$$$, and so on, until we visit a vertex for the second time. During that process, let's also keep at what $$$k$$$ a vertex first appeared, and at what $$$k$$$ it left the stack. To do that, we only need the current DFS stack $$$p$$$ and the previous one $$$prev$$$. Notice that the longest common prefix of those stacks is always $$$p.size()-1$$$, because $$$p$$$ was made by removing elements from the back of $$$prev$$$ and then appending a new element.

Whenever we visit a vertex $$$u$$$ for the second time, we already know how many paths start from it: that amount is $$$timeOut[u] - timeIn[u]$$$. So, instead of querying at $$$k+1$$$ now (which will visit those paths), let's go to $$$k + timeOut[u] - timeIn[u]$$$ instead. This will skip exactly all the paths that start on $$$u$$$, and this will effectively make our DFS go to the vertex after $$$u$$$ in DFS order.

This algorithm does exactly the walk a DFS (without vertex repetition) would do, and therefore, the edges of the graph will be the ones made by the 2 last vertices of $$$p$$$ (check code for more details).

Submission

FOR THOSE WHO COME AFTER...

The editorial is not linked to the round

Can someone read my solution for Div2/E1 (Interactive Graph — Simple version) and please explain how the number of queries made by my solution never exceeds 32*(n+m)?

I am unable to mathematically prove my solution's optimality as it tends to get quite rigorous at least for me. I am not even sure if my solution is optimal and whether if it might get hacked by some test case even if it gets accepted for now.

Intuition for my solution: I begin with a linear iteration where I start with the first path (i = 1). You can make an observation that while doing so, if a particular vertex appear at the same position in a series of consecutive paths and then it changes its position or does not appear in the next path at all, that means the entire sub-tree from that vertex has already been encountered and we can store the edges involved in that sub-tree since we iterate through all the paths from that vertex for the first time. Then, we also store the number of paths that originate from that vertex in count array (in my solution) because if that vertex appears for another time, we can directly skip to the path i = i+count[vertex] since we have already encountered the entire sub-tree from that vertex so there is no new edge to be stored.

Please go through my solution to understand what I am talking about.

Submission: 364466471

Some additional notes on the editorial solution for 1D (below $$$k$$$-pair denotes a pair which costs $$$k$$$ to make correct):

1. The fact that we want to maximize $$$0$$$-pairs is not immediately obvious because whether a $$$2$$$-pair is necessary depends on the $$$0$$$-pairs that we select. For instance, for the string $$$())(()$$$, we could either form the pairs $$$[(), )(, ()]$$$ for a cost of $$$0 + 2 + 0$$$ or the pairs $$$[(), )), ((]$$$ for a cost of $$$0 + 1 + 1$$$. However, we can make the following exchange argument: consider two matchable brackets $$$($$$ and $$$)$$$ such that both are in either $$$1$$$-pairs or $$$2$$$-pairs. We claim that it cannot be worse to pair these brackets together into a $$$0$$$-pair, and pair their previous brackets together into a new pair. This is clearly true because the original cost is at least $$$1 + 1$$$, while the new cost is at most $$$0 + 2$$$. From this, we get that indeed, we should select an LPS for both strings. Alternatively you could derive this from the fact that there exists at most 1 2-pair, but this approach feels more intuitive and generalizable to me.
2. Nonetheless, it's still not obvious which LPS to pick. Here, we can make yet another exchange argument. Let a matched bracket be any bracket in a 0-pair, and an unmatched bracket be any other bracket. Then, we claim that if there exists an unmatched $$$)$$$ between any $$$0$$$-pair, it's not worse to put this $$$)$$$ into the $$$0$$$-pair instead. For instance, if we have the string $$$()()$$$ and the pairs $$$()$$$ and $$$)($$$, it's definitely not worse to swap the pairs to $$$()$$$ and $$$()$$$. From this observation (and a symmetric one for left brackets), the LPS is uniquely determined.