[백준] 2529번: 부등호

https://www.acmicpc.net/problem/2529

initial

my initial code doesnt print leading 0s and are wrong for most test cases and is extremely slow. (explained below)

initial:

n = int(input())
moves = list(input().rstrip())
lst = [i for i in range(10)]
visited = [False for _ in range(len(lst))]
max_tot = -1
min_tot = 100
ans = []

def dfs(tmp):
    global max_tot, min_tot, ans
    if len(tmp) == n + 1:
        flag = False
        left = tmp[0]
        for i in range(1, n + 1):
            bracket = moves[i - 1]
            right = tmp[i]
            if bracket == '<':
                if left < right:
                    left = right
                else:
                    flag = True
                    break
            else:
                if left > right:
                    left = right
                else:
                    flag = True
                    break
        if not flag:
            val = ''.join(map(str, tmp))
            ans.append(int(val))

    for i in range(len(lst)):
        if not visited[i]:
            tmp.append(lst[i])
            visited[i] = True
            dfs(tmp)
            tmp.pop()
            visited[i] = False

dfs([])
ans.sort()

print(ans[-1])
print(ans[0])

tried fixing my initial code

but my code is extremely slow This is cuz I am generating all possibilities of permutations from 0 to 9, which is (10!). And for each permutatiaon im checking with o(n) condition, which makes total time n*10!. Not to mention that sort, which will take 10! more lol

and is wrong for
4
< > > <
89765
04321

but the correct ans should be

89756
03214

[Fixed] so
1) my code for taking the string input was wrong that made me skip the last bracket in that list. What I did wrongly was moves = list(input().rstrip()) but the correct code is moves = list(input().split()). But still the time complexity is really bad like im generating all permutations and even though I think i was doing backtracking but it isnt.

2) when I debugged, when we meet this if len(tmp) == n + 1: condition, whatever the result was I should return to the previous dfs stack. However, I didnt place a return statement after checking condition. So it proceded to that for i in range(len(lst)): statement

So i fixed those 2 and my code works but is 4964ms holy moly

n = int(input())
moves = list(input().split())
lst = [i for i in range(10)]
visited = [False for _ in range(len(lst))]
max_tot = -1
min_tot = 100
ans = []

def dfs(tmp):
    global max_tot, min_tot, ans
    if len(tmp) == n + 1:
        flag = False
        left = tmp[0]
        for i in range(1, n + 1):
            bracket = moves[i - 1]
            right = tmp[i]
            if bracket == '<':
                if left < right:
                    left = right
                else:
                    flag = True
                    break
            else:
                if left > right:
                    left = right
                else:
                    flag = True
                    break
        if not flag:
            val = ''.join(map(str, tmp))
            ans.append(int(val))
            return
        else:
            return

    for i in range(len(lst)):
        if not visited[i]:
            tmp.append(lst[i])
            visited[i] = True
            dfs(tmp)
            tmp.pop()
            visited[i] = False

dfs([])
ans.sort()
changed=''
val=ans[0]
if len(str(val))<n+1:
    changed = '0'*(n+1-len(str(val))) + str(val)
else:
    changed = ans[0]


print(ans[-1])
# print(ans[0])
print(changed)

solution (vv.impt)

Instead of generating all permutations (cuz my method blindly adds numbers from 0 to 9 until my tmp list's length meets n+1), what if we add number and do dfs on itonly when current iterating bracket condition is met or when i=0 (i=0 cuz we have to add '0' when there is only 1 number as u need 2 numbers to compare with bracket)

We can create a check condition that takes 2 numbers and current bracket as parameters and if they are compared and makes sense (i.e. True), only then we add that to our tmp string (not list this time cuz you need value 0 and list will get rid of 0 when you turn it into int) and do dfs on it.

also the min_ans doesnt have to be checked each time with min() cuz since i is iterated from 0 to 9, the first valid ans is guaranteed to be the smallest

tbc the solution

n = int(input())
brackets = list(map(str,input().split()))
visited= [False for _ in range(10)]
min_ans=''
max_ans=''
def check(i,j,h):
    if h=='<':
        return i<j
    else:
        return i>j

def dfs(idx,hola):
    global min_ans,max_ans
    if idx==n+1:
        if len(min_ans)==0:
            # since we are iterating from 0 to 9 sequentially the first string that meets the condition is garanteed the smallest
            min_ans=hola
        else:
            max_ans=hola
        return

    for i in range(10):
        if not visited[i]:
            if idx==0 or check(hola[-1],str(i),brackets[idx-1]):
                # if i do hola+=str(i), I need to slice it for backtracking or else it will accumulate
                hola+=str(i)
                visited[i]=True
                dfs(idx+1,hola)
                hola=hola[:-1]
                visited[i]=False
dfs(0,'')
print(max_ans)
print(min_ans)

very useful and good trick

as you can see when we append str(i) to our hola string once that check condition is True, we have to pop (or should I say slice for string cuz there is no pop method for string) the last element when dfs backtracking is finished.

OR, you can actually do

 solve(idx+1,hola+str(i))

this way we are not changing the value of string hola in the local scope but just passing that updated value in the deeper dfs calls. So when you backtrack to the current dfs call, the hola string is the same. VERY USEFUL

revisited jan 17th

Very well written, though I still would have solved the initial way that I did months ago.

So rmb we need to return once we reach the recur end condition and that useful tip is really useful - either change the variables and undo the changes after DFS OR just pass the variables as parameters to the dfs

btw even though we place 0 at i=0 by default, if it doesnt meet the dfs if check condition, it will exhaust all i iterations before going back to previous dfs call stack, slicing that value 0 and placing value at the front instead with the next i for loop.

also v impt to see that the first iteration will give a valid min string answer while the last tieration will give a valid max string ans.

revisited june 14th

dam retry again

complexity

Let's analyze the time and space complexity of the provided code:

Time Complexity:

1. DFS Function (dfs):

   • The dfs function is a recursive function that explores all possible combinations of digits to create valid numbers based on the inequalities.
   • The function is called with idx ranging from 0 to n inclusive, which indicates the current position in the inequalities list.
   • For each position, it iterates through the digits from 0 to 9, checks if they can be added to the current number (hola) based on the inequalities, and proceeds to the next position.
   • In the worst case, it explores all possible combinations of digits, so the time complexity of the dfs function is O(10^n), where n is the number of inequalities.

2. Result Output:

   • After the backtracking process is complete, the code prints the maximum and minimum valid numbers, which takes constant time.

The overall time complexity of the code is dominated by the dfs function and is O(10^n) in the worst case.

Space Complexity:

1. visited List:

   • The visited list is used to keep track of whether each digit (0 to 9) has been visited. It requires O(10) space, which is constant.

2. Function Call Stack:

   • The space used by the function call stack during the recursive calls depends on the depth of the recursion, which is at most n + 1. Each recursive call adds a new frame to the stack, and the space used for each frame includes the idx and hola variables. Therefore, the space complexity related to the call stack is O(n).

3. Other Variables:

   • Variables like min_ans, max_ans, and the loop variables require a constant amount of space.

The overall space complexity of the code is O(n) due to the function call stack and constant space for other variables.

In summary, the time complexity is exponential, O(10^n), and the space complexity is linear, O(n). The code explores a large search space, making it less efficient for a large number of inequalities (n).