https://www.acmicpc.net/problem/1062
initial
referred to: https://velog.io/@cjkangme/%EB%B0%B1%EC%A4%80-1062.-%EA%B0%80%EB%A5%B4%EC%B9%A8-%ED%8C%8C%EC%9D%B4%EC%8D%AC
I think to convert basically anything to bit we just use this 1<<i formula. The general idea is that we convert the given words into bit form and the alphabets that include acint in bit form.
The alphabet logic is a bit hard but as we iter i in range(26), we 1<<i which means we make a bitmask where ith digit is 1. Then we compare this bitmask with base_bit and if it is not 1, that means it is an alphabet that is not acint cuz 0 & 1=0. If that condition is met, we append 1<<i to alphabet list.
We include acint cuz anta and tica are already known so we dont have to spend our k alphabets to reteach these ones. Then we compute the possible combinations by combinations(alphabet,k-5) and iter through each word in bit form and if all the bits in that word & combi ==1, that means all the alphabets match so we increment count.
Combination is in tuple of bitmasks like (1,4,5) which means a,d,e are selected. When we do sum on this tuple, it adds up the bitmasks in the tuple with the or operator.
initial wrong code:
from itertools import combinations
n, k = map(int, input().split())
lst = []
for _ in range(n):
lst.append(input()[4:-4])
alphabets = [chr(i) for i in range(ord('a'), ord('z') + 1)]
combi = combinations(alphabets, k)
ans = 0
for comb in combi:
count = 0
flag=False
for word in lst:
if flag:
break
for c in word:
if c not in comb:
flag=True
break
else:
print(comb)
count += 1
ans = max(ans, count)
print(ans)solution
from itertools import combinations
def word2bit(word):
bit = 0
for char in word:
bit |= 1 << (ord(char) - ord('a'))
return bit
n, m = map(int, input().split())
lst = [input().strip() for _ in range(n)] # Use strip() to remove leading/trailing whitespaces
bits = list(map(word2bit, lst))
if m < 5:
print(0)
exit()
base_bit = word2bit('acint')
alphabet = [1 << i for i in range(26) if not (base_bit & (1 << i))]
answer = 0
for comb in combinations(alphabet, m - 5):
know_bit = sum(comb) | base_bit # Use 'comb' directly instead of 'combination'
count = 0
for bit in bits:
if bit & know_bit == bit: # Check if bit is a subset of know_bit
count += 1
answer = max(answer, count)
print(answer)dfs backtracking way
https://oh2279.tistory.com/158
complexity
so rmb since it is bitmask and it iterates for 1<<i times, it is not n but it is 2^m-5
Let's analyze the time and space complexity of the provided code:
Time Complexity:
Reading Input: Reading the values of n and m takes constant time, so it doesn't contribute to the overall time complexity.
Creating Bitmasks: The loop that reads the input and creates bitmasks using the word2bit function has a time complexity of O(n k), where n is the number of words and k is the average length of a word.
Creating Alphabet: Generating the alphabet list has a time complexity of O(26) because it iterates over a constant number of elements.
Calculating Combinations: Generating combinations using combinations(alphabet, m - 5) has a time complexity of O(C(21, m - 5)), where C(n, k) is the binomial coefficient representing the number of ways to choose k elements from a set of n elements.
Checking Subsets: The nested loop that checks if a bitmask is a subset of know_bit has a time complexity of O(n 2^(m-5)), where n is the number of words and m is the length of the alphabet.
The overall time complexity is dominated by the generation of combinations and checking subsets.
Space Complexity:
Input Space: The bits list stores the bitmasks for each word, so the space complexity is O(n * k), where n is the number of words and k is the average length of a word.
Alphabet Space: The alphabet list stores the bitmasks for the alphabet, so the space complexity is O(26), which can be considered constant.
Combinations: The comb variable inside the combinations loop stores the bitmask for each combination, so the space complexity is O(m).
The overall space complexity is dominated by the input space.
In summary, the time complexity is influenced by the generation of combinations and checking subsets, while the space complexity is mainly determined by the storage of bitmasks for each word.
