PROBLEM LINK:
Author: Shivam Singh
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin
PROBLEM
Two teams are making penalty series. You’re given a string of length 20 each character of which denotes whether the appropriate team made a successful shot or not. Determine the winning team or report about the tie.
QUICK EXPLANATION
Split the string into two parts and determine the outcome of the each part independently.
EXPLANATION
The problem consists of two parts and solves differently for each part. So first of all divide the given string into two halves.
Subtask 1 solution
The additional constraint about a tie after the first 10 kicks allows you to skip the solution for the first half of the string and start solving from the second one.
Subtask 2 solution
Look at the first half of the string. One team wins in the first half of the shoot-out series if in some moment its score is bigger than the score of the other team plus the number of attempts that team can make before the first half of the game ends. For implementation this in the simplest way keep four variables a, b, c, d denoting respectively how many goals the first team has made, how many goals the second team has made, the number of attempts the first team still can make and in the same way, the number of attempts the second team still can make. Now iterate through the first half of the string. Suppose the first team is making a kick now (when the current index i of the string is even in 0-indexation). Then the number of its attempts decreases by one, i.e. c = c – 1 and, if the i-th character of the string is equal to 1, a increases by 1, i.e a = a + 1. Now, if a > b + d, the first team wins so print "TEAM-A i+1" and exit the program. In the same way, if the second team makes step now, decrease d by one and, if the i-th character of the string is 1, increase b by one. Check whether b > a + c and, if so, print "TEAM-B i+1" and terminate the program.
Suppose no team won the shoot-out in the first half of the game. Then it’s need to check the second half of the string. In this case, the first team wins if it makes a goal in its kick and on the next step the second team does not. Similarly, the second team wins if it makes a goal in its kick and on the previous step the first team does not. So divide the second half of the string into 5 equal parts and find the first one equal to “10” (corresponding the first team wins) or “01” (the second team wins). If there is no such string print “TIE”.
Time compexity per test: O(N), N = 20.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.