### chokudai's blog

By chokudai, history, 4 months ago,

We will hold KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305）.

The point values will be 100-200-300-450-475-525-550-650. We are looking forward to your participation!

• +86

 » 4 months ago, # |   +38 E is same as codechef problem from this week — Problem.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 can it be done with dfs? i tried dfs but got wa on 11 cases.
•  » » » 4 months ago, # ^ |   0 No, DFS will TLE,you need to use multisource Dijkstra.
•  » » » 4 months ago, # ^ |   0 I sorted the guards with strengths from high to low. Then for each of them I ran BFS and only continue if the strength is > the strength so far.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 It passed? I did the same it TLE'd.
•  » » » » » 4 months ago, # ^ |   0 https://atcoder.jp/contests/abc305/submissions/42162802In the BFS, I only push neighbors to queue if neighbors' stamina are smaller than the current stamina.
•  » » » » » » 4 months ago, # ^ |   0 Thanks, It got accepted with just one if statement.
 » 4 months ago, # | ← Rev. 2 →   +5 Alternative "clean" solution to C: The cell in interest is the one, and the only one, where the cell itself is ., and two or more adjacent cells are #. Time complexity $O(NM)$, very clean.Alternative solution to G: Take ~10k first answers using bitmasks DP in $O(2^6nM)$. Then, take some "faith" to use Berlekamp-Massey, because the length of the recurrence will be somewhat less than 512. The problem is solved.
 » 4 months ago, # |   +3 The editorial of G is lacking many details. Can someone provide more details on how we can optimize its DP using matrix exponentiation?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +31 Suppose we have an empty string and append a character to it $n$ times. After appending each character, we must ensure that the current string does not contain any restricted substrings. Suppose $s_i$ is the string after appending $i$ characters. Suppose after the $i-$th step, we appended character $c$ to string $s_i$ such that it becomes $s_{i+1}$. Now we should ensure that $s_{i+1}$ does not contain any of the banned substrings. Since $s_i$ is valid till now, we need to look at only the last $6$ characters of $s_{i+1}$ to check whether it is valid. So we can look at it as a graph with an edge from $s_i$ to $s_{i+1}$. So we start our path from $s_0$(empty string) and reach $s_n$. Now we can have many possibilities for $s_i$, so we cannot store all $s_i$. Instead, we can just store the last $6$ characters of $s_i$.So, to sum up, you can make a graph of $x$ nodes, where each node represents some string which does not contain any banned substring. One node will correspond to an empty string. So you can visualise string $s$ as movement(starting from an empty string) from one node to another via directed edge.Since we are only concerned about strings of length less than $7$, $x \leq 127$. Our answer is a number of walks starting from an empty node with length $n$, which can be easily done using matrix exponentiation.Assume $s=abababab$ In this case, $s_0=$"" $s_1=a$ $s_2=ab$ $s_3=aba$ $s_4=abab$ $s_5=ababa$ $s_6=ababab$ $s_7=bababa$(notice that actually $s_7=abababa$, but we are only concerned with last $6$ characters) $s_8=ababab$(notice that actually $s_8=abababab$, but we are only concerned with last $6$ characters) Building graphqueue track; ll now=1; string use; track.push(use); pos[use]=1; auto bad=[&](string check){ for(auto it:avoid){ ll l=it.size(),r=check.size(); for(ll i=0;in){ break; } if(check.substr(i,l)==it){ return 1; } } } return 0; }; vector adj[MAX]; while(!track.empty()){ use=track.front(); track.pop(); for(auto c:{'a','b'}){ string cur=use; cur.push_back(c); if(bad(cur)){ continue; } if(cur.size()>6){ cur.erase(cur.begin()); } if(pos[cur]==0){ pos[cur]=++now; track.push(cur); } ll l=pos[use],r=pos[cur]; adj[l].push_back(r); } } Link to submission
•  » » » 3 months ago, # ^ |   0 Thanks for your reply. Your statement "Our answer is a number of walks starting from an empty node with length n" gave me a good hint so I did some research and analysis and found at the end that what we do simply is:Given that we have a matrix $dp$ where $dp[i][j]$ is the number of paths that start at $i$, end at $j$, and have a length $x$, and we have another matrix $adj$, where $adj[i][j]$ is $1$ if there is an edge from $i$ to $j$, then doing the matrix multiplication $dp\cdot adj$ will simply yield a new $dp'$ where $dp'[i][j] = \sum_{k=1}^{k=N}{dp[i][k]}$ (such that $adj[k][j]=1$), which is just $dp[i][j]$ for $x+1$.
•  » » 4 months ago, # ^ | ← Rev. 3 →   +3 Here is the $O(N . M . 2^6)$ dp const int bit = 6; vector dp(1 << bit); for(int mask = 0;mask < (1 << bit);mask++){ if(ok(bit,mask)){ dp[mask]++; } } for(int i = 0; i < n - bit; i++){ vector new_dp(1 << bit); for(int mask = 0;mask < (1 << bit);mask++){ for(int k = 0; k < 2; k++){ int new_mask = ((mask << 1) + k) & ((1 << bit) - 1); if(ok(bit,new_mask)){ new_dp[new_mask] += dp[mask]; } } } dp = new_dp; } Where the function ok(size,mask) just checks whether a banned substring occurs in the string mask. Now make the transition matrix from dp to new_dp. matrix mat(1 << bit,1 << bit); for(int mask = 0;mask < (1 << bit);mask++){ for(int k = 0; k < 2; k++){ int nmask = ((mask << 1) + k) & ((1 << bit) - 1); if(ok(bit,nmask)){ mat[mask][nmask] = 1; } } } Notice that new_dp = mat * dp. Your final answer is now power(mat,(n-bit)) * dp. You can calculate final dp in $O(\log n)$ instead of $O(n)$ using binary exponentiation. Here is my submission https://atcoder.jp/contests/abc305/submissions/42175122.
•  » » » 3 months ago, # ^ |   0 Thanks for your reply.
 » 4 months ago, # |   +16 I have another solution to C different from editorial which is much simpler.The answer is that cell which contains a '.' and has greater than 1 adjacent '#'s.
 » 4 months ago, # | ← Rev. 2 →   0 Ok, what is the bug when you get only 4 WAs in G. UPD: I am stupid
 » 4 months ago, # |   0 Is G based on matrix expo on 2D dp?I figured out the dp but had no clue how to convert a 2D dp to matrix expo...
 » 4 months ago, # |   0 Can someone explain G ?
