Please read the new rule regarding the restriction on the use of AI tools. ×

PurpleCrayon's blog

By PurpleCrayon, history, 3 years ago, In English

1541A - Pretty Permutations

Author: PurpleCrayon

Hint
Hint
Hint
Solution

1541B - Pleasant Pairs

Author: PurpleCrayon

Hint
Hint
Solution

1540A - Great Graphs

Author: PurpleCrayon

Hint
Hint
Hint
Solution

1540B - Tree Array

Author: ijxjdjd

Hint
Hint
Hint
Solution

1540C2 - Converging Array (Hard Version)

Author: ijxjdjd

Hint
Hint
Hint
Hint
Solution

1540D - Inverse Inversions

Author: PurpleCrayon

Hint
Hint
Hint
Solution

1540E - Tasty Dishes

Author: ijxjdjd

Hint
Hint
Hint
Hint
Solution
  • Vote: I like it
  • +96
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it -66 Vote: I do not like it

PURPLECRAYON ORZ

»
3 years ago, # |
  Vote: I like it -83 Vote: I do not like it

Damn, so orz round. PurpleCrayon orz

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I am curious, how many div2 testers solved D?

»
3 years ago, # |
Rev. 4   Vote: I like it +121 Vote: I do not like it

Alternate solution to 1540D - Инвертируем инверсии

