Here's how it works:
You're given the string "?<???????????)??]???????}??"
The task is to find the number of ways to replace each question mark with one of the characters in the string "()<>[]{}" such that the end result is valid parentheses sequence.
For example:
()[]{}<> is valid
([]()){} is valid
]() is not valid
(]{} is not valid
([)) is not valid.
Here are some test cases:
?[?? has 4 completions.
???? has 32 completions.
)??? has 0 complteions.
More formally validity is defined by:
The empty string is valid.
If a string S is valid then a+S+b is valid where "+" is string concatenation. And a,b are open/close brackets of identical type.
If S_1 and S_2 are valid bracket strings then S_1 + S_2 is a valid bracket string.
Market resolves YES if anyone posts the answer in the comments or NO if market closes before that.
Market closes 7th of april.
Related questions
🏅 Top traders
| # | Name | Total profit |
|---|---|---|
| 1 | Ṁ120 | |
| 2 | Ṁ26 | |
| 3 | Ṁ20 | |
| 4 | Ṁ10 | |
| 5 | Ṁ6 |
By (kinda) induction, goal: all valid strings are of even length. Base case: the empty string is of 0 length, which is even. Inductive steps: 2: If S is valid, then the length of the next valid string, a+S+b, has length 2 + length(S), which is also even. 3: If S_1 and S_2 are valid, then the length of S_1 + S_2 is even + even, which is even. So: all valid strings are of even length.
length("?<???????????)??]???????}??") == 27, so any substitution of ?s by brackets will still be of length 27, so no substitution can be of even length, so no substitutions exist
So the number of ways is zero, 0.
note: i'm [private_info], so I'm pretty retarded today, so this might be wrong, as evidenced by several past mistakes today. but i'll be fine in a week so if this is dumb i'll try to solve it later