We will hold AtCoder Beginner Contest 213.physics0523
- Contest URL: https://atcoder.jp/contests/abc213
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210808T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: kyopro_friends, Nyaan
- Tester: sugarrr, physics0523
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
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
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)$$$.
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.
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
tf
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 —
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.
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.
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 = 0toint i = 0it'll workI changed all to integer.Still giving RE
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.
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.
My code
If I understood correctly, by
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.