405433: GYM101962 E Hat-Xor

After having a wonderful time at the Carnival test festival, Jão and his friends decided to go for an after party in his house. At some point Jão convinced them to play a classical mathematical puzzle. He put his friends in a line and gave each one of them a typical Carnival hat colored in black or white. They were arranged in such a way that they could only see the hats of people that were in front of them. In particular, the last person could see everyone's hat and the first could see nothing.

This game must be played from the last one on the line to the first. Each person should try, in this order, to guess the color of his own hat out loud. For that, the participants can agree on some strategy before getting the hats.

Jão had so much fun watching his drunk friends trying to tackle the puzzle. Now he decided to teach them a powerful strategy. Let $$$n$$$ be the number of participants in the game, and let they have numbers from 1 to $$$n$$$, from the first person in line to the last. Let the black hat have an associated value of $$$1$$$ and the white one have a value of $$$0$$$. Then we can always guess at least $$$n-1$$$ values correctly by following this strategy:

1. The last one in line have no information about his own hat, so he should guess the xor ($$$\oplus$$$) of all the hats he can see;
2. The others players in line should do something different. Let $$$X$$$ be the xor of the values guessed by previous players. Let $$$Y$$$ be the xor of the hats the current player can see. If $$$X = Y$$$, then his own hat must be white, otherwise it must be black;

Notice that every player will follow (2), except for the last one in line, which will follow (1). This strategy ensures that the first $$$n-1$$$ participants in line will guess correctly. Can you see why it works?

Unfortunately, Jão's friends are drunk, so they tend to mess the strategy up. When someone messes up, that means that he should have guessed $$$x$$$ according to the strategy, but guessed $$$x \oplus 1$$$. Your task, given the guesses of each participant in line, is to decide if there is a hat distribution such that we can say no one messed up given those guesses.

The only input line contains a binary string $$$s$$$ ($$$|s| = n \leq 10^5$$$). The $$$i$$$-th character of $$$s$$$ represents the color guessed by the $$$i$$$-th guy in the line (0 for white, 1 for black).

Output YES if there is a hat distribution such that we can say no one messed up. Otherwise, output NO.

10010

YES

01110

NO