Petr's blog

A clean slate week
By Petr, history, 4 years ago, In English

https://petr-mitrichev.blogspot.com/2020/11/a-clean-slate-week.html

  • Vote: I like it
  • +99
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Huh, as I read this, my solution to E seems to have zero things common with editorial as well. I solve $$$O(nk)$$$ problems where each element is $$$0$$$ or $$$1$$$ with some probability (depending on its position). For binary strings original problem can be solved while keeping two variables — what is the optimal cost if I have an interval opened and what if I don't have it opened. Using that insight, for each prefix I count number of sequences that will lead me to each state of dp (and there are $$$O(n^2)$$$ states of this dp for each prefix, so $$$O(n^3)$$$ in total, so my solution works in $$$O(n^4k)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Right, this is exactly my approach as well!

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    By the way, do you have a proof for the reduction to 0/1 problems? It feels right intuitively, but I can't formulate easily why :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      You might want to read the editorial to problem Landscaping from 2016 US Open. That's what I did during the AGC.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +56 Vote: I do not like it

        US Open? I thought they play tennis there or something :p

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I don't, I went with my intuition as well :p

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

    I believe this was roughly scott_wu's approach as well, though I think he optimized the DP down to n^2 transitions. I think this is actually not so different from the official solution; once you observe that it suffices to solve the 0-1 problem, the dp to solve the 0-1 version is really equivalent to the editorial's; you just got there without proving the 0-1 reduction.

    → Reply
»
4 years ago, # |
  Vote: I like it -53 Vote: I do not like it

sir recommend some good resources for cp

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    You don't need any just make one submission(Accepted or wrong answer doesn't matter) in a rated contest then you will reach 3000 in 9-10 days because 2_din_me_rating_double xD!

    → Reply