codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1540.md (3484B)


      1 Source: https://codeforces.com/blog/entry/92199
      2 
      3 [1541A - Pretty Permutations](/contest/1541/problem/A "Codeforces Round 728 (Div. 2)")
      4 
      5 Author: [PurpleCrayon](/profile/PurpleCrayon "Master PurpleCrayon")
      6 
      7 **Hint**
      8 
      9 The parity (whether $n$ is odd or even) matters.
     10 
     11 **Hint**
     12 
     13 Swapping two adjacent cats keeps both of them close to their original location and changes both of their locations.
     14 
     15 **Hint**
     16 
     17 If $n$ is even, the optimal distance is $n$, and if $n$ is odd the optimal distance is $n+1$.
     18 
     19 **Solution**
     20 
     21 Tutorial is loading...
     22 
     23 [1541B - Pleasant Pairs](/contest/1541/problem/B "Codeforces Round 728 (Div. 2)")
     24 
     25 Author: [PurpleCrayon](/profile/PurpleCrayon "Master PurpleCrayon")
     26 
     27 **Hint**
     28 
     29 $i+j \leq 2 \cdot n$
     30 
     31 **Hint**
     32 
     33 The number of pairs $(a, b)$ such that $a \cdot b \leq x$ is $O(x log x)$.
     34 
     35 **Solution**
     36 
     37 Tutorial is loading...
     38 
     39 [1540A - Great Graphs](/contest/1540/problem/A "Codeforces Round 728 (Div. 1)")
     40 
     41 Author: [PurpleCrayon](/profile/PurpleCrayon "Master PurpleCrayon")
     42 
     43 **Hint**
     44 
     45 What's the minimum value that an edge from $a$ to $b$ can be?
     46 
     47 **Hint**
     48 
     49 Use edges with negative value whenever you can.
     50 
     51 **Hint**
     52 
     53 The sum of the values of edges with positive weight must be $\geq$ the maximum value in the array.
     54 
     55 **Solution**
     56 
     57 Tutorial is loading...
     58 
     59 [1540B - Tree Array](/contest/1540/problem/B "Codeforces Round 728 (Div. 1)")
     60 
     61 Author: [ijxjdjd](/profile/ijxjdjd "Master ijxjdjd")
     62 
     63 **Hint**
     64 
     65 Fix the initial node chosen and root the tree there, what is the contribution of each pair of nodes?
     66 
     67 **Hint**
     68 
     69 Nothing matters besides the path from node $a$ to node $b$, and the initially chosen node $r$.
     70 
     71 **Hint**
     72 
     73 You are given two stacks of size $a_1$ and $a_2$. In a single step, you randomly choose a stack to remove a single item from. What is the probability that $a_1$ becomes $0$ before $a_2$? Can you extend this argument for an arbitrary probability $p$ to remove from one of the two stacks, and a probability of $1-2p$ to do nothing?
     74 
     75 **Solution**
     76 
     77 Tutorial is loading...
     78 
     79 [1540C2 - Converging Array (Hard Version)](/contest/1540/problem/C2 "Codeforces Round 728 (Div. 1)")
     80 
     81 Author: [ijxjdjd](/profile/ijxjdjd "Master ijxjdjd")
     82 
     83 **Hint**
     84 
     85 What are the invariants? The monovariants?
     86 
     87 **Hint**
     88 
     89 What is the prefix sum array of the converged array? What is the difference array of the converged array?
     90 
     91 **Hint**
     92 
     93 What if you conducted the process on a prefix of size $1$, then of size $2$, and on and on?
     94 
     95 **Hint**
     96 
     97 How many values $x$ are actually interesting?
     98 
     99 **Solution**
    100 
    101 Tutorial is loading...
    102 
    103 [1540D - Inverse Inversions](/contest/1540/problem/D "Codeforces Round 728 (Div. 1)")
    104 
    105 Author: [PurpleCrayon](/profile/PurpleCrayon "Master PurpleCrayon")
    106 
    107 **Hint**
    108 
    109 The answer is always unique.
    110 
    111 **Hint**
    112 
    113 Try to figure out what the location of the $i$-th element would be if you only looked at the first $i$ elements, then the first $i+1$, etc. to find an $O(nq)$ solution.
    114 
    115 **Hint**
    116 
    117 Use sqrt decomposition to optimize it.
    118 
    119 **Solution**
    120 
    121 Tutorial is loading...
    122 
    123 [1540E - Tasty Dishes](/contest/1540/problem/E "Codeforces Round 728 (Div. 1)")
    124 
    125 Author: [ijxjdjd](/profile/ijxjdjd "Master ijxjdjd")
    126 
    127 **Hint**
    128 
    129 How much does each chef's initial dish contribute at time $k$?
    130 
    131 **Hint**
    132 
    133 What if you really, really wanted to use matrix exponentiation?
    134 
    135 **Hint**
    136 
    137 How can you multiply some vectors by a matrix in $O(N)$ time? (go back to linear algebra class)
    138 
    139 **Hint**
    140 
    141 Decompose into linear combinations of eigenvectors.
    142 
    143 **Solution**
    144 
    145 Tutorial is loading...