[백준] 20364번: 부동산 다툼

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

initial

I first thought maybe dfs until I saw n nodes could be up to 2^20 so making that graph for dfs traversal would already cause runtime.

Then I tried drawing this binary tree like you see in the image until I saw a relationship. The node multiplies by 2 for each child node so node 2 will have 4,5 and node 4 will have 8,9 and node 8 will have node16,17. So if we traverse from the bottom of the tree and if we have seen this parent node before, then we know this child node could not have been visited cuz the path is blocked from this parent to child node.

One mistake that i made is that if parent node 4 is blocked, i break out of loop with a flag but we need to return the ultimate parent- either 2 or 3. So instead of breaking, we continue until num>1.

Another mistake is that since i implemented in a dumb way where im changing the iter value of num itself, we need to set another variable as that number cuz we need to add the original number to our visited list or dictionary.

I optimised solution via using defaultdict(list) -> just normal dictionary -> visited list -> visited set(). But still it is at 800ms, though.

oh the ultimate contribution to making the time complexity much better is taking 1 input and performing your logic. My impl is taking all inputs in 1 for loop in a list and iterating each element but this guy took 1 element and performed logic on that 1 element. So he only iter once but i iter twice.

like this

for i in range(Q):
    k = int(sys.stdin.readline())
    sch(k)

solution

import sys
input=sys.stdin.readline

n, m = map(int, input().split())
lst = []

for _ in range(m):
    lst.append(int(input()))

visited=set()

for num in lst:
    result=0
    tmp=num
    while num>1:
        if num in visited:
            result=num
        num//=2
    visited.add(tmp)
    print(result)

complexity

oh so even though set operations are constant time, the while loop actually takes log n time. (cuz we are dividing it by 2 each time) And since we are iterating for n numbers it is n log n.

The time complexity of your code is (O(m \cdot \log n)), where (m) is the number of elements in lst and (n) is the maximum value in lst. The space complexity is (O(m)) due to the set visited.

Here's the breakdown:

1. Time Complexity:

   • The outer loop iterates over each element in lst, which has (m) elements.
   • The inner while loop has a time complexity of (\log n), where (n) is the maximum value in lst.
   • Therefore, the overall time complexity is (O(m \cdot \log n)).

2. Space Complexity:

   • The space complexity is dominated by the set visited, which stores unique elements from lst.
   • In the worst case, the set may store all (m) elements from lst.
   • Therefore, the space complexity is (O(m)).

The use of a set for visited is a good choice, as set membership tests have an average time complexity of (O(1)). This ensures efficient checking for visited elements during the loop. Overall, the code is reasonably efficient in terms of both time and space complexity.