awoo's blog

By awoo, history, 21 month(s) ago, translation, In English

1739A - Immobile Knight

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1739B - Array Recovery

Idea: BledDest

Tutorial
Solution (Neon)

1739C - Card Game

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1739D - Reset K Edges

Idea: BledDest

Tutorial
Solution (awoo)

1739E - Cleaning Robot

Idea: BledDest

Tutorial
Solution (awoo)

1739F - Keyboard Design

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +59
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Can someone suggest problems similar to Div2 C: Card Game, which requires DP, Combinatorics and some thinking. Thanks!

»
21 month(s) ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

For those who just want to see the recurrence used in solution for C:

$$$dp(n, p) = {n-1 \choose \frac{n}{2}}+ dp(n-2, p^{-1})$$$

Let $$$p$$$ represent some player, and $$$p^{-1}$$$ represent the opponent of that player.

»
21 month(s) ago, # |
  Vote: I like it +28 Vote: I do not like it

When does the robot break? Let the robot currently be in the cell (j,i) (0-indexed) and the next column with a dirty cell be nxti (possibly, nxti=i). The robot breaks only if both (1−j,nxti) and (j,nxti) are dirty.

I think there is a typo. break condition should be (1-j,nxti) and (j,nxti + 1)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, why does this greedy solution starting from the root and cutting whenever the depth exceeds the candidate does not work? TIA

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Consider the following input

    Input:

    1
    7 1
    1 1 3 2 5 5
    

    Output:

    2
    

    If you cut the tree whenever depth exceeds 2, you will require 2 operations, while the min. operations to make depth 2 is actually 1. Just make the tree and see why this happening :)

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

      is there any way to prove that you get the smallest number of edges if you start from bottom instead of top?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are the constraints so low for C?
I wrote a $$$O(n)$$$ solution which should easily work for $$$\Sigma n \geq 10^6$$$

The solution

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please help with my solution to problem E:

https://codeforces.com/contest/1739/submission/174503555

idea: dp[i][j][k] ; 0<=i<=1, 0<=j<=n-1, 0<=k<=2

dp[i][j][0] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j)

dp[i][j][1] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j), and cell (1-i,j) is already clean

dp[i][j][2] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j), and cells (1-i,j) and (1-i,j+1) are already clean

I store the index of next clean cell in row i in k00,k01,k02; and of row 1-i in k10,k11,k12

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Take a look at Ticket 16235 from CF Stress for a counter example.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much! Can you please clarify on the point below as well though?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Your statement looks reasonable to me. Probably a typo in the editorial.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E:

" When does the robot break? Let the robot currently be in the cell $$$(j,i)$$$ (0-indexed) and the next column with a dirty cell be $$$nxt_i$$$ (possibly, $$$nxt_i=i$$$). The robot breaks only if both $$$(1−j,nxt_i)$$$ and $$$(j,nxt_i)$$$ are dirty "

Shouldn't it break when $$$(1-j,nxt_i)$$$ and $$$(j,nxt_i+1 )$$$ are both dirty, and $$$( j,nxt_i )$$$ is clean ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep, that's a mistake in the editorial

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

BledDest!
Aho-Corasick is new algo for me and and read about this in cp-algorithms. They said if you need to find all strings from a given set in text, you need to use "exit links" to make code faster:

storing the nearest leaf vertex that is reachable using suffix links (this is sometimes called the exit link).
Link

As I see, you don't use this links or ncost array does this job?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah, ncost does the trick. Usually the exit links are helpful to traverse the whole path to the root along the suffix links without actually visiting non-terminal states of the Aho-Corasick (for example, this allows to find all occurrences of all strings we have to search for in $$$O(Ans)$$$); but in this problem, we are not interested in the actual occurrences themselves, only in their total cost, so precalculating it for each state is both easier and faster.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain problem E why it is not always optimal when the robot is at j-th row i-th column and $$$(1 - j, i)$$$ is dirty, $$$(j, i + 1)$$$ is clean, and we just always go to clean $$$(1 - j, i)$$$? I have been stuck by this for a long time but could not find any counter case :/

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    See this case:

    8
    00100110
    10001101
    

    You can see that if you clean the cell in (1, 3) (1-indexed, (row, col)) you will avoid doing some forced cleaning twice near the end.

    If you are doing DP, probably you just need to add one more transition to take care of this.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks you! It gets AC after I add this transition!

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

Can't figure out my mistake in problem D.

https://codeforces.com/contest/1739/submission/176283387

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

why my code for problem D always gives WA ? any help please .

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

    Take a look at Ticket 16324 from CF Stress for a counter example.

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

      Thanks a lot. it helps me to get my code accepted now. the problem is to clear visit and level arrays after each step from the binary search.

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

can anyone help me in D ?? 219602371

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

    Take a look at Ticket 17054 from CF Stress for a counter example.

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

      My output is same as the expected output in the counter example. Can you help me find another counter example

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

        It's not. Not atleast on my machine, hence the counter example. Please check for undefined behaviours in your code.

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

          Is the submission giving 2 on your machine ?

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

            Yes, of course, as you can see from the ticket details. Please use gdb to figure out the problematic area in your code.