codeforces-scrape

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

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