| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3845 |
| 2 | tourist | 3798 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3589 |
| 6 | Ormlis | 3532 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3463 |
| 9 | ecnerwala | 3451 |
| 10 | Um_nik | 3450 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | -is-this-fft- | 160 |
| 2 | Qingyu | 160 |
| 4 | atcoder_official | 157 |
| 5 | Dominater069 | 155 |
| 6 | adamant | 154 |
| 7 | djm03178 | 151 |
| 8 | luogu_official | 149 |
| 9 | awoo | 147 |
| 10 | Um_nik | 146 |
You're given a binary string. You can delete two equal adjacent characters however many times you like. Is it true that no matter how you delete adjacent characters, there is a unique shortest string that you can end up with?
I've been stuck on this for a while now. I suspect that the answer is yes, but I have no idea how to prove it. Please help me prove or disprove.
noone solves these hard things
Go touch some grass, bro. The obvious counter example is
001in which you can end up with both 0 and 1 at the end.Sorry, I forgot to mention they need to be equal.
Idk why but this lowkey feels AI generated
I actually want to know ._.
Final string will match regexp 0?(10)*1?. After all pairs of 00 and 11 eliminated total length will be the same. To make both 1010... and 0101... from same string by deleting pairs is impossible
I agree that the final string either looks like 0101... or 1010..., but didn't understand your reasoning for why 0101... and 1010... from the same string is impossible. What do you mean that "total length will be the same"? Length of what object?
I think he means the total length of the final string.
The answer is yes. Proof:
The only two possible resulting strings are 1010... and 0101... Consider a reversal of the process: starting with the end string and adding pairs of adjacent characters to produce the original string. It is impossible for to produce the same string from both of these resulting strings, so only one of them is a possible result.
Why is it impossible to produce the same string from 0101... and 1010... by adding 00s and 11s?
Flip every character on an even position, now the problem is that the operation is removing 10 or 01(since you're removing 2 characters at a time all other parities of positions are preserved, so doing this operation is just removing a 01 or 10 without the rest of the string being affected). You can always do that until the string is all 0s or all 1s. Let's say there are $$$x$$$ zeroes and $$$y$$$ ones in the new string. If $$$x>y$$$, the answer to the original problem is 01010... of length $$$x-y$$$, if $$$x<y$$$ it's 10101... of length $$$y-x$$$.
Genius! Thank you so much.
300iq solution