[Solution] Subtle Substring Subtraction solution codeforces

Subtle Substring Subtraction solution codeforces – Alice and Bob are playing a game with strings. There will be 𝑑tΒ rounds in the game. In each round, there will be a string 𝑠sΒ consisting of lowercase English letters.

[Solution] Subtle Substring Subtraction solution codeforces

Alice moves first and both the players take alternate turns.Β Alice is allowed to remove any substring of even length (possibly empty) and Bob is allowed to remove any substring of odd length from 𝑠s.

More formally, if there was a string 𝑠=𝑠1𝑠2β€¦π‘ π‘˜s=s1s2…skΒ the player can choose a substring 𝑠𝑙𝑠𝑙+1β€¦π‘ π‘Ÿβˆ’1π‘ π‘Ÿslsl+1…srβˆ’1srΒ with length of corresponding parity and remove it. After that the string will become 𝑠=𝑠1β€¦π‘ π‘™βˆ’1π‘ π‘Ÿ+1β€¦π‘ π‘˜s=s1…slβˆ’1sr+1…sk.

After the string becomes empty, the round ends and each player calculates his/her score for this round. The score of a player is the sum of values of all characters removed by him/her. The value of 𝚊aΒ isΒ 11, the value ofΒ πš‹bΒ isΒ 22, the value of 𝚌cΒ isΒ 33, ……, and the value of 𝚣zΒ isΒ 2626. The player with higher score wins the round. For each round, determine the winner and the difference between winner’s and loser’s scores. Assume that both players play optimally to maximize their score. It can be proved that a draw is impossible.

Input

The first line of input contains a single integer 𝑑tΒ (1≀𝑑≀5β‹…1041≀t≀5β‹…104) denoting the number of rounds.

Each of the next 𝑑tΒ lines contain a single string 𝑠sΒ (1≀|𝑠|≀2β‹…1051≀|s|≀2β‹…105) consisting of lowercase English letters, denoting the string used for the round. HereΒ |𝑠||s|Β denotes the length of the string 𝑠s.

It is guaranteed that the sum ofΒ |𝑠||s|Β over all rounds does not exceedΒ 2β‹…1052β‹…105.

[Solution] Subtle Substring Subtraction solution codeforces

For each round, print a single line containing a string and an integer. If Alice wins the round, the string must be “Alice“. If Bob wins the round, the string must be “Bob“. The integer must be the difference between their scores assuming both players play optimally.

Example
input

Copy
5
aba
abc
cba
n
codeforces
output

Copy
Alice 2
Alice 4
Alice 4
Bob 14
Alice 93

Subtle Substring Subtraction solution codeforces

For the first round,Β “πšŠπš‹πšŠ”βˆ’β†’βˆ’βˆ’βˆ’π™°πš•πš’πšŒπšŽπšŠπš‹πšŠ”β†’“𝚊”βˆ’β†’βˆ’π™±πš˜πš‹πšŠβ†’“”“aba”β†’Alice”aba”β†’”a”β†’Bob”a”β†’””. Alice’s total score isΒ 1+2=31+2=3. Bob’s total score isΒ 11.

For the second round,Β “πšŠπš‹πšŒ”βˆ’β†’βˆ’βˆ’βˆ’π™°πš•πš’πšŒπšŽ“πšŠπš‹πšŒβ†’“𝚊”βˆ’β†’βˆ’π™±πš˜πš‹πšŠβ†’“”“abc”β†’Alice”abc”β†’”a”β†’Bob”a”β†’””. Alice’s total score isΒ 2+3=52+3=5. Bob’s total score isΒ 11.

For the third round,Β “πšŒπš‹πšŠ”βˆ’β†’βˆ’βˆ’βˆ’π™°πš•πš’πšŒπšŽπšŒπš‹πšŠ”β†’“𝚊”βˆ’β†’βˆ’π™±πš˜πš‹πšŠβ†’“”“cba”β†’Alice”cba”β†’”a”β†’Bob”a”β†’””. Alice’s total score isΒ 3+2=53+2=5. Bob’s total score isΒ 11.

For the fourth round,Β “πš—”βˆ’β†’βˆ’βˆ’βˆ’π™°πš•πš’πšŒπšŽ“πš—”β†’“πš—”βˆ’β†’βˆ’π™±πš˜πš‹πš—β†’“”“n”β†’Alice”n”β†’”n”β†’Bob”n”β†’””. Alice’s total score isΒ 00. Bob’s total score isΒ 1414.

For the fifth round,Β “πšŒπš˜πšπšŽπšπš˜πš›πšŒπšŽπšœ”βˆ’β†’βˆ’βˆ’βˆ’π™°πš•πš’πšŒπšŽπšŒπš˜πšπšŽπšπš˜πš›πšŒπšŽπšœβ†’“”“codeforces”β†’Alice”codeforces”β†’””. Alice’s total score isΒ 3+15+4+5+6+15+18+3+5+19=933+15+4+5+6+15+18+3+5+19=93. Bob’s total score isΒ 00.

For Solution

Click here

Leave a Comment