You are viewing a single comment's thread. Return to all comments →
why is this solution giving TLE, even though its time complexity is O(2**K N log N) as given in the editorial.
def candlesCounting(k, candles): full_mask = 2**k bit = [[0]*(full_mask) for _ in range(50001)] # fenwick tree storing the number of subsequences with height of last candle in the subsequence equal to the index, also stores the information of colors contained in those sequence. ans = 0 for i in range(len(candles)): h,c = candles[i] hh = h-1 res = [0]*(full_mask) # res[i] stores the number of subsequences with height of last candle equalt to hh, along with the info of colors contained in such subsequences of candles. while hh > 0: # this is prefix sum query res = [res[j]+bit[hh][j] for j in range(full_mask)] hh -= (hh & (-hh)) new_res = [0]*(full_mask) new_res[(1 << (c-1))] = 1 for j in range(full_mask): # obtaining the subsequences number ending at the index ith candle new_res[j | (1 << (c-1))] += res[j] ans += new_res[-1] while h < 50001: # updating fenwick tree bit[h] = [bit[h][j]+new_res[j] for j in range(full_mask)] h += (h & (-h)) return ans%(1000000007)
Seems like cookies are disabled on this browser, please enable them to open this website
Candles Counting
You are viewing a single comment's thread. Return to all comments →
why is this solution giving TLE, even though its time complexity is O(2**K N log N) as given in the editorial.