### awoo's blog

By awoo, history, 20 months ago, translation,

1739A - Immobile Knight

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1739B - Array Recovery

Idea: BledDest

Tutorial
Solution (Neon)

1739C - Card Game

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1739D - Reset K Edges

Idea: BledDest

Tutorial
Solution (awoo)

1739E - Cleaning Robot

Idea: BledDest

Tutorial
Solution (awoo)

1739F - Keyboard Design

Idea: BledDest

Tutorial
Solution (BledDest)
• +59

| Write comment?
 » 20 months ago, # |   +2 Can someone suggest problems similar to Div2 C: Card Game, which requires DP, Combinatorics and some thinking. Thanks!
 » 20 months ago, # | ← Rev. 4 →   +10 For those who just want to see the recurrence used in solution for C:$dp(n, p) = {n-1 \choose \frac{n}{2}}+ dp(n-2, p^{-1})$ Let $p$ represent some player, and $p^{-1}$ represent the opponent of that player.
 » 20 months ago, # |   +28 When does the robot break? Let the robot currently be in the cell (j,i) (0-indexed) and the next column with a dirty cell be nxti (possibly, nxti=i). The robot breaks only if both (1−j,nxti) and (j,nxti) are dirty.I think there is a typo. break condition should be (1-j,nxti) and (j,nxti + 1)
 » 20 months ago, # |   0 In D, why does this greedy solution starting from the root and cutting whenever the depth exceeds the candidate does not work? TIA
•  » » 20 months ago, # ^ |   +1 Consider the following inputInput: 1 7 1 1 1 3 2 5 5 Output: 2 If you cut the tree whenever depth exceeds 2, you will require 2 operations, while the min. operations to make depth 2 is actually 1. Just make the tree and see why this happening :)
•  » » » 5 months ago, # ^ |   0 is there any way to prove that you get the smallest number of edges if you start from bottom instead of top?
 » 20 months ago, # |   0 Why are the constraints so low for C?I wrote a $O(n)$ solution which should easily work for $\Sigma n \geq 10^6$ The solution
•  » » 15 months ago, # ^ |   0 Can i ask a question？ why in editorial the dp[0][0][2] is 1 ？
•  » » » 12 months ago, # ^ |   0 my exact same doubt.
 » 20 months ago, # |   0 Someone please help with my solution to problem E:https://mirror.codeforces.com/contest/1739/submission/174503555idea: dp[i][j][k] ; 0<=i<=1, 0<=j<=n-1, 0<=k<=2dp[i][j][0] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j)dp[i][j][1] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j), and cell (1-i,j) is already cleandp[i][j][2] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j), and cells (1-i,j) and (1-i,j+1) are already cleanI store the index of next clean cell in row i in k00,k01,k02; and of row 1-i in k10,k11,k12
•  » » 20 months ago, # ^ |   +3 Take a look at Ticket 16235 from CF Stress for a counter example.
•  » » » 20 months ago, # ^ |   0 Thank you so much! Can you please clarify on the point below as well though?
•  » » » » 20 months ago, # ^ |   +3 Your statement looks reasonable to me. Probably a typo in the editorial.
 » 20 months ago, # |   0 For problem E:" When does the robot break? Let the robot currently be in the cell $(j,i)$ (0-indexed) and the next column with a dirty cell be $nxt_i$ (possibly, $nxt_i=i$). The robot breaks only if both $(1−j,nxt_i)$ and $(j,nxt_i)$ are dirty "Shouldn't it break when $(1-j,nxt_i)$ and $(j,nxt_i+1 )$ are both dirty, and $( j,nxt_i )$ is clean ?
•  » » 20 months ago, # ^ |   0 yep, that's a mistake in the editorial
 » 20 months ago, # |   0 BledDest!Aho-Corasick is new algo for me and and read about this in cp-algorithms. They said if you need to find all strings from a given set in text, you need to use "exit links" to make code faster: storing the nearest leaf vertex that is reachable using suffix links (this is sometimes called the exit link).Link As I see, you don't use this links or ncost array does this job?
•  » » 20 months ago, # ^ |   +3 Yeah, ncost does the trick. Usually the exit links are helpful to traverse the whole path to the root along the suffix links without actually visiting non-terminal states of the Aho-Corasick (for example, this allows to find all occurrences of all strings we have to search for in $O(Ans)$); but in this problem, we are not interested in the actual occurrences themselves, only in their total cost, so precalculating it for each state is both easier and faster.
 » 20 months ago, # |   0 Can somebody explain problem E why it is not always optimal when the robot is at j-th row i-th column and $(1 - j, i)$ is dirty, $(j, i + 1)$ is clean, and we just always go to clean $(1 - j, i)$? I have been stuck by this for a long time but could not find any counter case :/
•  » » 20 months ago, # ^ |   +13 See this case: 8 00100110 10001101 You can see that if you clean the cell in (1, 3) (1-indexed, (row, col)) you will avoid doing some forced cleaning twice near the end.If you are doing DP, probably you just need to add one more transition to take care of this.
•  » » » 20 months ago, # ^ |   +3 Thanks you! It gets AC after I add this transition!
 » 20 months ago, # |   0 Can't figure out my mistake in problem D.https://mirror.codeforces.com/contest/1739/submission/176283387
•  » » 20 months ago, # ^ |   +3 Take a look at Ticket 16293 from CF Stress for a counter example.
•  » » » 20 months ago, # ^ |   0 Thanks!
 » 20 months ago, # |   0 why my code for problem D always gives WA ? any help please .
•  » » 20 months ago, # ^ |   +3 Take a look at Ticket 16324 from CF Stress for a counter example.
•  » » » 20 months ago, # ^ |   0 Thanks a lot. it helps me to get my code accepted now. the problem is to clear visit and level arrays after each step from the binary search.
 » 10 months ago, # |   0 can anyone help me in D ?? 219602371
•  » » 10 months ago, # ^ |   0 Take a look at Ticket 17054 from CF Stress for a counter example.
•  » » » 9 months ago, # ^ |   0 My output is same as the expected output in the counter example. Can you help me find another counter example
•  » » » » 9 months ago, # ^ |   0 It's not. Not atleast on my machine, hence the counter example. Please check for undefined behaviours in your code.
•  » » » » » 9 months ago, # ^ |   0 Is the submission giving 2 on your machine ?
•  » » » » » » 9 months ago, # ^ |   0 Yes, of course, as you can see from the ticket details. Please use gdb to figure out the problematic area in your code.