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 \gt 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.me/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?