I posted this question 2 times before, but one expert gave me a wrong solution and one expert gave me solution but it passed 38 test cases out of 50. I attached my code very below as well, so you can improve from there, but I think since I am getting time limit execution for some test cases, I think I need some Dynamic Programming way solution. Before you give me the Python code and solution, please run the sample input test cases and check you are getting the right sample output. Currently, my Python code execution time is about 0.47 seconds, so I need a better solution to improve this runtime execution.

Question:

Sample Input:

5 3 100 75 45 80 30 55 95 2 100 65 90 20 30 5 150 35 105 100 45 75 115 75 55 35 105 7 150 70 95 15 65 85 75 55 105 80 10 90 115 110 45 8 200 35 30 50 80 70 15 10 40 70 20 20 85 65 40 25 50

Sample Output:

#1 15 #2 -1 #3 25 #4 -1 #5 45

What I did tried to get all permutations of [inflation, deflation] list and from each permutation, I used binary search to find minimal initial tire pressure list.

I am failing some 12 test cases and I can't see the detail reason, but I assume that is time limit execution because permutation requires O(N!) time complexity, so I think I need some Dynamic Programming way to solve this I think, but not sure. At the very below comment of my current solution code, you can removed the comment sign and check the execution time.

My current solution:

import sys

sys.stdin = open("sample_input.txt", "r")

import time

start_time = time.time()

from itertools import permutations

def calcuateInitialTirePressure(ordredTirePressureList, potentialInitialTirePressure):

startingTirePressure = potentialInitialTirePressure

for i in range(len(ordredTirePressureList)):

currInflation, currDeflation = ordredTirePressureList[i][0], ordredTirePressureList[i][1]

startingTirePressure += currInflation

if not (0

return float("inf")

startingTirePressure -= currDeflation

if not (0

return float("inf")

return potentialInitialTirePressure

def getInitialTirePressure(permutationIndexList):

ordredTirePressureList = []

for i in permutationIndexList:

ordredTirePressureList.append(tirePressures[i])

minTirePressure = float("inf")

maximumStartPressure = 100 - ordredTirePressureList[0][0]

start, end = 0, maximumStartPressure

while start

mid = (start + end) // 2

potentialInitialTirePressure = calcuateInitialTirePressure(ordredTirePressureList, mid)

if potentialInitialTirePressure == float("inf"):

start = mid + 1

else:

minTirePressure = min(potentialInitialTirePressure, minTirePressure)

end = mid - 1

return minTirePressure

def getAppropriateInitialTirePressure(n):

minStartPressure = float("inf")

permutatedPressuresIndexList = list(permutations(range(n)))

for permutationIndexList in permutatedPressuresIndexList:

currInitialPressure = getInitialTirePressure(permutationIndexList)

if currInitialPressure == float("inf"):

continue

minStartPressure = min(minStartPressure, currInitialPressure)

# If no valid orderings were found, return -1

if minStartPressure == float("inf"):

return -1

return minStartPressure

T = int(input())

for test_case in range(1, T+1):

n, k = map(int, input().split())

inflate = list(map(int, input().split()))

deflate = list(map(int, input().split()))

tirePressures = [[inflate[i], deflate[i]] for i in range(n)]

result = getAppropriateInitialTirePressure(n)

print("#{} {}".format(test_case, result))

# print("--- %s seconds ---" % (time.time() - start_time))

Samsung tire is before its launch. Prior to its product launch, it will test the safety of the tire. In order to launch the tire, the tire must pass N tests in total. Each test is constructed of "inflate" and "deflate" \begin{tabular}{|c|} \hline [inflate] \\ 10 \\ [deflate] \\ 20 \\ \hline \end{tabular} and has the following features: (1) Each test starts with "inflate" first and then "deflate". (2) As long as all N test cases are executed, the test order can be randomly chosen. The maximum air pressure of the Samsung tire is K. The tire gets damaged, if the inner air pressure of the tire exceeds K or is less than 0. For instance, given the maximum tire air pressure K=100 and the initial air pressure as 60 , the tire in the following two cases will get damaged. For instance, given the maximum tire air pressure K=100 and the initial air pressure as 60 , the tire in the following two cases will get damaged. Given N, K and N number of test cases, find the test order so that the initial tire air pressure can be minimized. Print the value of the initial air pressure! (However, if there is no correct answer, print "-1"). For instance, suppose there are 3 test cases (N=3) as demonstrated below and the maximum tire air pressure is 100(K=100). \begin{tabular}{|c|c|c|} \hline [inflate]75 & [inflate]45[deflate]30 & [inflate]80 \\ [deflate] & [deflate]95 \\ \hline \end{tabular} The order of testing so that the initial tire air pressure can be minimized is shown below which is 15 in this case. (The blue numbers denote the air pressure after either "inflate" or "deflate") The order of testing so that the initial tire air pressure can be minimized is shown below which is 15 in this case. (The blue numbers denote the air pressure after either "inflate" or "deflate") Below is an example of tire damage, independent of the initial air pressure and the order of testing. (N=2,K=100) The answer is "-1". [Constraints] 1N850K200 [Input] The first line contains a single integer T-the number of total test cases. From the next line on each test case is given. Each test case consist of 3 linesthe first line contains N,K, the second line contains the "inflate" value for each test case and the third line contains the "deflate" value for each test case. [Output] Print "\#t" (without the quotes), leave a blank space and print the answer. (t refers to the test case number and starts with 1). Samsung tire is before its launch. Prior to its product launch, it will test the safety of the tire. In order to launch the tire, the tire must pass N tests in total. Each test is constructed of "inflate" and "deflate" \begin{tabular}{|c|} \hline [inflate] \\ 10 \\ [deflate] \\ 20 \\ \hline \end{tabular} and has the following features: (1) Each test starts with "inflate" first and then "deflate". (2) As long as all N test cases are executed, the test order can be randomly chosen. The maximum air pressure of the Samsung tire is K. The tire gets damaged, if the inner air pressure of the tire exceeds K or is less than 0. For instance, given the maximum tire air pressure K=100 and the initial air pressure as 60 , the tire in the following two cases will get damaged. For instance, given the maximum tire air pressure K=100 and the initial air pressure as 60 , the tire in the following two cases will get damaged. Given N, K and N number of test cases, find the test order so that the initial tire air pressure can be minimized. Print the value of the initial air pressure! (However, if there is no correct answer, print "-1"). For instance, suppose there are 3 test cases (N=3) as demonstrated below and the maximum tire air pressure is 100(K=100). \begin{tabular}{|c|c|c|} \hline [inflate]75 & [inflate]45[deflate]30 & [inflate]80 \\ [deflate] & [deflate]95 \\ \hline \end{tabular} The order of testing so that the initial tire air pressure can be minimized is shown below which is 15 in this case. (The blue numbers denote the air pressure after either "inflate" or "deflate") The order of testing so that the initial tire air pressure can be minimized is shown below which is 15 in this case. (The blue numbers denote the air pressure after either "inflate" or "deflate") Below is an example of tire damage, independent of the initial air pressure and the order of testing. (N=2,K=100) The answer is "-1". [Constraints] 1N850K200 [Input] The first line contains a single integer T-the number of total test cases. From the next line on each test case is given. Each test case consist of 3 linesthe first line contains N,K, the second line contains the "inflate" value for each test case and the third line contains the "deflate" value for each test case. [Output] Print "\#t" (without the quotes), leave a blank space and print the answer. (t refers to the test case number and starts with 1)