[Solution] Stone Game solution codechef

Stone Game solution codechef – Initially, Alice and Bob both have a bag of NN stones each with every stone having a lowercase alphabet written on it. Both players know the stones of the other player.

Alice and Bob want to create a string SS of length 2N2⋅N using the stones they have. They play a game to create the string. The rules of the game are as follows:

  • Initially, all the indices of SS are empty.
  • Alice starts the game. The players take alternating turns. In each turn, the player can choose one of the stones from their bag and place it at any empty index ii (1i2N)(1≤i≤2⋅N) of SS.
  • The game ends when both the players have used all their stones.
  • Alice wants SS to be as lexicographically small as possible while Bob wants SS to be as lexicographically large as possible.

Stone Game solution codechef

Find the final string SS formed by characters written on stones if both Alice and Bob play optimally!

Note: A string XX is lexicographically smaller than a string YY if and only if one of the following holds:

  • XX is a prefix of YY and XYX≠Y
  • In the first position where XX and YY differ, the string XX has a letter that appears earlier in the alphabet than the corresponding letter in YY.

Input Format

  • The first line contains an integer TT – the number of test cases. The description of TT test cases follows:
  • The first line of each test case contains an integer NN – the number of stones each player has.
  • The second line of each test case contains a string AA of length NN describing the stones in Alice’s bag initially.
  • The third line of each test case contains a string BB of length NN describing the stones in Bob’s bag initially.

Output Format

For each test case, print the final string SS formed if Alice and Bob play optimally.

Stone Game solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • It is guaranteed that the sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

2
3
aza
abz
4
cccc
cccc

Sample Output 1 

azabza
cccccccc

Explanation Stone Game solution codechef

Test case-1: Initially Alice’s stones are aza , while Bob’s stones are abz. Initially SS is _ _ _ _ _ _.

  • Alice’s turn
    Alice puts stone a at index i=1i=1.
    String SSa _ _ _ _ _
    Alice’s stones: [za]
    Bob’s stones: [abz]

  • Bob’s turn
    Bob puts stone z at index i=2i=2.
    String SSa z _ _ _ _
    Alice’s stones: [za]
    Bob’s stones: [ab]

  • Alice’s turn
    Alice puts stone a at index i=3i=3.
    String SSa z a _ _ _
    Alice’s stones: [z]
    Bob’s stones: [ab]

Stone Game solution codechef

  • Bob’s turn
    Bob puts stone b at index i=4i=4.
    String SSa z a b _ _
    Alice’s stones: [z]
    Bob’s stones: [a]

  • Alice’s turn
    Alice puts stone z at index i=5i=5.
    String SSa z a b z _
    Alice’s stones: []
    Bob’s stones: [a]

  • Bob’s turn
    Bob puts stone a at index i=6i=6.
    String SSa z a b z a
    Alice’s stones: []
    Bob’s stones: []

Since both the players have used all their stones, the game ends.
So the final string SS is azabza.

Leave a Comment