### chokudai's blog

By chokudai, history, 2 months ago,

We will hold AtCoder Beginner Contest 211.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +56

 » 2 months ago, # |   +7 How to solve E?
•  » » 2 months ago, # ^ |   +15 I did it with DP on a broken state. Maintain the connected components of the last row when processing the next row.
•  » » » 2 months ago, # ^ |   0 How to calculate the upper bound of the valid combinations. (Except for taking hint from Sample 3)
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +12 You can see that consecutive red squares are in the same connected component, so there can be at most $4$ distinct connected components in a row.This gives you a bound of $5^8 = 390625$, which is enough to work with (for storage).Actual bound is much lower. Number of such connectivity states which are valid are called crossing-free partitions and are related to catalan numbers.
•  » » » » » 2 months ago, # ^ |   0 Hey!, why $5^8$ not $4^8$ ?
•  » » » » » » 7 weeks ago, # ^ |   0 Because a cell can have at max 4 distinct disjoint sets in its neigbourhood. Or it does not have any nearby, in which case it will create one disjoint set of its own.AwakeAnay correct me if I am wrong.
•  » » » 2 months ago, # ^ |   0 Can you share your code? Here is my submission but I was getting the wrong answer on sample test 3.
•  » » » » 2 months ago, # ^ |   +6
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 can you help me why my code outputs very big answer AwakeAnayi'm not sure whether i understand the problem correctly or not. https://atcoder.jp/contests/abc211/submissions/24516062
•  » » » 2 months ago, # ^ |   +6 Have you done E using broken state as $dp[i][mask][cnt]$ denote the number ways to colour cnt cells if we put mask in the ith column. As seems like I am undercounting as this mask may not be connected if mask in the previous column is already connected. I am finding no way to take that into account in this DP. As only checking the connectivity of current mask and previous mask is connected or not is not sufficient it seems.
•  » » » » 2 months ago, # ^ |   0 yes i got it, is there any way to solve it using dp or what
•  » » 2 months ago, # ^ |   0 Probably generate all k-nominos in all rotations then check on the template.Implementation looks annoying though.
•  » » 2 months ago, # ^ |   +5 Simple bitmask dp works here. Just label the squares from 0 to n*n-1, and the mask denotes which squares are currently colored red, and we can store the masks in a map. For the mask, use unsigned long long since it can go up to $2^{64}-1$. Then iterate through all the mask generated, and check if it has k set bits and if so, add it to the answer. I don't know the runtime for this code, but I assumed this approach should work due to the answer for 8*8 being small. Code
•  » » 2 months ago, # ^ |   +3 DP was not needed on problem E, just generate all polinominos of size k, there are not that many. To geneate all of size k, consider all of size k-1 and add a valid cell to it. Code
 » 2 months ago, # |   0 Is there solution for E using dp on profile? Thought a lot about that.
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   +2 My submission for problem D was basically a copy of https://www.geeksforgeeks.org/number-shortest-paths-unweighted-directed-graph/ because it doesn't make much sense to re-implement something else. Does AtCoder have any plagiarism checker, which could flag the use of third-party code?
•  » » 2 months ago, # ^ |   +4 Spirit of the contest relies in cracking and implementing algorithm by user himself instead of searching it on web.
•  » » » 2 months ago, # ^ |   0 The spirit of the contest is to be brutally efficient, while complying with the rules. If you voluntarily decide to handicap yourself, then you will have a worse position in the scoreboard and the other people will outperform you.What makes people brutally efficient? Let's look at the best of the best. The solution of the fastest solver of the problem D had been submitted only 1 minute and 31 seconds after the start of the contest! Their problem D solution was just a simplistic use of a pre-written graph library code. What about "cracking and implementing algorithm"? That's what I have done with problem C myself and this did cost me around 30 minutes. But it was apparently a well known classic problem too, so the best competitive programmers only spent a little bit more than a minute to find useful code snippets in their collections of pre-written code. And tourist also has demonstrated how true champions are doing this in the last Codeforces Global Round 15. He quickly noticed that the problem I from that round was a reuse of an older problem, so he reused the already existing solution for it.Even if a problem is not a direct copy of the older one, then a way to trivially reduce it to one of the already known solved problems still may exist.
 » 2 months ago, # | ← Rev. 2 →   +12 I actually hated problems C and D.How can problems be so common?Because problems should be made with original concepts at a certain level.
•  » » 2 months ago, # ^ |   +8 Well it's a beginner contest so I think it's fine. AtCoder seems to focus more on known algorithms and less on adhoc problems compared to Codeforces (at least in lower levels). Both approaches are valuable in my opinion.
•  » » » 2 months ago, # ^ |   0 Well, maybe you are right.But there will be very good problems in tomorrow's ARC for sure.
•  » » » » 2 months ago, # ^ |   0 Yes C was quite standard, although I failed to solve it . Could you comment some problem link which are like C ?
•  » » » » » 2 months ago, # ^ |   0
•  » » » » » » 2 months ago, # ^ |   0 i didn't understand the part where: if (a[i - 1] == b[j - 1]) lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j]; could anyone explain a bit? I'm a little confused as to why we are ignoring last character of the given string..
•  » » » » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 Some thoughts on problem D : Number of Shortest PathsThe important point to note is that in a BFS tree, edges can only exist between nodes at same level or consecutive levels.Let's label node 1 as $source$ and node $n$ as $target$. Consider any (shortest) path from $source$ to $target$. It's obvious that the last node in the path is $target$. But let's focus on the penultimate node. If the $target$ is at level $L$, then the penultimate node must've been at level $L - 1$. Moreover, all the nodes at level $L - 1$ which have a tree edge to $target$ at level $L$ are a possible candidate for the penultimate node. Hence, if we can somehow determine the number of shortest paths to these candidate nodes, the answer for the target node would be the sum of all contributions. Applying this process recursively, we have the DP definition, where, $dp[node]$ denotes the number of shortest paths that start at $source$ and end at node $node$ : dp[node] = sum(dp[penult]) where penult is the collection of all nodes in the previous level that share an edge with the current node The base case is $dp[source] = 1$.How to efficiently fill this DP? Start a BFS, and and whenever you encounter a children, check whether the children is from the next level or the current one. If the children would go to the next level, increase the DP value of the children by the DP value of the parent. If the children is from the same level, do nothing. Note that, as discussed earlier, the level difference can't be more than 1 in a BFS tree. Code#include using namespace std; const int mod = 1e9 + 7; void solve() { int n, edges; cin >> n >> edges; vector> adj(n); for(int i = 0; i < edges; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } queue bfs; vector level(n, -1); vector dp(n, 0); level[0] = 0; dp[0] = 1; bfs.push(0); while(not bfs.empty()) { auto source = bfs.front(); bfs.pop(); for(auto child : adj[source]) { if(level[child] == -1) { level[child] = level[source] + 1; dp[child] += dp[source]; dp[child] %= mod; bfs.push(child); } else if(level[child] == level[source] + 1) { dp[child] += dp[source]; dp[child] %= mod; } } } cout << dp[n - 1] << endl; } int main() { solve(); return 0; } 
 » 2 months ago, # |   +1 derp: forgot modulo twice, only noticed one of them during contest.
»
2 months ago, # |
0

Why in problem C, recursion with memoisation gives TLE, whereas the bottom-up approach works fine.

Code
•  » » 2 months ago, # ^ |   +1 It's because you are not passing the string by reference, thereby introducing an extra $n$ factor in the time complexity.
•  » » » 2 months ago, # ^ |   0 Ok, Thankyou, now it is passed
 » 2 months ago, # | ← Rev. 2 →   +5 My approach to C is different from editorial:https://atcoder.jp/contests/abc211/submissions/24490495
•  » » 2 months ago, # ^ |   +3 best approach
•  » » 2 months ago, # ^ |   +6 It's not different, you just use a different notation for states and do the same dp, just on a map.
 » 2 months ago, # |   0 Can you please add test cases for yesterday's contest? Couldn't find it on the dropbox link.
 » 2 months ago, # |   +8 I haven't seen my solution to F described, so I'll drop it here. For each polygon, take the points with the lowest x-coordinate, breaking ties by y-coordinate. Then let the value of that point be $1$, and label the rest of the points going clockwise (or counterclockwise, doesn't matter since $M$ is even) with $1, -1$. Now to query $(x + 0.5, y + 0.5)$, we simply want the sum of the values of points in the rectangle with opposite points $(0, 0), (x, y)$. The implementation of this is very straightforward if you have rectangle sum already implemented. You can also easily extend this to solve queries where you can alternate between adding/removing polygons and querying how many polygons a point is in.Submission
 » 4 weeks ago, # |   0 how to solve C