Ninja World Tournament

1) An integer “A”: Introduce a new score of ‘A’ on the track record. 2) "+": Introduce a new score on the track record that is the sum of the previous two scores. 3) "C": Nullify the previous score, removing it from the track record. 4) "D": Introduce a new score on the track record that is double the previous score.

The first line of input contains an integer 'T' representing the number of test cases. The first line of each test case contains an integer ‘N’ representing the number of operations in the list of strings, ‘MATCHRESULT’. The next line of each test case contains ‘N’ space-separated strings representing the operations in the list of strings, ‘MATCHRESULT’.

1 <= T <= 5 1 <= N <= 1000 MATCHRESULT[ i ] ∈ {[-3 * 10 ^ 4, 3 * 10 ^ 4], “+”, “C”, “D”} Where ‘T’ is the number of test cases, ‘N’ is the number of operations in the list of strings, ‘MATCHRESULT’ and ‘MATCHRESULT[ i ]’ is the ‘i’th operation in the list of strings, ‘MATCHRESULT’. Time limit: 1 second.

Test Case 1 : Given MATCHRESULT = {“2”, “3”, “+”, “D”, “C”}. Initially, TRACKRECORD = {}. For “2”, Introducing 2 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {2}. For “3”, Introducing 3 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {2, 3}. For “+”, Introducing the sum of 2 and 3, i.e., 5 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {2, 3, 5}. For “D”, Introducing the double of 5, i.e., 10 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {2, 3, 5, 10}. For “C”, Nullifying the score 10 and thus removing it from the ‘TRACKRECORD’. Therefore, TRACKRECORD = {2, 3, 5}. Sum of all the scores = 2 + 3 + 5 = 10. Test Case 2 : Given MATCHRESULT = {“15”, “C”, “10”, “D”}. Initially, TRACKRECORD = {}. For “15”, Introducing 15 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {15}. For “C”, Nullifying the score 15 and thus removing it from the ‘TRACKRECORD’. Therefore, TRACKRECORD = {}. For “10”, Introducing 10 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {10}. For “D”, Introducing the double of 10, i.e., 20 on the ‘TRACKRECORD’. Therefore, TRACKRECORD = {10, 20}. Sum of all the scores = 10 + 20 = 30.

Brute Force

The idea is to use the brute force approach. We will traverse the list of strings, ‘MATCHRESULT’ and introduce the score in the ‘TRACKRECORD’ as per the given conditions.

Algorithm:

Declare a vector of integers, ‘TRACKRECORD’ to record the scores.
Run a loop for each operation string, ‘OP’ in ‘MATCHRESULT’.
- if OP == “+”, that shows that we have to introduce a new score which is sum of the previous two scores. Therefore,
  - Sum the previous two scores and insert it at the end of the ‘TRACKRECORD’.
- Else if OP == “C”, that shows that we have to nullify the previous score. Therefore,
  - Remove the last element from the ‘TRACKRECORD’.
- Else if OP == “D”, that shows that we have to introduce a new score which is the double of the previous score. Therefore,
  - Double the previous score and insert it at the end of the ‘TRACKRECORD’.
- Else, ‘OP’ is an integer string. Therefore,
  - Convert the string ‘OP’ to integer and insert it at the end of the ‘TRACKRECORD’.
Declare an integer variable, ‘SUMSCORE’ to store the sum of all the scores present in the ‘TRACKRECORD’.
Run a loop for each integer variable, ‘SCORE’ in the ‘TRACKRECORD’.
- Add ‘SCORE’ to the ‘SUMSCORE’.
In the end, return ‘SUMSCORE’.

Time Complexity

O(N), where ‘N’ is the number of operations in the list of strings, ‘MATCHRESULT’

Since the loop runs ‘N’ times to process each string of ‘MATCHRESULT’ and each iteration of the loop takes constant time for execution. Therefore, the overall time complexity = O(N) * O(1) = O(N).

Space Complexity

O(N), where ‘N’ is the number of operations in the list of strings, ‘MATCHRESULT’

Since the array, ‘TRACKRECORD’, takes O(N) space in the worst case. Therefore, the overall space complexity is O(N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Output 1:

Sample Input 2:

Sample Output 2: