Could not find any discussion on problems, so I am posting here.

How to solve B and L?

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

1 | tourist | 3771 |

2 | jiangly | 3688 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | djq_cpp | 3486 |

6 | MiracleFaFa | 3466 |

7 | ksun48 | 3452 |

8 | Radewoosh | 3406 |

9 | greenheadstrange | 3393 |

10 | xtqqwq | 3382 |

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

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 171 |

7 | adamant | 168 |

8 | maroonrk | 167 |

9 | antontrygubO_o | 166 |

10 | errorgorn | 164 |

Could not find any discussion on problems, so I am posting here.

How to solve B and L?

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/10/2022 08:29:09 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

B:

An interval [L,R] of 1s (0 at the L-1 and R+1) is possible if and only if, the number of fallen boxes in this interval equals R-L+1 and also there's no boxes in L-1 and R+1. So we can use a dp solution. After this observation and

O(N^{3}) dp solution it's easy to decrease complexity.O(N^{3}) Solution: https://ideone.com/fM5nVpO(N^{2}) Solution: https://ideone.com/7pZh4RO(N*log(N)) Solution: https://ideone.com/GHDnd1O(N) Solution: https://ideone.com/L9o6dzL: Answer is always 2 or 3, I think it's easy to come up with a solution to calculate the number of ways after that.

Thanks a lot. In L, what is the proof that answer will always be 2 or 3?

The number of the edges is 4(

n- 1) and there are only n nodes. So there must be a node with degree ≤ 3.In L, can you please give me some hints on how to calculate the number of ways?

The solution after being aware of that the answer is 2 or 3, can be enumerate the cutting edge on a tree, and calculate which of the edges should be cut on the other tree. A trick solution is to use LCA and cal sum of subtree when using DFS. Another solution is just use dsu on tree, then u can easily calculate the answer.