### chokudai's blog

By chokudai, history, 7 weeks ago, We will hold AtCoder Beginner Contest 213.physics0523

We are looking forward to your participation! Comments (41)
 » 7 weeks ago, # | ← Rev. 2 →   Why are there $8$ problems in recent ABCs? UPD: please upvote the announcement (the contest deserves much more contribution than my comment lol)
•  » » The fish in your profile picture is so cute!
•  » » » It's NOT a fish
•  » » » » r/woosh
 » 7 weeks ago, # | ← Rev. 4 →   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.
 » how to solve F? there's no editorial for it
 » How to solve F?
 » Any simpler way to solve F than suffix array?
•  » » How to do it with a suffix array?
•  » » » 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)$.
 » 7 weeks ago, # | ← Rev. 2 →   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.
 » 7 weeks ago, # | ← Rev. 2 →   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)
•  » » 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.
•  » » 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.
 » Is LCP array well-known? Never heard of it and it came out of nowhere @ 500 points problem so...
•  » » 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
•  » » » I don't know why, but I dislike string algorithm/problems by instinct.. so never knew them. Thanks, on my list to study.
•  » » we finally met at the same blog...
•  » » » there's one more guy with that pfp midnoon
 » Can anyone tell how to solve E?
•  » » 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
•  » » » 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.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   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.
•  » » » » 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.
•  » » » Thank you, I didnt know what was 01 bfs and turns out its just optimised dijkstra for a graph whose weight is 0 or 1.
•  » » I have uploaded a video editorial here that you may find useful: https://www.youtube.com/watch?v=UWGMq3oT9h0
•  » » » 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! :)
 » Can any one suggest me why My Problem D Solution is giving RE.
•  » » I haven't looked at your code but have explained my solution here: https://www.youtube.com/watch?v=-y2VIFMkz50
•  » » I guess if you change line 16 from ll i = 0 to int i = 0 it'll work
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   I changed all to integer.Still giving RE
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   Its giving you RE even on samples. Is there anything stoping you from running it locally and considering error output?
•  » » » » » It's running fine locally. All the samples are giving correct output. Strange situation.
•  » » » » » » On line-14, change the data type of dfs from int to void. Should get you AC then.
•  » » » » » » » Thanks a lot brother. It worked .But why function returning nothing matters here? I saw on CF judging system, functions return type doesn't even matter as long as you don't use the function return value.
 » 7 weeks ago, # | ← Rev. 2 →   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.
•  » » Also,we could solve problem G in $O(2^nn^2)$,by subset convolution.
•  » » 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$.
•  » » » 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.
 » 7 weeks ago, # | ← Rev. 2 →   Problem — C I am getting WA on only one test case, what I am doing wrong. please help MY Submission
 » I'm not familiar with Python. What does this mean in Problem C's tutorial? Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))} The whole solution: H,W,N=map(int,input().split()) X,Y=[],[] for i in range(N): x,y=map(int,input().split()) X.append(x) Y.append(y) Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))} Ydict = {y:i+1 for i,y in enumerate(sorted(list(set(Y))))} for i in range(N): print(Xdict[X[i]], Ydict[Y[i]])