awoo's blog

Educational Codeforces Round 125 Editorial
By awoo, history, 3 years ago, translation, In English

1657A - Integer Moves

Idea: BledDest

Tutorial
Solution (Neon)

1657B - XY Sequence

Idea: adedalic

Tutorial
Solution (adedalic)

1657C - Bracket Sequence Deletion

Idea: BledDest

Tutorial
Solution (vovuh)

1657D - For Gamers. By Gamers.

Idea: BledDest

Tutorial
Solution (awoo)

1657E - Star MST

Idea: BledDest

Tutorial
Solution (awoo)

1657F - Words on Tree

Idea: BledDest

Tutorial
Solution (awoo)
  • Vote: I like it
  • +119
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
3 years ago, # |
  Vote: I like it +59 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -41 Vote: I do not like it

video solution in Hindi -problem A Integer moves

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

BledDest thank you for such an interesting and good task D. I hope there will be more similar tasks

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Update:-I got it from the editorial thank u authors.

can someone please explain me the problem e i m unable to get it from the editorial.

Thanks in advance.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

There are two different $$$k$$$ in the editorial of E.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    awoo, please if you can make me understand the second part of the editorial of problem E (I am very much confused about the k's in the editorial ) and how the answer is written in dp[k][n] like we have n not k vertices. It is actually written the opposite (I think so) so please can you make me understand what is actually happening in the DP part of the editorial(how actually things are working) and what the two k's are? Seen the implementation but of not much help. Sorry if i am making it long.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      BledDest and awoo the editorial and the implementation in problem E are totally different can anyone please explain what's happening in implementation motivated from editorial.

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

        This two ways of solution looks different but the implementation just swapped j and t in the tutorial above. The writer uses some functions to make coding easier and I think is not so difficult to understand this implementation.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand this line from the D's tutorial. Can anyone help? You can see that for each cost c we can only leave one unit type of that price that has the largest value of d⋅h. Let's call it bstc. Thank you, in advance.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    suppose we have warriors h1,d1,c and h2, d2, c. They have the same cost. In this case we can pick one which have greater h * d and discard another from consideration. In other words for each 1 <= c <= C we can keep max 1 warrior with highest d * h

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E is very beautiful! Thank you.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, if we give the input : 5 ((((( the expected answer ACC to editorial is 2 1. However, I feel it should be 1 0 because it is already a palindrome and it will take only 1 operation to delete it. Can someone kindly point out where's the flaw in my thinking process?

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

    Because You have to always take the shortest prefix meaning (( and (( and (.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in case of problem A if I choose point 20,23 how can i reach their in 2 moves?

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Greedy algo for F (that might just be a special case of 2sat in the end? idk):

Dumb greedy: Place a string, then dfs to its intersecting string neighbors and try to fix those, and so on.

But this isn't correct: if you look at the cases where for a string $$$S$$$, flipping its neighbor $$$T$$$ both ways both work, then the algorithm can't decide which way to fix $$$T$$$.

But if flipping $$$T$$$ both ways works, that must necessarily mean that the nodes at $$$T \cap S$$$ are fixed letters. So just don't consider nodes with fixed letters as intersecting anymore; two strings are only intersecting if they share a node s.t. two letters are possible.

Now you can actually make the binary choice at each intersection, so greedy string fixing dfs works.

Time complexity is still $$$\widetilde{\mathcal{O}}(n + q + \sum_i^q|s_j|)$$$

The idea is similar to this problem

Implementation here, could be a lot cleaner.

→ Reply