PALINGAM - Editorial

[deadwing97]

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Primary Tester: Prateek Gupta
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

Two players A,B are playing a game. Player A has a string s with him, and player B has string t with him (of the same length and may consist of lowercase english letters only). Each player knows the string of the other player. Player A makes the first move and they keep alternating turns.
Players are building another string w which starts empty. In each move, a player removes any single character from his string and inserts this character at any position in w. If at any stage of the game, the string w is a palindrome and its length is greater than 1, then the player who made the last move wins. If both players strings are empty and w is not a palindrome then player B wins. Find out the winner assuming that both of them are playing optimally.

DIFFICULTY:

Easy

PREREQUISITES:

EXPLANATION:

This problem is solved by breaking this game into few scenarios:

Scenario 1

If all of first player’s letters are present into the second’s string, then the second player wins after his first move (the first player picks any letter and the second appends the same letter to w achieving a palindrome of length 2).

Scenario 2

So the first player’s move must be a unique letter (not present in the second’s string). So his string must contain at least one unique letter. It’s obvious that the second player must choose a unique letter (not present in the first player’s string). Otherwise the first player would just choose the same letter the second player had chosen in his first move achieving a palindrome of length 3, and winning the game after his second move.

Scenario 3

In case both of them had at least one unique letter, if the first player had a unique letter occurring at least twice, he would win easily. Picking this letter in his first and third move would result into a palindrome of length 3 (regardless of the second player’s move).

Any Other Scenario

If none of the above described scenarios is fulfilled, then player B would win for sure, that’s because there will be at least 2 unique letters in the string after the second move (and the first player’s letter) has no other copy (otherwise scenario 3 is fulfilled). And it’s clear that no palindrome can contain 2 unique letters. So the game is in second player’s control, he can just postpone placing the other copies (of his first played unique letter) or even place them arbitrarily so no palindrome is formed at any stage (Note that in some scenarios the second player may be able to form a palindrome but it doesn’t matter because he is the winner anyway). If no other copies exist then no palindrome ever

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: Can be found here
TESTER’s solution: Can be found here
EDITORIALIST’s solution: Can be found here

[dpraveen]

Here is an outline of a more formally written proof if you are interested.

Lemma:

A wins if and only if one of the following two situations happens.
1. There exists a character x that appears twice in S, but doesn’t occur in T.
2. The characters of T are a subset of S, and there exists a character in S that doesn’t occur in T.

In all other cases, B wins.

---

Proof:

Let S denote the multiset of characters of string s.
Similarly, we define mutliset T of characters of string t.

We define a multiset S to be subset of multiset T if each character in S exists at least once in T.

Assume S <= T (i.e. S is a subset of T). Then the B wins by the following strategy - In the second move, B puts exactly the same character as that of A’s character in the first move.

Henceforth, we assume the contrary, i.e. S is not a subset of T i.e. there exists a character x that exists only in S but not in T.

Case 1: The character x occurs at least twice in S. A wins in this case. A will put x, then B will put y s.t. y != x (x is not present in T). Now A will make palindrome xyx by putting x.

Case 2: The opposite of Case 1. All the characters in S\T occur exactly once in S, and the set S\T is non-empty, i.e. there exists an x that appears exactly once in S, but not in T.
There will be two cases in it.
1. T is a subset of S.
In this case, A wins. A puts x in his first move. B will put some character y to form xy. Now, A will put y again to form yxy and will make a palindrome.
2. Otherwise. There exists a character y that doesn’t exist in S.
In this case, B wins. The game can proceed as follows.
- Case a). In the first move, A puts a character c that exists in T. In this case B wins by putting c again and making cc.
- Case b). In the first move, A will put a character x, that doesn’t exist in T.
In the second move, B will put character y, that doesn’t exist in S. Note that x != y.
Case 1. Let the number of occurrence of y be 1. In this case, one can never form a palindrome as both x and y appear exactly once in S U T. There can’t be palindrome with two characters with odd occurrences.
Case 2. The number of occurrence of y is strictly greater than 1. In this case, B’s strategy would be to append y on only one of the sides (either left or right). As x occurs only once. It should be the center of the palindrome. As all y’s are only one side, the string can’t be a palindrome centered around x. The character y only exists in string t. So B can always do so.

Hence proved.