### chokudai's blog

By chokudai, history, 3 years ago,

We will hold AtCoder Beginner Contest 213.physics0523

We are looking forward to your participation!

• +282

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +138 Why are there $8$ problems in recent ABCs? UPD: please upvote the announcement (the contest deserves much more contribution than my comment lol)
•  » » 3 years ago, # ^ |   +78 The fish in your profile picture is so cute!
•  » » » 3 years ago, # ^ |   -25 It's NOT a fish
•  » » » » 3 years ago, # ^ |   +4 r/woosh
 » 3 years ago, # | ← Rev. 4 →   +8 In D, forgot that I had to sort my adjacency vector as well. Got two WA and kept waiting for like 20 minutes. My bad :") Still got it at the last minute, GG.
 » 3 years ago, # |   +3 how to solve F? there's no editorial for it
 » 3 years ago, # |   +3 How to solve F?
 » 3 years ago, # |   +29 Any simpler way to solve F than suffix array?
•  » » 3 years ago, # ^ |   +7 How to do it with a suffix array?
•  » » » 3 years ago, # ^ |   +18 Build the suffix array and LCP array.Now, let $pos[i]$ denote position of suffix starting at index $i$ in the suffix array. $ans[i]$ will be sum of minimums of all segments ending at position $pos[i]-1$ and sum of minimums of all segments starting at $pos[i]$ (in the LCP array). Also an additional $n-i$ for LCP with itself.To find minimums on segment, we can find next smaller and previous smaller elements in the LCP array and using them precalculate the contribution of each prefix and suffix in $O(n)$.
 » 3 years ago, # | ← Rev. 2 →   +3 For Problem H I tried a very simple approach. For each node we have an array $ans$ with $T+1$ values counting the amount of paths with length $t$ to this node. I iterate $t$ from $0$ to $T-1$ and on each step I walk all paths from each node and update $ans[t+k]+=ans[t]*paths[k]$. This yields correct answers but obviously this is $O(MT^2)$ and gets TLE. What is the intended solution here?Edit: Editorial is out, it's Divide & Conquer with FFT. Guess it is time to learn FFT for me.
 » 3 years ago, # | ← Rev. 2 →   +11 PLEASE MAKE ABC PROBLEMS E F G H EASIER !!! IT IS A "BEGINNER" CONTEST!!! (I know that it's my problem, but they are yellow, orange, and red difficulty)
•  » » 3 years ago, # ^ |   +33 I think they are meant to be educational in a sense that you get to learn about advance techniques/data structures while solving them, and in many cases they tend to be easier (relatively) than the average problems that require such techniques/DS.
•  » » 3 years ago, # ^ |   +36 I think it's not bad though: although you might not be able to solve them this time, the problems are very educational and you can learn to solve problems like them in the future.
 » 3 years ago, # |   +7 Is LCP array well-known? Never heard of it and it came out of nowhere @ 500 points problem so...
•  » » 3 years ago, # ^ |   0 I mean the first codeforces edu videos are about suffix array and they also teach you about lcp arrays there. I’m pretty sure it’s a well known data structure for solving string problems and also has real-life applications
•  » » » 3 years ago, # ^ |   +44 I don't know why, but I dislike string algorithm/problems by instinct.. so never knew them. Thanks, on my list to study.
•  » » 3 years ago, # ^ |   +20 we finally met at the same blog...
•  » » » 3 years ago, # ^ |   0 there's one more guy with that pfp midnoon
•  » » » » 3 years ago, # ^ |   +1 tf
 » 3 years ago, # |   0 Can anyone tell how to solve E?
•  » » 3 years ago, # ^ |   +3 0-1 Bfs where 0 cost is when the adjacent squares are empty, and the 1-cost is when you punch a 2x2 right next to you
•  » » » 3 years ago, # ^ |   +1 But, let's say I'm at 'T' in the below grid — .... .T## .### ###. Now let's say I punch a neighbor — now there will exist a punch that lets me go through 2 hash symbols with 1 cost. How is the cost of second hash symbol handled if we don't track the state of cells? i.e. I don't understand how 0-1 BFS handles the case where I'm at the SECOND destroyed cell after punching.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 21112 11111 11011 11111 21112 If you stand in 0, and everything else is a wall, you can reach "cell 1" by one punch, and can reach "cell 2" by two punches.
•  » » » » 3 years ago, # ^ |   +1 You can mark every block you can reach with curent_num_of_punches + 1. Cause there no sense going some direction and from that path break back to current path — or else you would break it through in that second spot. And when you finish with all the cur cells — you goto cur+1.
•  » » 3 years ago, # ^ |   +1 I have uploaded a video editorial here that you may find useful: https://www.youtube.com/watch?v=UWGMq3oT9h0
•  » » » 3 years ago, # ^ |   +3 Thanks a lot! Your drawing helped clarify it — what made it click for me was that we're redefining each cell's adjacency list to include cells that are up to two hashes away. Thanks! :)
 » 3 years ago, # |   0 Can any one suggest me why My Problem D Solution is giving RE.
•  » » 3 years ago, # ^ |   +5 I haven't looked at your code but have explained my solution here: https://www.youtube.com/watch?v=-y2VIFMkz50
•  » » 3 years ago, # ^ |   0 I guess if you change line 16 from ll i = 0 to int i = 0 it'll work
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I changed all to integer.Still giving RE
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +2 Its giving you RE even on samples. Is there anything stoping you from running it locally and considering error output?
•  » » » » » 3 years ago, # ^ |   0 It's running fine locally. All the samples are giving correct output. Strange situation.
•  » » » » » » 3 years ago, # ^ |   +3 On line-14, change the data type of dfs from int to void. Should get you AC then.
 » 3 years ago, # | ← Rev. 2 →   +6 Another solution for H:Consider the naive dp,$f(u,i)=\sum_{e:(u,v)}\sum_t f(v,i-t)p(e,t)$Let $F_u=\sum_{i=0}^T f(u,i)x^i$,then we have $n$ variables(Polynomial) and $n$ equation. They are polynomials,so we can't use gauss's method directedly.let's take $L(L\ge n,L=2^k)$ roots of unity,$\omega_L^0,\omega_L^1..\omega_L^{L-1}$,replace $F_u$ with $F_u(\omega _L^k)$ for $k\in [0,L)$,and do gauss's method for them.then do IDFT to calculate the polynomials for the $L$ points values.$O(Tn^3+T\log T n)$update: it's wrong,see the comments below to see reasons.
•  » » 3 years ago, # ^ |   +10 Also,we could solve problem G in $O(2^nn^2)$,by subset convolution.
•  » » 3 years ago, # ^ |   +20 If I understood correctly, by we have $n$ variables(Polynomial) and $n$ equation you mean equations like $F_u = \sum \limits_{e : (u, v)} F_v \cdot p(e)$. These equations do not hold because the degree of LHS is $T$ but degree of the RHS is $2T$.
•  » » » 3 years ago, # ^ |   0 Oh yes,it's wrong.I want the equations hold $\mod x^{T+1}$,but if take $\omega_L^0...\omega_L^{L-1}$,the equations hold $\mod (x^{T+1}-1)$ (don't take mod,the roots exist,but may have infinity degree,so the results after taking mod are not the same.)Thanks a lot for pointing out my mistakes.
»
5 weeks ago, # |
-16

i think this code has waek test cases my solution also got ac in at coder the questio there is ABC 213 E i wanted to do this ques for long but in my head i was stuck ion one testcase which i think is p=not prent here

4 4

# ...

....

....

....

output should be :1

but it get AC even if 0 or 1 ant thing is printed can any have a dicussion with me regarding this