# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 202 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/18/2021 16:31:04 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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)$$$.

Right, this is exactly my approach as well!

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 :)

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

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

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

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.

sir recommend some good resources for cp

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

xD!2_din_me_rating_double