•  » » 4 months ago, # ^ |   0 Consider Aho Corasick Automaton, where each node represent a state, and the edges are transitions. Inserting a string s will set all the states with the s as suffix bad. This can be precalculate by building the failure links. The problem can now be rephrased as "Starting from the root state, how many walks are there such that we didn't pass through a bad state", which can be done using matrix exponentiation.Submission
 » 4 months ago, # |   0 The test cases of Thank U, Next seems to be weak or weird. Today's Atcoder's Problem E was exactly the same just that queries were distinct. But my same solution to the former problem Solution of Codechef gave TLE at the latter problem Solution of Atcoder. Any suggestions on this issue?
•  » » 4 months ago, # ^ |   +11 You must check if the node is already in the (priority) queue before you push to it. If you don't do this, the time complexity may degenerate to (something higher than $O(V+E)$ but I am too lazy to prove a bound) in some cases. Learnt this through moments of pain. Many times it works without this optimization, but it is very important to know this.
•  » » » 4 months ago, # ^ |   0 Do we really need to use priority_queue? The edges are not weighted so I just used a normal multisource BFS but got TLE in 6 tc. And the same code got accepted in cc. Submission on ATCSubmission on CC
•  » » » » 4 months ago, # ^ |   0 Not really, but dijkstra is much more straightforward for most tasks like these. Do note that this optimization applies to BFS (or even non-recursive DFS) too.
•  » » » » » 4 months ago, # ^ |   0 Got it, thanks.
•  » » » » » » 4 months ago, # ^ |   +7 priority_queue is important here because your queue does not satisfy the bfs property that after a node is processed, all further nodes will have distance ≥ the previously processed nodes. The priority queue is used to pick the node with the least distance, it doesn't have anything to do with existence of weighted edges here. I guess cc tests were weak, it's easy to force a testcase which will result in O(n²) time complexity.
•  » » » » » » » 4 months ago, # ^ |   0 Yeah, when I looked at the proof of Dijkstra then it all made sense why we use priority_queue in such situation.
 » 4 months ago, # |   0 Submitted correct D 3 mins after the end of the contest because of a stupid mistake on prefix sum. Hurts.
 » 4 months ago, # |   0 can anyone please tell why this submission is giving wrong answerhttps://atcoder.jp/contests/abc305/submissions/42171077
•  » » 4 months ago, # ^ |   +11 I think u might have done the same mistake as I did. Once u output pre, u should read in the k vertices again, otherwise the input read later would be wrong.
•  » » » 4 months ago, # ^ |   0 yes,same mistakethank you.
 » 4 months ago, # |   0 Problem E SubProof?
 » 4 months ago, # |   0 Alternate solution for D, just walk through the map: for (auto& [t, node] : ranges) { if (node.type == 1) { last = t; } if (last != -1) { total += t - last; last = t; } if (node.type == 2) { last = -1; } for (auto& j : node.qbegin) { ans[j] = total; } for (auto& j : node.qend) { ans[j] = total - ans[j]; } }
 » 3 months ago, # | ← Rev. 10 →   0 In Problem G, I built the matrix $\boldsymbol M$ as the dp function, but I'm stucked at how to calculate the answer: signed main() { int n, m; cin >> n >> m; for (int i = 0; i < m; ++ i) { string s; cin >> s; int l = s.size(); int ans = 0; for (int c : s) ans = ans * 2 + c - 'a'; for (int k = 0; k < (1 << (6 - l)); ++ k) { in[(k << l) + ans] = 1; } } Mat M; for (int i = 0; i < 32; ++ i) for (int j = 0; j < 32 ; ++ j) M.a[i][j] = ((i & 15) == (j >> 1)) * (1-in[i * 2 + (j & 1)]); Mat X = M^n; int ans = 0; for (int i = 0; ans = 0, i < 32; ++ i, cout << ans << endl) for (int j = 0; j < 32 ; ++ j) ans += X.a[i][j]; } Its output: 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5