awoo's blog

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

| Write comment?
»
2 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.

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

video solution in Hindi -problem A Integer moves

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

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

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

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

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

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

E is very beautiful! Thank you.

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

In problem C if I give the input as ())( then the expected output should be 1 0 as the given input is a palindrome, but the solution provided in the editorial gives 1 2 as the output when run, which means that we have to leave the last 2 characters in the string, I don't understand how 1 2 is considered correct, can someone please explain. Thanks in advance.

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

    you've probably figured but () is a good substring and it is shorter than ())(

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

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

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

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

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