Hi guys, I got stuck in a problem and i want to make test generation but idk how to generate a regular bracket does anyone know how to do that?

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

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

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

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 154 |

5 | maroonrk | 153 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

Hi guys, I got stuck in a problem and i want to make test generation but idk how to generate a regular bracket does anyone know how to do that?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2024 15:12:34 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Maintain stack. Randomly choose an operation to add a forward bracket or reverse bracket. When you add a forward bracket, add it to the stack. Add a reverse bracket only if there is at least one forward bracket in the stack. And in that case remove one forward bracket from the stack. In order to maintain a size limit, note that a bracket sequnce of size 2n has exactly n forward brackets. So use it to restrict the length of the sequence.

I found my mistake btw thank you so much for the solution :D

You can represent a regular bracket sequence as an Eulerian traversal of a tree — an opening bracket ( is a descent into a new vertex, a closing bracket ) is an ascent to an ancestor vertex.

Random trees can be generated using a Prüfer code. Then it becomes possible to generate a regular bracket sequence with equal probability.

What a nice idea! thank you :DD

I tried to write it and I think I successfully implemented for it. This is the source code for anyone who need it: https://ideone.com/cLbvx9

Thanks so much, guys!

This generates

someregular bracket sequence, and it may be enough. But also may be too regular for some uses. For example, the generated sequence is symmetric: $$$i$$$-th bracket from the left and $$$i$$$-th bracket from the right are always different.