https://www.acmicpc.net/problem/14888
initial
So immediately i knew it was a backtracking question where the operations of add,sub,mul,div are to be traversed via dfs. But I really need to revise cuz I couldnt implement it. I tried making a string path where all operations are appended like ‘++-x/’ and iterated for each index and doing operation with the previous and current number. But i wanst sure how to “undo the changes” as required by backtracking.
I googled a solution and btw i didnt even make the recursive end condition, which means my dfs function would loop endlessly. The end condition should be that when index reaches n, we mark the maxAns and minAns and return, which ends the loop and backtracks.
We are gonna add those 4 operations and how many there are in our dfs function. If for erxample add>0, we add lst[index] to current value and decrement add. We then dfs on this like (index+1,val). Once we backtrack, we have to increment back the subtracted add. BTW we dont need to explicitly revert back the value because when we backtrack, the call stack would preserve the state of the value.
What i mean is if we do
Val += lst[index]
dfs(val)
We HAVE to revert back the change that we did to val like
Val -= lst[index]
But if we just pass the change as parameter like
//no val +=lst[index]
dfs(val+lst[index])
Then when we come back by backtracking, technically val isnt changed cuz we have just passed val+lst[index] as parameter. So we dont have to revert back the changes.
Oh btw for division we have to do int(val/lst[index]) and not just val//lst[index]. While both gives same results for positive numbers, for negative numbers the former rounds towards 0 whereas latter rounds towards negative infinity.
solution
import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
maxAns = float('-inf')
minAns = float('inf')
def dfs(index, val):
global maxAns, minAns, add, sub, mul, div # Declare variables as global
if index == n:
maxAns = max(val, maxAns)
minAns = min(val, minAns)
return
if add > 0:
add -= 1
dfs(index + 1, val + lst[index])
add += 1
if sub > 0:
sub -= 1
dfs(index + 1, val - lst[index])
sub += 1
if mul > 0:
mul -= 1
dfs(index + 1, val * lst[index])
mul += 1
if div > 0:
div -= 1
dfs(index + 1, int(val / lst[index]))
div += 1
dfs(1, lst[0])
print(maxAns)
print(minAns)complexity
The time complexity of the provided code is O(4^n), where n is the number of elements in the list lst. This is because, for each element in the list, the algorithm explores four possibilities (addition, subtraction, multiplication, and division), and the recursion depth can go up to the number of elements in the list.
The space complexity is O(n), where n is the recursion depth. This is because the recursion depth is determined by the number of elements in the list. Each recursive call consumes space on the call stack, and the space required is proportional to the recursion depth.
In summary:
Time complexity: O(4^n)
Space complexity: O(n)
The time complexity is exponential due to the four recursive calls for each element in the list, leading to a combinatorial explosion of possibilities. If the size of the input list is large, the algorithm may take a considerable amount of time to run.
