Skip to main content

Uber

Uber OA 2023 - Magical Disappearing Dice Game

Problem Description:

Samuel has gifted Tina the Magical Dice Game for her birthday. This game involves a strip of T cells, where some cells are empty (denoted by 0), and some are blocked (denoted by 1). Tina and Samuel decide to play a competitive game on this strip. The game proceeds with players taking turns, and Tina goes first.

The game has the following rules:

  1. On their turn, a player must choose N contiguous empty cells and place a disappearing banner on them. Once the banner is placed, the cells are considered blocked for X turns, after which the banner disappears and the cells become empty again.
  2. If a player cannot find N contiguous empty cells on their turn, they lose the game.
  3. If neither player can make the first move (i.e., no N contiguous empty cells exist at the start), the game is automatically declared a tie.

You need to determine who will win the game: Tina, Samuel, or will the game result in a Tie (if it continues indefinitely or no valid move exists).

Input Format:

  • s: A binary string of length T, where 0 represents an empty cell and 1 represents a blocked cell.
  • Three integers: T, N, and X, where:
    • T: Total number of cells in the strip.
    • N: The number of contiguous empty cells required to place a disappearing banner.
    • X: The number of turns after which a banner disappears, and the cells become empty again.

Output Format:

  • Return a string representing the outcome of the game:
    • "Tina" if Tina wins.
    • "Samuel" if Samuel wins.
    • "Tie" if the game results in an infinite loop or neither player can start the game.

Constraints:

  • 1<=N<=T<=200
  • 1<=X<=20
  • The string s is a binary string of length T.

Sample Testcase 1:

Input:

s = "0011000"
T = 7
N = 2
X = 1

Output:

Tina

Explanation:

  • Tina starts the game and places a banner on cells 3 and 4 (s[2], s[3]).
  • Samuel cannot make a move as there are no remaining contiguous cells of size ( N = 2 ) available, so Tina wins.

Sample Testcase 2:

Input:

s = "0000011111"
T = 10
N = 3
X = 1

Output:

Tie

Explanation:

  • Tina places the banner on cells 5, 6, and 7.
  • Samuel places the banner on cells 9, 10, and 11.
  • After ( X = 1 ) turn, the cells that Tina originally covered (5, 6, 7) are available again, and Tina places her banner there.
  • The game goes on in an infinite loop, so the result is a Tie.