codeforces-scrape

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

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