GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 5 October 2022

[Solution] Suspense String CodeChef Solution



Problem

Alice and Bob are playing a game with a binary string S of length N and an empty string T.
They both take turns and Alice plays first.

  • In Alice's turn, she picks the first character of string S, appends the character to either the front or back of string T and deletes the chosen character from string S.
  • In Bob's turn, he picks the last character of string S, appends the character to either the front or back of string T and deletes the chosen character from string S.

The game stops when S becomes empty.
Alice wants the resultant string T to be lexicographically smallest, while Bob wants the resultant string T to be lexicographically largest possible.

Find the resultant string T, if both of them play optimally.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integer N - the length of the string S.
Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

    • The next line is the binary string S.

Output Format

For each test case, print the the resultant string T, if both of them play optimally.

Explanation:

Test case 1: Alice picks the first bit which is 1 and appends it to the empty string T. Bob then picks the last bit 0 and appends it to the back of T making the resultant string to be 10.

Test case 2:

  • Alice picks 0 and adds it to T. Thus, S becomes 001 and T becomes 0.
  • Bob picks 1 and adds it to front of T. Thus, S becomes 00 and T becomes 10.
  • Alice picks 0 and adds it to front of T. Thus, S becomes 0 and T becomes 010.
  • Bob picks 0 and adds it to back of T. Thus, S becomes empty and T becomes 0100.

No comments:

Post a Comment