2003.md (5236B)
1 Source: https://codeforces.com/blog/entry/133168 2 3 [Full video](https://youtu.be/9RMg-xKznTw) 4 5 [2003A - Turtle and Good Strings](/contest/2003/problem/A "Codeforces Round 968 (Div. 2)") 6 7 **Hint 1** 8 9 Solve with $K=2$ only. 10 11 My submission — [278058173](/contest/2003/submission/278058173 "Submission 278058173 by aryanc403") 12 13 **Video Editorial** 14 15 [2003B - Turtle and Piggy Are Playing a Game 2](/contest/2003/problem/B "Codeforces Round 968 (Div. 2)") 16 17 **Hint 1** 18 19 Turtle wants to maximise the remaining value, so he should try to remove the smallest values. 20 Similarly Piggy wants to minimise the remaining value, so he should try to remove the largest values. 21 22 My submission — [278054761](/contest/2003/submission/278054761 "Submission 278054761 by aryanc403") 23 24 **Video Editorial** 25 26 [2003C - Turtle and Good Pairs](/contest/2003/problem/C "Codeforces Round 968 (Div. 2)") 27 28 **Hint 1** 29 30 Try to find bad pairs. 31 32 **Hint 2** 33 34 Some of the bad substring are. 35 - aaaabbbbb 36 - aabb 37 - ab 38 39 Some of the good substring are. 40 - ababababb 41 - abab 42 43 **Hint 3** 44 45 Intuitively, we should try to create a string which does not contain equal chars together. 46 47 My submission — [278156003](/contest/2003/submission/278156003 "Submission 278156003 by aryanc403") 48 49 **Video Editorial** 50 51 [2003D1 - Turtle and a MEX Problem (Easy Version)](/contest/2003/problem/D1 "Codeforces Round 968 (Div. 2)") 52 53 **Hint 1** 54 55 Lets pick an array $B_1,B_2,...,B_M$, and see what happens when we do operation of X, with this array. 56 Let $\text{sm1}$ be the smallest missing value in B, and $\text{sm2}$ be the second smallest missing value in B. 57 58 Now, if $X=sm1$, 59 $\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = $ 60 $\text{mex}(\text{sm1}, B_1, B_2, \ldots, B_M) = sm2$ 61 62 otherwise, 63 $\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = sm1$ 64 65 **Hint 2** 66 67 Now, we can model it as a graph problem, 68 Graph consists of $m+1$ nodes labelled with $0,1,...,m$ 69 From any node we can reach $\text{sm1}$, and from $\text{sm1}$ we can reach $\text{sm2}$. 70 71 Our goal is to find for each node, maximum labelled we can reach starting from it. 72 73 **Hint 3** 74 75 We cannot create a graph of size $m+1 = 10^9 + 1$. 76 Let $K=\max(sm2)$ ie $K$ is maximum value of second maximum among all arrays given in input. 77 78 Notice that maximum X, we can reach after doing any operations is $K$. 79 So for all $i \gt K$, we should not do any operations, and $F(i)=i$. 80 81 Now, we can directly, calculate sum of i more than $K$ and create a graph with $K+1$ nodes. 82 83 **Hint 4** 84 85 Next observation was, from $X$, we will go to smaller value only once. 86 87 My submission — [278155964](/contest/2003/submission/278155964 "Submission 278155964 by aryanc403") 88 89 **Video Editorial** 90 91 [2003D2 - Turtle and a MEX Problem (Hard Version)](/contest/2003/problem/D2 "Codeforces Round 968 (Div. 2)") 92 93 **Hint 1** 94 95 Refer hints of D1. 96 97 **Hint 2** 98 99 Because we cannot use same array twice, the only difference it makes it, 100 If from $X$ we go to $\text{sm1}$ of an array, we will not be able to go to $\text{sm2}$ with the same operation. 101 So we should reach $\text{sm1}$ using some other array, if it exists. 102 If such an array does not exists, we will not be able to reach $\text{sm2}$ using this operation. 103 104 My submission — [278157539](/contest/2003/submission/278157539 "Submission 278157539 by aryanc403") 105 106 **Video Editorial** 107 108 [2003E1 - Turtle and Inversions (Easy Version)](/contest/2003/problem/E1 "Codeforces Round 968 (Div. 2)") 109 110 **Hint 1** 111 112 First solve for case $L_1=1, R_M=N$ and $R_i + 1 = L_{i+1}$, ie every element is part of some range. 113 114 **Hint 2** 115 116 For each range lets fix $K_1,K_2,K_3,...,K_M$, and see how does an interesting permutation looks like. 117 118 **Hint 3** 119 120 Let $P_1=K_1-L_1+1$, $P_2=K_2-L_2+1$, and so on... 121 Similary let $S_1=R_1-K_1$, $S_2=R_2-K_2$, and so on... 122 123 Let $P = \sum P_i$ and $S = \sum S_i$. 124 Smallest $P$ elements should go to prefix of each range and largest $S$ elements should fo to suffix of each range. 125 126 **Hint 4** 127 128 In optimal permutation, we should place $1...P$ in descending order in prefixes, and we should place $P+1....P+S$ in descending order in suffixes. 129 130 **Hint 5** 131 132 Now, lets do a dp, $dp[i][pLen]$, 133 This denotes we have processed first $i$ ranges so far, smallest pLen elements went to prefix and remaining went to suffix. 134 135 Now, we can iterate on value of $P_{i+1}$ and try to count no of new inversions that will come up. 136 137 **Hint 6** 138 139 How to handle elements not present in any range? 140 We add them in a range of length 1, and take prefix of length 1 or suffix of length 1. 141 142 My submission — [278160207](/contest/2003/submission/278160207 "Submission 278160207 by aryanc403") 143 144 **Video Editorial** 145 146 [2003E2 - Turtle and Inversions (Hard Version)](/contest/2003/problem/E2 "Codeforces Round 968 (Div. 2)") 147 148 **Hint 1** 149 150 Refer to hints of E1. 151 152 **Hint 2** 153 154 Lets merge all intersecting ranges, and look at a group of ranges. 155 156 **Hint 3** 157 158 All ranges in this group will have same value of $K_i$. 159 This $K_i$ must be more than or equal to left endpoint of all ranges. 160 And this $K_i$ must be less than or equal to right endpoint of all ranges. 161 162 My submission — [278161293](/contest/2003/submission/278161293 "Submission 278161293 by aryanc403") 163 164 **Video Editorial** 165 166 **Chat QnA**