awoo's blog

By awoo, history, 2 months 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

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

can anyone help me in D 174113824

»
2 months 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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sum of product 2 ....codechef

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks will look into it

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        btw this question can be done in O(n) , with some combinatorics and some thinking..wont require dp..

»
2 months 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.

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

    What is the analytical base case of this recurrence ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • If a Alice has got the biggest card, he will win.
      • Otherwise
        • If the opponent will lose in the round with $$$n$$$ cards, the player will win in the round with $$$n + 2$$$ cards.
        • Otherwise : he will lose.
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    W Observation. I did this

»
2 months 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)

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

My solution to Prblem C in Div 2.

This is very interesting.

We can find that:

  • if Alice has the biggest number, he will win. Because he can use this card first.

  • Otherwise Boris has the biggest number, it's obvious that Boris will be "stronger" in the first turn, and he get first in the secound turn. So the number of ways that Alice wins is equal to the number of ways that Boris wins with $$$n - 2$$$ cards.

So we have $$$fst_i = \frac{C_{i}^{i/2}}{2} + lst_{i - 2}$$$.

There is another key to the task : the number of way to make a draw is equal to $$$1$$$. So $$$lst_i = C_{i}^{i/2} - fst_i - 1$$$.

My submission : 174191151

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

    _ So the number of ways that Alice wins is equal to the number of ways that Boris wins with n−2 cards_ i dont understand this part, can you explain how you get to that observaton ?

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

      Because in the first round, Boris is Stronger and plays cards first in the second round. (This is because Boris has got the biggest card). If Boris loses the round with $$$n - 2$$$ card, then Alise will win in the round with $$$n$$$ cards. For example.

      Alice : $$$2, 3$$$

      Boris : $$$1, 4$$$

      Alice uses card $$$2$$$ and Boris uses card $$$4$$$, then Alice has card $$$3$$$ and Boris has card $$$1$$$. in this case ($$$2$$$ cards in total) Alice will win in the game ($$$4$$$ cards in total).

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

        I think i slightly get your idea, but waittt isnt the example you gave should be a draw

»
2 months 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

  • »
    »
    2 months 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 :)

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

      Thank you! I should have observed that removing a complete sub tree at (h-1) is better than removing each of its children at (h).

»
2 months 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

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

Can anyone tell why this is giving WA? https://codeforces.com/contest/1739/submission/174471060

»
2 months 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

»
2 months 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 ?

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

    yep, that's a mistake in the editorial

»
2 months 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?

  • »
    »
    2 months 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.

»
2 months 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 :/

  • »
    »
    2 months 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.

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

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

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

can anyone tell what is the turn variable used for in Div2 C: Card Game solution 1

»
7 weeks 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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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.

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

BledDest Problem C-Card Game (Did you converted combination recurrence relation of solution 2 to bottom up dp in solution 1. How did you exactly come up with Solution 1.)

'we can use dynamic programming of the form dp x,y,t, where x is the number of characters A we used, y is the number of characters B we used'

Please could you give some recurrence relation to understand DP

one more thing to notice it is mentioned t=0 means draw but t=2 is draw in Solution1.

t is 0, 1 or 2 depending on whether our string coincides with the draw string (t=0),

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Reverse everything and make a problem and throw at our face.