(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.

»
3 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

speedforces.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    My solution is $$$O(K N^3 + QN)$$$. I just precomputed the coefficient of each $$$a_i$$$ for each prefix-range for each number of days since person $$$i$$$ becomes positive (only $$$1000$$$ possible days) in $$$O(N \cdot K \cdot N^2)$$$, and then summed up the appropriate ones to answer each query in $$$O(N)$$$. It's written in the offline style to use only $$$O(KN)$$$ memory at a time (grouped by $$$a_i$$$) instead of $$$O(KN^2)$$$.

    My passing submission is just $$$KN^3 / 6$$$ instead of the $$$KN^3$$$ I submitted in contest :'(

    If you guys wanted to prevent this, $$$K$$$ could've been much higher, like $$$1e18$$$.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      :( I knew of this solution (it’s why ML is tight) but I didn’t realize that it could be done offline with small memory. Of course $$$K$$$ higher is obvious solution but main issue is that the extra modulos from binary exponentiation make it very hard to pass in Java without allowing other unoptimal solutions through such as precomputing inverses of the matrix. Probably $$$k=10^5$$$ would’ve been a better choice. Thanks.

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But that's exactly what I did, and the final answer is the sum of the array — sum of all subarrays. 120611950

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      No, that's not what you did. To compute the answer via the method described above, you would have to compute how many elements are lesser than the current element at any given iteration and add them and also keep and their count using a Fenwick tree/ BIT. That's the incorrect approach though because sorting would be more optimal.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry if I misunderstood things. mangat_angad only mentioned adding negative weighed edges to the 1->2->3->...N graph, which is what I thought to arrive at my solution. The array I mentioned is indeed sorted and formed by distance differences which are the weights in the 1->2->3->...N graph. Unfortunately I'm still too noob to understand the tree structures you mentioned.

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Here's what it's trying to say:

    Suppose we start by marking the root. To mark a or b, we must first mark the lca, so we may assume that the lca has just been marked.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And what does this line mean? "The problem can be rephrased as having two stacks of size dist(l,a) and dist(l,b) with an arbitrary p to remove a node from one of the two stack (and 1−2p to nothing) and finding the probability that dist(l,b) reaches zero before dist(l,a)."

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Once you've reached the lca $$$l$$$, in a single step you either step closer to $$$a$$$, step closer to $$$b$$$, or step closer to neither.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you add implementation for this problem please?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, we mark lca first (of course). But why wouldn't it affect the final probability of reaching b before a? I mean, why is it sufficient to calculate the probability after marking lca?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        Before marking the lca, there is no way to make more progress towards $$$b$$$ than $$$a$$$ or vice versa. The subset of marked vertices also does not change the probability of moving towards $$$a$$$ or $$$b$$$ after reaching the lca because we're choosing uniformly at random and exactly two vertices are of interest.

»
3 years ago, # |
Rev. 3   Vote: I like it +30 Vote: I do not like it

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

How to calculate P_i
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution in a little bit more detail? :')

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +12 Vote: I do not like it

      Oof, I can give you an image, that shows how the distances from the two DFS are distributed on an example. You can see Nodes $$$A$$$ and $$$B$$$ and the numbers are the distances we write into the nodes.

      If you have specific questions about some steps go ahead and ask.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what does the dp states mean in your helper program? I am unable to understand. Can you please explain?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You have Nodes $$$1$$$ through $$$N$$$, neighbouring IDs are connected. The state $$$dp[l][r]$$$ is the probability, that node $$$N$$$ will be reached before node $$$1$$$ with all the nodes $$$l$$$ through $$$r$$$ marked already. Obviously $$$dp[1][x]=0$$$ and $$$dp[x][N]=1$$$ ($$$dp[1][N]$$$ can't happen). The recurrence is $$$dp[l][r]=(dp[l-1][r]+dp[l][r+1])/2$$$

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    same :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Step 1. use linearity of expectation. The answer is

    $$$\sum_{a<b} P(b\text{ appears before }a). $$$

    Step 2: Observe that if we start by marking a vertex $$$c$$$ on the path between $$$a$$$ and $$$b$$$, and suppose the next marked vertex on the path is $$$d$$$. Then, the probability that $$$d$$$ is between $$$c$$$ and $$$a$$$ and the probability that $$$d$$$ is between $$$c$$$ and $$$b$$$ are both $$$1/2$$$. This is because there are only two choices for $$$d$$$ and we're choosing uniformly at random. This means that the answer only depends on $$$\text{dist}(c,a)$$$ and $$$\text{dist}(c,b)$$$.

    Step 3: run a dp to calculate the probability that we mark $$$b$$$ before $$$a$$$ given $$$\text{dist}(c,a)$$$ and $$$\text{dist}(c,b)$$$.

»
3 years ago, # |
Rev. 2   Vote: I like it -72 Vote: I do not like it

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! */

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -35 Vote: I do not like it

    .

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Not studied yet, I'm still a beginner, but planning to start soon. Thanks for the guidance.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      once upon a time, I also did problems while not know what vectors are. sad times :'(

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      There's no issue in not knowing vectors. Yes they are important I agree but not knowing vectors should not be discouraged. I became expert here without knowing anything about vectors plus he is a beginner so he shouldn't be discouraged like this.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        +1, I agree with you. Same I was expert last year solely using arrays

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -28 Vote: I do not like it

          Bas kar bsdk kitna jhooth bolega

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Yash.Amin Could you please refrain from using foul language on educational discussions. Thanks

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Ah my bad, I did not want to come across as being arrogant, but I was genuinely confused that some people did not know vectors although they are using C++.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add implementations too.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Simply running two loops and checking every case would give a TLE. So, we might want to minimize the number of operations. For this, we would only consider the cases where the sum of indices is a multiple of an element.

    For this, we would first create two loops, one within the other, first loop iterating i from 0 to (n — 1) with an incrementation of 1. By observation, we can see that the first index for which the sum of indices will be a multiple of arr[i] is (arr[i] — 2 — i).

    So, in the nested loop we will run j = (arr[i] — 2 — i) till (n — 1) with an incrementation of arr[i]. We would ignore the cases where j < 0 or j >= n.

    Finally, we need to check for how many cases this holds (arr[i] * arr[j] = i + j + 2 and j > i).

    Suggestions are welcomed!

»
3 years ago, # |
  Vote: I like it -64 Vote: I do not like it

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!

*/

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Use spoilers for writing codes, please!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Actually, this is my first comment. Don't know much of this stuff as of now, but I'll surely take care of it the very next time.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    NICE CODESTYLE!!!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is &mdash?

    Just curious to know as haven't seen it before.

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems. thanks for almost fast editorial.

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Deleted :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I don't really understand the need for a recursive function for the stack emptying probabilities in 1540B - Древесный массив. 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If $$$m=2$$$ and $$$n=1$$$, your approach gives $$$\frac{1}{3}$$$. The correct answer should be $$$\frac{1}{4}$$$.

    P/S: I'm also curious if there is any combinatoric approach for this,ijxjdjd

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I would guess that there’s no easy closed form. You can evaluate in $$$O(n)$$$ however by counting right up paths from $$$(a,0)$$$ to $$$(x,y)$$$ for all $$$a$$$ and multiplying by $$$2^{-steps}$$$.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    The problem with this is that all the possibilities are not equilikely, consider $$$m=2, n=1$$$ and let $$$1$$$ denote entries from the stack of size $$$n$$$. Then the probability of obtaining $$$100$$$ is $$$1/2$$$, while obtaining $$$010$$$ and $$$001$$$ has a probability of $$$1/4$$$. Your approach assumes a uniform prior probability (in which case the answer is indeed $$$1/3$$$ whereas here it is $$$1/4$$$ which is the probability of getting $$$001$$$)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I like to think about C this way: The cheapest node is the root, and the most expensive node, X, is the one with the highest value, D. Therefore no matter how we make our edges, we need at least 1 path from node to X with distance D. So let's build 1 single edge of positive weight from 1 to X with weight D.

    Now from node X, all other nodes are <= D. We can use negative edges to go there. Now the problem just becomes "assign as many negative edges as possible" to the rest of the nodes.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 1540B - Древесный массив 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That is correct, but to see how it stays the same you can think of it inductively. Use strong induction and assume probability is the same no matter what the state of the tree is. Then from $$$(x,y)$$$ you always have an equal probability of ending up in one of the two states you can transition to because $$$p$$$ is always the same. Every scenario you enter one state, there’s another scenario with the same probability that enters the other state. So, the probability of entering one of the two states is the same as the other, thus $$$0.5$$$. Hopefully that makes things more clear.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh thanks, it's clear now. So, base of induction is when only l reached, and we can show that probability to make step towards a and b is same because for each individual set you can go from l to b instead of going from l into a, using exactly same steps in between (those steps which doesn't change distances to a and b). And similar holds for next steps.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 5   Vote: I like it -8 Vote: I do not like it

        Can you explain this?

        Assume $$$X$$$ is initially node we chose. Then define a function $$$g$$$ :

        $$$g[a][b][STATE]$$$ = probability to reach a before b while state of the tree we reach is $$$STATE$$$, and $$$a$$$, $$$b$$$ is length of path.

        follow the image, I can see : $$$g[a][b][STATE_x] = \frac{1}{4} (g[a][b][STATE_d] + g[a][b][STATE_e] + g[a — 1][b][closer_a] + g[a][b — 1][closer_b])$$$

        It can easy see that the probability can change. Or I wrong in some where?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I'll hide my long explanation under spoiler

          horrible wall of text
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, sorry, there is one missing part. We proved $$$P(reached(\alpha+1,\beta))=P(reached(\alpha,\beta+1))$$$ given $$$(\alpha,\beta)$$$ is reached, but this is actually what we need. This given condition is what I missed. Without given we could reach $$$(\alpha+1,\beta)$$$ from reaching $$$(\alpha+1,\beta-1)$$$.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 5   Vote: I like it 0 Vote: I do not like it

              Thanks for amz explain. I realize that I had some missunderstand in the way we calc $$$P(reach\ A\ before\ B)$$$

              This's exactly what in my mind one day ago: let $$$s = ...a...b...$$$ where $$$a$$$ and $$$b$$$ is node $$$a$$$ and node $$$b$$$, "$$$...$$$" mean some node between them which we chose them in exactly that order, or in other word, $$$s$$$ is state represent what we chose (exact in this order) I think $$$P(reach\ A\ before\ B)$$$ (or $$$P(A<B)$$$) must be calculate in this way :

              $$$P(A<B) = \sum_{\substack{all\ s\ which\ a<b}} P(s)$$$

              But unfortunately, it's wrong (may be, or I still missunderstanding)

              $$$P(A) = \sum_{\substack{all\ B[i]\ \subseteq\ A}} P(B[i])$$$ if and only if all $$$B[i]$$$ are distinct

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                $$$P(A < B)$$$ in your terms is exactly what we need (if a = A and b = B).

                I don't understand last formula, everything else looks fine.

                And to find $$$P(A < B)$$$ we use fact above and calculate all possible ways to reach $$$a$$$ earlier than $$$b$$$ we use $$$(\alpha, \beta)$$$ states using my notation: you either get $$$\alpha$$$ equal to dist to $$$a$$$ when $$$\beta$$$ = 0, or $$$\beta$$$ = 1, or 2, or 3...

                $$$ P(A < B) = \\ =\sum\limits_{i=0}^{dist(b,l)}P(reach(dist(a,l),i)\;given\; reached(dist(a,l)-1,i)) \\ = \sum\limits_{i=0}^{dist(b,l)}P(reached(dist(a,l)-1,i))\cdot \frac{1}{2} $$$

                Or you can rephrase task into other task with two kind of balls. What probability to remove all balls of one kind earlier than other, if you pick one or other kind of ball with probability 1/2.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 D, O(N^4) solution 120623566

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your code really helps me a lot in debugging,thanks.

    By the way,it's weired that I get Wrong6 when I try to optimize to O(N^3*logN) by binary search on tree.

    I have tested my function on other online judge and my function seems to be correct.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Bro you did not included the condition that i and j should be different i.e (i != j) because it is given in question that no are distinct

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think its covered as I started j from i+1. I tried that explicitly too but it didn't work. I wrote the same idea in a different way and it worked but this kind of implementation is not working.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        yeah, you are right, I run your code using vector instead of creating memeset it worked fine, i guess there is some problem in that. 120633207

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Only fault in your code is that you didn't used memset correctly

    I just changed your memset with this " memset(ind, 0, sizeof(ind)) " and it worked perfectly fine

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot to both of you. I shouldn't have used it without properly knowing about it.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Bro can u explain this soln????? i thought of taking all pairs that give negative edges except for the adjacent pairs.... bt getting wrong ans in 3rd 4th test case.....

    while(n>2) { sum-=(n-2)*(llabs(a[j]-a[i])); n--; // n = size i++; // i = 0 j--; // j = n-1 } cout<<sum<<endl;

    mysoln

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      My solution is simple. First sort the array.

      Then start connecting adjacent values with their differences. This way sum of all edges with positive weight will be same as the sum of adjacent differences in the array.

      After that start making negative edges for every i. So each i will have i negative edges. Where negative weight is same as -(arr[i] — arr[j]).

      Instead of search it for every j I have formula as (prefixsum till i) — arr[i]*i

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you tell me why are we sorting the array for a particular node call it x we need to add a negative weight from x to 1 , x to 2 x to 3 till x to x-1 keeping in mind the the path sum doesn't become negative so why are we sorting the array

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          We are sorting values only once so as to connect neighboring nodes with minimum values,i.e. difference b/w consecutive values.
          From this sum of positive edges will be minimum.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ohhh thanks I got it

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            My solution is working now I only needed to sort the array my code would have been accepted during the contest :(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain div2 B plz

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Beautiful Problems. Amazing Round!!!!

»
3 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

UPD: It's wrong.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hello! The answer would be -18.

    Diagram:

    Notice that once you sort the distances, the adjacent nodes have no effect on your final answer. But you can add negative edges as long as they are not adjacent, resulting in such a diagram. Hence you can use prefix sums to solve the problem. (if x nodes came before this, for each node, the answer to add is (x-1)*curr value — csum of first (x-1) nodes).

    Hope that made sense!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you Zemrith for so much detail explanation and the solution too it helped me a lot.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    first sort the array they will from non negative weight edges. 0 -> 1 -> 2 -> 2 -> 3 -> 3 so the non negative weights will be 1 | 1 | 0 | 1 | 0. form here greedily build most negative weights(backward edges) such that there are no negative cycles.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First you can sort D and get: N = 6, D = [0, 1, 2, 2, 3, 3]

    Now calculate the diffs:

    diffs = [1, 1, 0, 1, 0]

    The edges for this graph could be something like this:

       1     1     0     1     0      <- forward edges
    1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6
      -1    -1     0    -1     0      <- backward edges
    
    

    Now you have to add more negatives edges, and you could do this by choosing some i and j, i < j and add an edges from j to i, and the weight will be sum of the values from diff[i] to diff[j].

    Another way to think about this is: look at D array, it represents distances between adjacent nodes, all we have to do is add all of the edges with length 2, then all of the edges of length 3, ..., all of the edges of length N - 1.

    So, for our case we would have these edges

    a b   W
    -------
    1 2 - 1 
    2 3 - 1 
    3 4 - 0    <- adjacent forward edges
    4 5 - 1
    5 6 - 0
    
    2 1 - -1 
    3 2 - -1 
    4 3 - 0    <- adjacent backward edges
    5 4 - -1
    6 5 - 0
    
    3 1 - -2 
    4 2 - -1   
    5 3 - -1    <- edges of length 2
    6 4 - -1
    
    4 1 - -2 
    5 2 - -2   <- edges of length 3
    6 3 - -1    
    
    5 1 - -3 
    6 2 - -2   <- edges of length 4
    
    6 1 - -3   <- edges of length 5
    
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You ilidar for clearing my doubt and for detailed explaination.

»
3 years ago, # |
Rev. 7   Vote: I like it +18 Vote: I do not like it

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:

Tree-Array-Rep

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})$$$

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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), with having arbitary probability $$$0 < p \leq 0.5$$$ of chosing to pick the top of each stack (and $$$1-2p$$$ for doing nothing). Then

    $$$dp_{i,j}=\int_{0}^{0.5} x \cdot (dp_{i-1,j}+dp_{i,j-1}) + (1-2x) \cdot dp_{i,j} \,dx$$$

    Solving the equation, we get $$$dp_{i,j}=\frac{1}{6} \cdot (dp_{i-1,j}+dp_{i,j-1})$$$ What is the mistake in this logic?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      The biggest issue with this logic is that it's assuming $$$p$$$ is arbitrary chosen from a certain state. While $$$p$$$ can be anything in the world, it is always an exact number from a certain state, hence why an integral is wrong.

      As a different type of intuition, you can think, "is it more likely to reach $$$(i-1, j)$$$ than state $$$(i, j-1)$$$"? and vice versa. For me at least, I don't see how it's possible for either of those questions to be true, so they should be equal.

      If you're looking for a more rigorously correct $$$dp$$$, it would look something like this.

      Proof
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

`](https://mirror.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;
        
    }
     
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    v[i].first * v[j].first can create overflow. So, you need to convert them to long long by using

    ll left = 1LL * v[i].first * v[j].first;

    instead and it would pass.

    (Simply save the value in long long won't help. You need to convert them to long long before doing multiplication. 1LL* is one way)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    x and y is the distance left for each side right? So, if you take one out, it won't make sense to add that one to the other side since the distance should be either x-1 and y or x and y-1.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much I understand. I had a minor misunderstanding of the parameters to the dp state.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

code forces round 728 div2
Problem B :https://mirror.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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If i am using #define node pair<int,int> it is getting accepted but when i am using typedef pair<int,int> node; it is giving wrong answer

    Why this is happening ?? Is it a bug??

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Not really sure why this is happening.

      However, I think the problem is the position of #define int long long. So, for #define pair<int,int> node it seems that compiler change node -> pair<int,int> -> pair<long long, long long>. However, when you do typedef, it still keeps in pair<int, int> which creates an overflow problem later on.

      I did try moving #define int long long up above typedef and the code pass. So, my best guess is #define int long long only replace int after that position with long long. Thus, node is still pair<int, int> in the typedef solution, while node is changed to pair<long long, long long> in the second solution.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Check the definition of bi again dude. bi here means number of elements greater than pi. So to get ci, which is number of elements smaller than pi, you need i-bi.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I read it again. If I read it correctly, bi stands for j<i,pj>pi, and ci stands for j>i,pj<pi. For example, p={1,3,5,4,6,2}, I think b4=1,c4=1, please point out my problem

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        oh, the array index starts from 1

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You are right.

        I guess it might just be typo and ci stands for j<i, pj<pi. At least with this definition of ci the algorithm seems correct :)

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    There are a couple ways you could do it:

    1. Just use standard binary lifting (initialize once for each root). This runs in $$$\mathcal{O}(n^3 \log{}n)$$$, and should pass under the given constraints. You could also just use $$$\mathcal{O}(1)$$$ lca using an rmq over an euler tour.
    2. You could use a version of dp, where $$$dp[a][b] = lca(a, b)$$$. If the depth of $$$a$$$ is greater than the depth of $$$b$$$, $$$dp[a][b] = dp[parent[a]][b]$$$, otherwise $$$dp[a][b] = dp[a][parent[b]]$$$. The base cases are $$$dp[a][a] = a$$$ for all $$$a$$$. This runs in $$$\mathcal{O}(n^3)$$$.
    3. You could extend this idea and do the main solution's dp directly on the tree (without ever worrying about lca's). The recurrence is equivalent to the main solution ($$$dp[a][b] = \frac{dp[parent[a]][b]+dp[a][parent[b]]}{2}$$$ with the base cases being one node is an ancestor of the other.
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Realy impressive solution. I'm surprised no stars were given to you until me. Maybe many people didn't get your idea since the solution is actually much more complicated than your brief comment(at least in my opinion). I also wrote a piece of code which used your method but simplified a small part of steps. Here it is.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The calculation is independent based on whichever node that you choose first (it becomes the “root”). Initially you choose one of $$$n$$$ nodes with equal probability so you divide by $$$n$$$ at the end after you’ve summed up the independent expected value after choosing the node $$$i$$$ initially.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't get one thing , like in A , we can reorder the cats just by rotating the array , it simply changes the location of each cat .