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