PURPLECRAYON ORZ

Damn, so orz round. PurpleCrayon orz

I am curious, how many div2 testers solved D?

Alternate solution to 1540D - Inverse Inversions

(Read the first nontrivial paragraph of the editorial before reading this alternate solution)

Let $$$p_r(k) = x$$$ denote that of the numbers $$$p(1), \ldots, p(r)$$$ in sorted order, $$$p(k)$$$ is equal to the $$$x$$$th of these numbers. We will take a decomposition strategy just as the editorial does, though our strategy will be different. We will divide $$$[1, n]$$$ into blocks of length $$$b$$$. For each block covering some interval $$$[l, r]$$$, we will store $$$p_r(k)$$$ for each $$$k \in [l, r]$$$ in sorted order.

This means that for any $$$k$$$, if we know $$$p_r(k)$$$ for some block $$$[l, r]$$$, then we can determine $$$p_{r'}(k)$$$ for the block $$$[l', r']$$$ immediately to the right by binary searching on the numbers stored for $$$[l', r']$$$. Therefore, we can perform queries in $$$O\left(\frac n b \lg b\right)$$$.

We now need to figure out updates. There are probably simple ways to perform updates in $$$O(b\lg b)$$$, but this yields an overall runtime of $$$O(q\sqrt n \lg n)$$$ which is too slow.

Therefore, we can instead store each block as a segment tree. For each range $$$[l, r]$$$ in the segment tree we store the same thing we store for the whole block: $$$p_r(k)$$$ for each $$$k \in [l, r]$$$ in sorted order.

We then have to quickly merge two intervals. We can merge two intervals of length $$$\lambda$$$ in $$$O(\lambda \lg \lambda)$$$ by doing binary search just as we did above, but this still only yields $$$O(b\lg b)$$$ update overall. However, these $$$\lambda$$$ binary searches can be optimized using two pointers to $$$O(\lambda)$$$, making the overall update $$$O(b)$$$.

We thus have $$$O\left(\frac n b \lg b\right)$$$ query and $$$O(b)$$$ update. Therefore, we can choose $$$b = \sqrt{n\lg n}$$$ to attain an overall runtime of $$$O\left(q\sqrt{n\lg n}\right)$$$ just as the editorial does.

Submission in Kotlin

Submission in C++

It is interesting to note that this solution is quite fast. At the time of writing this update, the C++ version is the fastest correct submission (and runs under 1 second!) and the Kotlin version is faster than the vast majority of submissions.

The 3rd hint for the second problem is same as that of the first problem, is it related or a mistake? UPD: it is corrected.

speedforces.

Problem B Detailed Explanation

c was too easy, d was too hard. but d was very nice problem though.

Paging ecnerwala to explain his solution to D1E if he'd like. It seems offline?

Does Div2 D deserved to be D Problem? According to me it should've been Div2 E.

I feel like such an idiot for not being able to understand problem C (Div2). For some reason I thought the nodes were connected like this — 1->2->3->....->N and that we had to minimise answer by adding other edges (of negative weight in case they dont give a negative cycle) to this graph.

Just want to apologize to authors for the stupidest question, I misread the task..

Can someone tell me the meaning of this line in problem Div2D/Div1B

Note that, until reaching, l every possible process still has the same probability of reaching b before a. Therefore, we can assume that the process has reached l and calculate the probability from there.

What same probability are they talking about?

So, my Solution for Div1 Problem B / Div2 Problem D / 1540B — Tree Array:

Chose two Nodes $$$A$$$ and $$$B$$$ with $$$A>B$$$.

First DFS: Find the path from $$$A$$$ to $$$B$$$. I call it $$$path_p$$$. On $$$path_p$$$ mark the distance to $$$B$$$ for each node.

Second DFS: For each remaining node $$$N$$$ find the shortest path to $$$path_p$$$. It will hit it at some node of the $$$path_p$$$ which has some distance $$$D$$$ marked on it. We mark $$$N$$$ with $$$D$$$. (See comment below for image.)

Calculation: For each node $$$N$$$ we can calculate $$$P_i$$$. $$$P_i$$$ is the probability to reach Node $$$B$$$ before we reach Node $$$A$$$. We sum $$$P_i$$$ for each node. $$$P_i$$$ is also the probability, that the pair of Nodes $$$A$$$ and $$$B$$$ with starting node $$$N$$$ will contribute to the inversion sum.

Iteration: We need to repeat this for each pair $$$A$$$ and $$$B$$$. In the end we divide the answer by $$$n$$$, the amount of nodes (the probability to start with Node $$$N$$$).

This algorithm is $$$O(N^3)$$$. See my Solution 120603369

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

int solve(int n)
{
    vector<vector<double>> dp(n,  vector<double>(n, 0));


    for(int i = 0; i < n; ++i)
    {
        dp[0][i] = 1;
        dp[i][n - 1] = 0;
    }
    dp[0][n - 1] = -1;
    for(int w = n; w >= 0; w--)
    {
        for(int i = 1; i + w < n - 1; i++)
        {
            int l = i;
            int r = w + i;
            dp[l][r] = 0.5 * (dp[l - 1][r] + dp[l][r + 1]);
        }
    }
    cout << n << "\n\n";
    for(int i = 0; i < n; i++)
    {
        cout << dp[i][i]*(1<<(n-2)) << "\n";

    }
    cout << "\n\n\n\n";
    return 0;
}

//======================
// Technical stuff
//======================

int main()
{
    int ntest = 12;
    for(int test = 2; test < ntest; ++test)
    {
        solve(test);
    }
    return 0;
}

I can't grasp the editorial of Div 2 D/ Div 1 B. Can somebody provide a more intuitive explanation?

include<bits/stdc++.h>

using namespace std;

int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; long long arr[n]; for(int i = 0; i < n; i++){ cin >> arr[i]; } long long cnt = 0; for(int i = 0; i < n — 1; i++){ for(int j = arr[i] — 2 — i; j < n; j += arr[i]){ if(j < 0 || j >= n) continue; else{ if((arr[i] * arr[j] == i + j + 2) && (j > i)) cnt++; } } } cout << cnt << "\n"; } return 0; }

