2005.md (4844B)
1 Source: https://codeforces.com/blog/entry/133966 2 3 Checkout [Codeforces Month of Blog Posts Pt. II (Win $500+!)](https://codeforces.com/blog/entry/133806) 4 5 [Full video](https://youtu.be/-62rIr88JLU) 6 7 [2005A - Simple Palindrome](/contest/2005/problem/A "Codeforces Round 972 (Div. 2)") 8 9 **Hint 1** 10 11 Lets fix the count of aeiou $C_a,C_e,C_i,C_o,C_u$ 12 What is the minimum number of subsequence palindromes? 13 14 **Hint 2** 15 16 No of palindromes that consist of only a is $2^{C_a}-1$ and similarly for eiou. 17 So lowerbound on no of palindrome is $2^{C_a}+2^{C_e}+2^{C_i}+2^{C_o}+2^{C_u}-5$ 18 Does there exists a permutation where this lowerbound is achievable? 19 20 **Hint 3** 21 22 This lowerbound is achieved on strings of form aaaaaaaaaeeeeeeeeeeiiiiiiiiiioooooooooouuuuuuuuu 23 24 **Hint 4** 25 26 How to find optimal values of $C_a,C_e,C_i,C_o,C_u$? 27 28 **Hint 5** 29 30 In optimal answer $|C_x-C_y| \le 1$. 31 You can try to prove it using [exchange arguments technique](https://codeforces.com/blog/entry/63533). 32 33 My submission — [281138271](/contest/2005/submission/281138271 "Submission 281138271 by aryanc403") 34 35 **Video Editorial** 36 37 [2005B1 - The Strict Teacher (Easy Version)](/contest/2005/problem/B1 "Codeforces Round 972 (Div. 2)") 38 39 **Hint** 40 41 Separately solve for cases when David is on left side of both the teachers, in between the teachers and right side of both the teachers. 42 43 My submission — [281147180](/contest/2005/submission/281147180 "Submission 281147180 by aryanc403") 44 45 **Video Editorial** 46 47 [2005B2 - The Strict Teacher (Hard Version)](/contest/2005/problem/B2 "Codeforces Round 972 (Div. 2)") 48 49 **Hint 1** 50 51 We need the nearest teacher on the left side and right side, and then B1 solution works. 52 53 **Hint 2** 54 55 To find the nearest teachers, you can either use [binary search](https://usaco.guide/silver/binary-search) or use [lower_bound stl](https://avadhootk.medium.com/lower-bound-in-c-stl-a048eebd5876) function. 56 57 My submission — [281146462](/contest/2005/submission/281146462 "Submission 281146462 by aryanc403") 58 59 **Video Editorial** 60 61 [2005C - Lazy Narek](/contest/2005/problem/C "Codeforces Round 972 (Div. 2)") 62 63 **Hint 1** 64 65 Let's first simplify the scoring function. 66 67 **Hint 2** 68 69 Let's say we have fixed string $t$, you do we find the score? 70 Let the no of narek strings formed is $c$ and total no of chars narek is $t$. 71 No of chars found by chatgpt will be $t-5*c$. 72 The score is $5*c-(t-5*c) = 10*c-t$. 73 74 **Hint 3** 75 76 Another way to see this cost function is - 77 Chatgpt will reduce score by -1 whenever it finds any of the char narek. 78 We will increase by +10 whenever we complete the string narek. 79 80 **Hint 4** 81 82 Now, $dp[i][j]$ can be the maximum score so far such that we have processed the first $i$ string, and we have got the first $j$ chars of uncompleted narek string (which is required for +10). 83 84 My submission — [281162411](/contest/2005/submission/281162411 "Submission 281162411 by aryanc403") 85 86 **Video Editorial** 87 88 [2005D - Alter the GCD](/contest/2005/problem/D "Codeforces Round 972 (Div. 2)") 89 90 **My solution has a bad time complexity. Anyways you can check what I did and what the reasoning was.** 91 92 My submission — [281180437](/contest/2005/submission/281180437 "Submission 281180437 by aryanc403") 93 94 **TLE solution** 95 96 [2005E1 - Subtangle Game (Easy Version)](/contest/2005/problem/E1 "Codeforces Round 972 (Div. 2)") 97 98 **Hint 1** 99 100 Use [Minimax Algorithm](https://youtu.be/KU9Ch59-4vw) 101 102 **Hint 2** 103 104 Let's say we know what positions a player playing $i+1$ can select and still win the game. 105 Can we use this information to find all the positions that a player playing $i$ move can select? 106 107 **Hint 3** 108 109 A player selecting $r,c$ on the move $i$ wins the game if and only if there is no position in $[r+1...n][c+1...m]$ which player playing $i+1$ move can select and win. 110 111 **Hint 3** 112 113 With careful implementation, one can solve the above problem in $O(N*M*L)$ time complexity. 114 115 My submission — [281195816](/contest/2005/submission/281195816 "Submission 281195816 by aryanc403") 116 117 **Video Editorial** 118 119 [2005E2 - Subtangle Game (Hard Version)](/contest/2005/problem/E2 "Codeforces Round 972 (Div. 2)") 120 121 **Hint 1** 122 123 First solve E1. 124 125 **Hint 2** 126 127 Consider the following testcase - 128 129 ``` 130 1 2 2 131 2 2 1 132 2 3 3 133 ``` 134 135 If a player has to select $2$ from somewhere, they should only select $(1,3)$ or $(2,2)$ or $(3,1)$. 136 Selecting $(2,1)$ instead of $(2,2)$, will just increase no of possible moves for the opponent. 137 138 **Hint 3** 139 140 We should ignore the nos not present in A. 141 For each nos present X in A and each column C, we can precompute maximum R such that $B[R][C]=X$. 142 143 **Hint 4** 144 145 Now, we should play this game only on these indexes. 146 With careful implementation on can solve it in $O(N*M+N*L)$. 147 148 My submission — [281209324](/contest/2005/submission/281209324 "Submission 281209324 by aryanc403") 149 150 **Video Editorial** 151 152 **Chat QnA**