We will hold KYOCERA Programming Contest 2023(AtCoder Beginner Contest 305).
- Contest URL: https://atcoder.jp/contests/abc305
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230610T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: MMNMM, Nyaan, evima, nok0
- Tester: PCTprobability, nok0
- Rated range: ~ 1999
The point values will be 100-200-300-450-475-525-550-650. We are looking forward to your participation!
E is same as codechef problem from this week — Problem.
can it be done with dfs? i tried dfs but got wa on 11 cases.
No, DFS will TLE,you need to use multisource Dijkstra.
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.
It passed? I did the same it TLE'd.
https://atcoder.jp/contests/abc305/submissions/42162802
In the BFS, I only push neighbors to queue if neighbors' stamina are smaller than the current stamina.
Thanks, It got accepted with just one if statement.
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.
The editorial of G is lacking many details. Can someone provide more details on how we can optimize its DP using matrix exponentiation?
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,
Link to submission
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$$$.
Here is the $$$O(N . M . 2^6)$$$ dp
Where the function
ok(size,mask)
just checks whether a banned substring occurs in the stringmask
. Now make the transition matrix from dp to new_dp.Notice that
new_dp = mat * dp
. Your final answer is nowpower(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.Thanks for your reply.
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.
Ok, what is the bug when you get only 4 WAs in G. UPD: I am stupid
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...
Can someone explain G ?
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 thes
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
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?
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.
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 ATC
Submission on CC
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.
Got it, thanks.
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.
Yeah, when I looked at the proof of Dijkstra then it all made sense why we use priority_queue in such situation.
can anyone please tell why this submission is giving wrong answer
https://atcoder.jp/contests/abc305/submissions/42171077
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.yes,same mistake
thank you.
Problem E SubProof?
https://usaco.guide/CP2.pdf#page=107
Alternate solution for D, just walk through the map: