https://www.acmicpc.net/problem/14888
initial
After some thinking, I could tell this was a dfs + backtracking question. But I wasnt sure how to implement the dfs, especially backtracking part.
so I tried using permutations to create every possible pair and iterate through numbers list and calculating each pair on it like this
from itertools import combinations, permutations
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
import math
n=int(input())
num = list(map(int,input().split()))
op = list(map(int,input().split()))
check = ['+','-','x', '/']
ready = []
for i in range(len(op)):
for j in range(op[i]):
ready.append(check[i])
min_tot = int(10e9)
max_tot = -int(10e9)
for pair in list(permutations(ready,n-1)):
tmp=num[0]
for i in range(1,n):
# tmp=num[i-1]
op=pair[i-1]
if op=='+':
tmp += num[i]
elif op=='-':
tmp-=num[i]
elif op=='x':
tmp*=num[i]
else:
tmp = int(tmp/num[i])
min_tot=min(tmp,min_tot)
max_tot=max(tmp,max_tot)
print(max_tot)
print(min_tot)but this gave runtime error so I had to rethink (or should I say google) for dfs + backtrack
solution
Just before this q, I implemented dfs backtracking (which should have been dfs + dp but anyway)
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-1563%EB%B2%88-%EA%B0%9C%EA%B7%BC%EC%83%81
and I saw that the solution above ^ places parameters in that dfs, which are gonna be used in checking the valid conditions - whether to break out of that recursive loop or not. So let's practice on this q.
rmb we want to put useful parameters, which are gonna be used to check the validity of condition.
parameters for dfs
1) to end our recursion, we need depth parameter and if that is ==n, we check our accumulated value and update min and max value accordingly
2) as mentioned in 1, we need an accumulated value parameter
3) We can put the number of operators (+,-,x,%) in our parameter. I couldnt think of this way. If there are more operators left than n, we dfs on that same operator until either depth reaches n or that number of operator reaches 0 (cuz we subtract each time we go deeper into dfs). If depth==n, we update min,max values and backtrack by return. If number of operators reach 0, we go to the next operator count.
n=int(input())
num = list(map(int,input().split()))
op = list(map(int,input().split()))
min_tot = int(10e9)
max_tot = -int(10e9)
def dfs(depth,plus,minus,mul,div,total):
global min_tot, max_tot
if depth==n:
min_tot=min(min_tot,total)
max_tot=max(max_tot,total)
return
if plus:
dfs(depth+1,plus-1,minus,mul,div,total+num[depth])
if minus:
dfs(depth+1,plus,minus-1,mul,div,total-num[depth])
if mul:
dfs(depth+1,plus,minus,mul-1,div,total*num[depth])
if div:
dfs(depth+1,plus,minus,mul,div-1,int(total/num[depth]))
dfs(1,op[0],op[1],op[2],op[3],num[0])
print(max_tot)
print(min_tot)care diff between // and int(x1/x2)
while both produces same result for + integers, it is diff for negative values. // rounds down (floor division) so -7//3 is -3. But int(x1/x2) first calculate float point of -2.333 and truncates up towards 0. So it is -2.
the question asked for latter so follow that.
revisited 13th jan
I retried it like https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-14888%EB%B2%88-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0
revisited june 25th
putting useful parameters for dfs like so is the key to this problem, which I thought of doing but kind failed. I remember there was a similar problem where you just make the whole thing to a string and use eval() but this question wants the operation in sequence from left to right, not prioirtising the * and /. So cant use eval but put the number of operators and depth level in the parameters.
complexity
The time complexity of this code can be analyzed based on the number of recursive function calls. In the worst case, it explores all possible combinations of operations for the given input, which results in an exponential time complexity. Specifically, the code makes O(4^n) recursive calls, where n is the number of input numbers. This is because for each number, there are four choices (addition, subtraction, multiplication, and division), and the code explores all combinations.
The space complexity is determined by the depth of the recursive call stack. In the worst case, the depth of the recursive call stack can be up to n (equal to the number of input numbers). Therefore, the space complexity is O(n).
It's important to note that this code may not be efficient for a large number of input values, as it explores an exponential number of possibilities. Depending on the problem size, it may result in a significant runtime and memory usage.
