Educational Codeforces Round 136 Editorial

1739A - Immobile Knight

Idea: BledDest

1739B - Array Recovery

Idea: BledDest

1739C - Card Game

Idea: BledDest

1739D - Reset K Edges

Idea: BledDest

1739E - Cleaning Robot

Idea: BledDest

1739F - Keyboard Design

Idea: BledDest

• 2 months ago, # ^ | I need help too; (●'◡'-)

• 7 weeks ago, # ^ | Take a look at Ticket 16232 from CF Stress for a counter example.

• 2 weeks ago, # ^ | sum of product 2 ....codechef

  • 2 weeks ago, # ^ | Thanks will look into it

    • 2 weeks ago, # ^ | btw this question can be done in O(n) , with some combinatorics and some thinking..wont require dp..

• 2 months ago, # ^ | What is the analytical base case of this recurrence ?

  • 7 weeks ago, # ^ | If a Alice has got the biggest card, he will win. Otherwise If the opponent will lose in the round with cards, the player will win in the round with cards. Otherwise : he will lose.

• 2 months ago, # ^ | ← Rev. 2 →   0 _ 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 ?

  • 7 weeks ago, # ^ | 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 card, then Alise will win in the round with cards. For example. Alice : Boris : Alice uses card and Boris uses card , then Alice has card and Boris has card . in this case ( cards in total) Alice will win in the game ( cards in total).

    • 7 weeks ago, # ^ | ← Rev. 3 →   0 I think i slightly get your idea, but waittt isnt the example you gave should be a draw

• 7 weeks ago, # ^ | Consider the following input Input: 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 :)

  • 7 weeks ago, # ^ | 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).

• 7 weeks ago, # ^ | Take a look at Ticket 16235 from CF Stress for a counter example.

  • 7 weeks ago, # ^ | Thank you so much! Can you please clarify on the point below as well though?

    • 7 weeks ago, # ^ | Your statement looks reasonable to me. Probably a typo in the editorial.

• 7 weeks ago, # ^ | yep, that's a mistake in the editorial

• 7 weeks ago, # ^ | 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 ); 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.

• 7 weeks ago, # ^ | 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.

  • 7 weeks ago, # ^ | Thanks you! It gets AC after I add this transition!

• 5 weeks ago, # ^ | Take a look at Ticket 16324 from CF Stress for a counter example.

  • 5 weeks ago, # ^ | 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.