https://www.acmicpc.net/problem/16987
initial
i have been trying to solve like a human and getting list idnex out of range
n = int(input())
lst = [list(map(int,input().split())) for _ in range(n)]
ans = -int(10e9)
def dfs(index,hard,weight,count):
global ans
if index>=n-1:
ans = max(ans,count)
return
for i in range(index,n):
hard-=lst[i+1][1]
lst[i+1][0]-=weight
if hard>0 and lst[i+1][0]<0:
count+=1
dfs(index+1,hard,weight,count)
count-=1
hard+=lst[i+1][1]
lst[i+1][0]+=weight
elif hard<0 and lst[i+1][0]>0:
count+=1
dfs(index+1,lst[i+1][0],lst[i+1][1],count)
count-=1
hard+=lst[i+1][1]
lst[i+1][0]+=weight
elif hard<0 and lst[i+1][0]<0:
count+=2
if index+2>=n:
ans = max(ans,count)
count-=2
hard+=lst[i+1][1]
lst[i+1][0]+=weight
else:
dfs(index+2,lst[i+2][0],lst[i+2][1],count)
count-=2
hard+=lst[i+1][1]
lst[i+1][0]+=weight
# if no eggs cracked
else:
dfs(index+1,lst[i+1][0],lst[i+1][1],count)
hard+=lst[i+1][1]
lst[i+1][0]+=weight
dfs(0,lst[0][0],lst[0][1],0)
print(ans)
solution
We can pass 2 parameters to dfs backtracking function - list of eggs and sequence. Sequence would be the index of the egg which we are holding right now and about to hit with another egg (that is gonna be iterated in a for loop). In that for loop, we don't want to hit with itself so if i==seq, continue. If the egg already is cracked (i.e. i[0]<=0, continue) continue also. Only then we do dfs backtracking on eggs on i index and seq index.
To end our recursion, if seq is equal to n (we are index out of range), we count how many eggs have been cracked before returning.
(need revisit i dont fully get it)
ONE PART I FOUND IT TRICKY was this part:
If the rest of the eggs, besides the one we are holding now, are all cracked, we can count the eggs and return. But this logic can happen before our main logic of dfs backtracking.
check = True
for i in range(N):
if sequence == i: continue
if eggs[i][0] > 0: check = False
if check:
countCrackedEggs(eggs)
returnTake
3
1 100
8 5
3 5
for example. our if seq==n: recursion end logic will never reach because any pair of eggs will crack each other open. So we will not go beyond our length of the list and count our cracked eggs. So in this kind of cases, we need to check and count this edge case.
correct:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
lst = [list(map(int,input().split())) for _ in range(n)]
ans = 0
def count_eggs(lst):
global ans
count=0
for i in lst:
if i[0]<=0:
count+=1
ans=max(ans,count)
def dfs(seq,lst):
global ans
if seq==n:
count_eggs(lst)
return
if lst[seq][0]<=0:
dfs(seq+1,lst)
return
check = True
for i in range(n):
if seq==i:
continue
if lst[i][0]>0:
check=False
break
if check:
count_eggs(lst)
return
for i in range(n):
if i==seq:
continue
if lst[i][0]<=0:
continue
lst[seq][0] -= lst[i][1]
lst[i][0] -= lst[seq][1]
dfs(seq+1,lst)
lst[seq][0] += lst[i][1]
lst[i][0] += lst[seq][1]
dfs(0,lst)
print(ans)better
here the index and the count of cracked eggs is put as paramter.
def backtrack(cur, cnt):
if cur == N:
global max_cnt
if cnt > max_cnt: max_cnt = cnt
return
if S[cur] <= 0 or cnt == N - 1:
backtrack(cur + 1, cnt)
return
for i in range(N):
if i == cur or S[i] <= 0:
continue
# update s, w
S[cur] -= W[i]
S[i] -= W[cur]
if S[cur] <= 0: cnt += 1
if S[i] <= 0: cnt += 1
backtrack(cur + 1, cnt)
# restore s, w
if S[cur] <= 0: cnt -= 1
if S[i] <= 0: cnt -= 1
S[cur] += W[i]
S[i] += W[cur]
N = int(input())
S = []
W = []
max_cnt = 0
for _ in range(N):
s, w = map(int, input().split())
S.append(s)
W.append(w)
backtrack(0, 0)
print(max_cnt)complexity
The time and space complexity of the given code is exponential, specifically O(2^n). This is because the code uses a depth-first search (DFS) approach to explore all possible combinations of eggs being broken or not. For each egg, there are two choices: either break it or leave it intact. As a result, the number of recursive calls grows exponentially with the number of eggs (n).
The space complexity is also influenced by the recursion stack, which can grow significantly for large values of n. Each recursive call creates a new context with its own local variables, contributing to the overall space complexity.
It's worth noting that this code could be highly inefficient for large values of n, as the number of recursive calls and computations increases exponentially, making it impractical for large input sizes. There may be more efficient algorithms to solve this problem.