/* Accepted code A different approach using arrays (as I don't know what vectors are, haven't read that) I hope this is a optimal approach. Any suggestions related to this are whole-heartedly welcomed. Also, please guide me how could I have optimized the code to a much extent. Thanks in advance! Keep programming! */

Please add implementations too.

include<bits/stdc++.h>

using namespace std;

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int t;

cin >> t;

while(t--){

int n;

cin >> n;

long long arr[n];

for(int i = 0; i < n; i++){

    cin >> arr[i];

}

long long cnt = 0;

for(int i = 0; i < n — 1; i++){

for(int j = arr[i] &mdash; 2 &mdash; i; j < n; j += arr[i]){

    if(j < 0 || j >= n) continue;

    else{

    if((arr[i] * arr[j] == i + j + 2) && (j > i)) cnt++;

    }

}

}

cout << cnt << "\n";

}

return 0;

}

/* Accepted code

A different approach using arrays (as I don't know what vectors are, haven't read that)

I hope this is a optimal approach.

Any suggestions related to this are whole-heartedly welcomed.

Also, please guide me how could I have optimized the code to a much extent.

Thanks in advance!

Keep programming!

*/

Div2 B can also be done in O(NsqrtN). We know that for a given pair of indeces i+j < 2n, so any pair that a[i] * a[j] < 2n will have to have one of the two terms be <= sqrt(n) (with some off by one errors of course). So the algorithm is to store an array of pairs [array value, index] and sort that array by the value. If the array value is <= sqrt(2n) we can naively loop over the rest of the array in O(n) time and check (be careful about overcount), and if the value is > sqrt(n), we can ignore it. This works since when a[i] * a[j] < 2n one of a[i] or a[j] has to be <= sqrt(2n) and as a result, every pair will be counted.

