Problem Statement
Eren is on a spree to conquer as many cities as possible in his journey of the rumbling. Each city is connected to one or more city in a directed or undirected way. Directed edges (a,b) mean he can go from city a to city b, but not the other way around. Undirected edges mean both directions are viable for the path. After careful consideration, he has finalized a path from his starting city to the last destination city he wants to rumble. There are some cities in the path which can be pillaged multiple times, these are marked by self loops in the graph.
A self-loop in a graph is when a node's outgoing edge goes to the same node, or in short, when the Edge List (E) contains one (or more) entries of the form (n,n).
In the decided optimum path, the self loops are represented by repeating the same node twice. For example, the optimal path for the above graph may be 1,1,2,2,3,3,4,4. However, if we pillage more than one city more than once, we may not have enough time to reach the destination in time. So, only one of the self-loop cities will be pillaged twice. The city with the highest node value would give the most benefit if pillaged multiple times.
Given the path representation of the cities, find out the best city to pillage.
Input Format
The first line of input is a single integer t, denoting the number of test cases. t test cases follow.
Each test case has two lines of input.
- First line: two space-separated integers n and m, n denoting the length of the path representation, and m being the total number of cities.
- Second line: a string s of length n, which is the path representation of the optimum path, with repeated nodes marking self loops.
Constraints
1 ≤ t ≤ 100
1 ≤ m ≤ 9
1 ≤ si ≤ m ∀i[1,n]
m ≤ n ≤ 2 × m
Loops bigger than self loops are not viable paths.
Output Format
For each test case, the output should be a single number x ∈ [1,m] denoting the city best suited for repeated pillaging. If there are no viable cities, return -1.
Sample Input 1
Input:
1
5 3
12233
Output:
3
Explanation
There are three cities that can be pillaged repeatedly, they are 1, 2, 3. Out of the three, 3 has the highest node value, thus being the best choice for pillaging.
Solution
def find_best_city(t, test_cases):
# Initialize an empty list to store results of each test case
results = []
# Loop through each test case
for case in test_cases:
n, m = case[0] # Ignore n and take m as the highest number
s = case[1] # The path representation as a string
# Check for the highest number (m) that is repeated in the string
while m > 0:
if s.count(str(m)) > 1: # If m is repeated more than once in the string
results.append(m) # Store m as the result for this test case
break # Exit the loop since we found the answer
m -= 1 # Decrement m to check for the next highest number
else:
# If no repeated number is found, append -1
results.append(-1)
return results # Return the list of results for all test cases
# Reading the number of test cases from input
t = int(input())
# Initialize a list to store all test cases
test_cases = []
# Loop to read each test case
for _ in range(t):
# Read n and m (we ignore n and only use m)
n, m = map(int, input().split())
# Read the path representation string s
s = input().strip()
# Append the test case as a tuple of ((n, m), s)
test_cases.append(((n, m), s))
# Get the results for all test cases by calling the function
results = find_best_city(t, test_cases)
# Print the results for each test case
for result in results:
print(result)
Sample Solution Provided by Instructor
def solve(num):
# Initialize a variable to keep track of the maximum digit found
# that is repeated consecutively in the string. We start with a
# placeholder character that is less than any possible digit.
max_digit = '\0'
# Loop through the string 'num', but stop one character early to
# avoid out-of-bounds access when checking the next character.
for index in range(len(num) - 1):
# Check if the current character is the same as the next character.
if num[index] == num[index + 1]:
# If it is, update max_digit to the maximum value between
# the current max_digit and the current character.
max_digit = max(max_digit, num[index])
# After the loop, if no consecutive repeated digit was found,
# max_digit would still be the initial placeholder '\0'.
# We return '-1' to indicate that no such digit exists.
# Otherwise, we return the largest digit that was found to be repeated consecutively.
return '-1' if max_digit == '\0' else max_digit
# Read the number of test cases (t) from the input.
t = int(input())
# Loop through each test case.
for _ in range(t):
# Read two integers 'n' and 'm' from the input.
# These integers are currently unused in the solve function.
n, m = map(int, input().split())
# Read the string 'num' from the input, which represents the number
# in which we are supposed to find the largest consecutive repeated digit.
num = input()
# Call the solve function with the input string 'num' and print the result.
print(solve(num))