chokudai's blog

By chokudai, history, 17 months ago, In English

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!

  • Vote: I like it
  • +86
  • Vote: I do not like it

| Write comment?
»
17 months ago, # |
  Vote: I like it +38 Vote: I do not like it

E is same as codechef problem from this week — Problem.

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    can it be done with dfs? i tried dfs but got wa on 11 cases.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, DFS will TLE,you need to use multisource Dijkstra.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
17 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The editorial of G is lacking many details. Can someone provide more details on how we can optimize its DP using matrix exponentiation?

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    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 graph

    Link to submission

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$.

  • »
    »
    17 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Here is the $$$O(N . M . 2^6)$$$ dp

    const int bit = 6;
    
    vector<Mint> 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<Mint> 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<Mint> 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.

»
17 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

»
17 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Ok, what is the bug when you get only 4 WAs in G. UPD: I am stupid

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain G ?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it, thanks.

          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              17 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah, when I looked at the proof of Dijkstra then it all made sense why we use priority_queue in such situation.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please tell why this submission is giving wrong answer

https://atcoder.jp/contests/abc305/submissions/42171077

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E SubProof?

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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];
    }
}