I don't understand in div1 C why it's prefix of b, in the case i=3 we have $$$a_1+a_2+a_3=f_1+f_1+b_1+f_1+b_1+b_2$$$ so $$$f_1=(ap_i-2b_1-b_2)$$$ I believe the general formula is something in the taste of $$$f_1=(ap_i-ibp_{i-1}+bpt_{i-1})/i$$$ where bpt_i=b_1+2b_2+...+ib_i, I think I miss something
Edit: corrected

Nice problems. thanks for almost fast editorial.

is there anyone who can't even solve one question of today's contest ..

Deleted :)

Please explain div2c/div1a problem a little bit more. Thank you.

I don't really understand the need for a recursive function for the stack emptying probabilities in 1540B - Tree Array. I mean given that you have a stack of size n and and m you can basically have an array of size n + m filled with 0s and 1s where 0 at the ith place means that the ith element was taken from the first stack. Any such array which has n 0s and m 1s correspond to one process and it's easy to see that whoever takes the last spot in the array gets emptied later which gives an easy way to calculate the probabilities. Namely $$$\binom{n + m - 1}{n - 1} / \binom{n + m}{n}$$$ for the first and similar to the other.

Problem Div2C/Div1A, Plz somebody explain 3rd hint. I didn't get why this condition must be true

The sum of the values of edges with positive weight must be ≥ the maximum value in the array.

In problem 1540B - Tree Array I agree with everything up to:

Once l is reached, we now note that the probability that the process "gets closer" to b is always equal to the probability of getting closer to a.

I agree with this quote if it was about each individual set of marked nodes and single step for them. Because for any individual set of marked nodes, those probabilities is just one over the number of options at the moment. But I don't understand why I should forget about everything else what happens with other parts of tree, because after single step which is neither towards a neither towards b, the number of options (nodes we can mark on next step) may change.

Div2 D, O(N^4) solution 120623566

Although Div.2 D is harder than ever, in my opinion, it's such a useful and excellent problem.

Is it usual for people to post solutions online during the contest like this channel? https://youtube.com/channel/UCIAiAwwbj9OLmbZehfc28OQ

Can anyone please explain why this submission 120562335 is failing for Div2 B? It would be a great help.

Instead of $$$a_i \cdot a_j \leq 2n$$$, we could also check $$$a_i \cdot a_j \leq i+n$$$ which is a bit faster ($$$ \sim 62ms$$$).

can anyone explain B. pleasant pairs more easy words??

For those who are searching for a simple solution for great Graphs problems in O (nlogn). https://codeforces.com/contest/1541/submission/120600816

can anyone explain div2 B plz

Beautiful Problems. Amazing Round!!!!

UPD: It's wrong.

For DIV 2C/1A can anyone explain with this test case N = 6 and D = 0 1 2 3 2 3. What are the edges that we can have with their weights?

Could someone please provide a more strict intuition or insight of Div2D/Div1B of why "the actual probability p does not matter"? The intuition in the editorial is still alien to me of why those choices of not progess toward to either stacks (and probability 'p' also changes from time to time too) doesn't matter.

Update: Here is the intuition I came up with (The strict proof can be found in the comment of the author below)

Let $$$dp_{i,j}$$$ = the probability of emptying the first stack (which now have $$$i$$$ things left) before the second stack (which now have $$$j$$$ things left) in some states of the current tree.

now, we will try break this $$$dp_{i,j}$$$ down into the sum of $$$dp_{i-1,j}$$$ and $$$dp_{i,j-1}$$$

We will try to illustrate this with trying to split and color, either red or blue, a stick of length $$$1$$$. The length of the sticks representing the 'probability', and the color of the sticks will represent $$$dp_{i-1,j}$$$(red) or $$$dp_{i,j-1}$$$(blue), depending on the color.

Suppose in the current state, we have probability $$$p$$$ for choosing to pop each stacks, and the rest $$$1-2p$$$ of doing nothing. The picture will look like this:

We will split the stick equally(*) into several sticks of length $$$p$$$, and then color two of them red and blue. (* We can split it evenly because in the original problem, $$$p$$$ is in the form $$$\frac{1}{number\ of\ candidate\ unmark\ nodes}$$$ ) Now, the remaining sticks represent the state of $$$dp_{i,j}$$$ again (in some other state of the entire tree, so might be in some different $$$p$$$). That means we will split those sticks similary.

The key observations is:

1) We know that, in the original problem, if we keep picking nodes that aren't progressing toward the target nodes, we will run out of nodes eventually and finally choose the two nodes. That means, all the sticks will eventually colored into 'red' and 'blue'.

2) When we split a stick into several smaller equal length sticks, we will color two of them into red and blue. Those two sticks always have the same length. That means, the total length of blue sticks and the total length of red sticks will be equal in the end.

Analogically, that means, eventually, $$$dp_{i,j}$$$ will split into $$$dp_{i-1,j}$$$ and $$$dp_{i,j-1}$$$ evenly, no matter $$$p$$$ might be or the state of tree of $$$dp_{i,j}$$$ might be. Therefore, $$$dp_{i,j} = \frac{1}{2} \cdot (dp_{i-1,j}+dp_{i,j-1})$$$

I am getting wrong ans . could someone tell me where the code make differene ( [yestrday competiton problem .

`](https://codeforces.com/contest/1541/problem/B).

int main( ) {
    clock_t begin = clock();
    file_i_o();
    // Write your code here....
    int t;
    cin>>t;
    while(t-- ){
        int n;
        cin>>n;
        vector<pair<int,int>>v;
        v.push_back({0,0});
        loop(i,0,n) {
            int x;
            cin>>x;
            v.pb({x,i+1});

        } 
        sort(v.begin()+1,v.end());
        int count =0;
        for(int i=1 ; i<=n;i++) {
            for(ll j=i+1;j<=n;j++) {
                ll left = v[i].first * v[j].first;
                ll right = v[i].second + v[j].second;

                if(left == right) count++;
                if(left > 2*n ) break;
            }
        }
        cout<<count<<endl;
        
    }
     

Hi, in problem Div1.B/Div2.D; I can't wrap my head around $$$F[x][y]=F[x−1][y]/2+F[x][y−1]/2$$$. Why is it not $$$F[x][y]=F[x−1][y+1]/2+F[x+1][y−1]/2$$$, can someone please explain to me why is my transition wrong and/or why is the aforementioned transition correct?

PLease explain why 2 same codes are not giving the same ans

code forces round 728 div2
Problem B :https://codeforces.com/contest/1541/problem/B

AC Submission : https://ide.codingblocks.com/s/579769

Wrong output Submission :https://ide.codingblocks.com/s/579771

Difference is using of macro (node) instead of pair<int,int>

Please help

May I ask why in the Div1D solution ci=i-bi, I think it should be ci=bi ...

Here's my solution of B div 1 / D div 2 without LCA, using single DFS per node. 120700765 It is similar to what OleschY suggested above. I've tried to describe it in the blog

Can someone explain how you can find the LCA for each pair so quick? Iterating through every root is and then considering every pair is already N^3

O(n2) is also working for div2 C Great Graphs. https://codeforces.com/contest/1540/submission/120964787

Div1D can be done in $$$O(n \sqrt{n})$$$. We can use square root decomposition to replace all BITs in tutorial. Since a value in a non-updated position changes by at most one and all values change in the same direction, the full recomputation is only needed in the updated position and we can perform an incremental change in $$$O(1)$$$ for values in each non-updated positions.

Code

ijxjdjd in problem Tree array you said that Fixing a given root r, the expected value of the entire process is obviously the sum of the expected values for a fixed root divided by n.

why we divide by n at the end ?