# Tag Info

6

If the grader is complaining about "time limit exceeded," it must be because some loop is executing too many times. All of your functions are clearly O(1) — they have no loops. So which loop is executing too many times? It must be the only loop in the entire program: while(!isFull(n)){ cin>>a; push(a); } Is it possible that ...

4

There's a few general code hygiene things that I'll look at first, and then I'll comment on the algorithm design. First, const should mean constant. I know that in Javascript you don't get in trouble for changing the contents of a const array but it's still confusing to use it with a variable whose job is to change. const arr I like but const resultArray I ...

3

You can get an immediate speed-up by ditching the defaultdict(int), and using a bytearray(blockCount+1) instead. Both have roughly $O(1)$ lookup time, but the latter has a much smaller constant factor. In the former, each key must be hashed, then binned, then a linear search through the bin is required to find the correct key entry, if it exists, and ...

3

Needless for loop usage for loops in Python are heavy. Using for loops needlessly leads to performance loss. For instance, rather than doing this: for j in range(m): if mat[i[0]-1][j]=="0" and mat[i[1]-1][j]=="0": You could just count the number of ones using int(), bin() and | as below: orResult = int(mat[i[0] - 1], 2) | int(mat[j[0] - 1], 2) ...

2

Josiah's answer covers most stuff pretty well. The only additional suggestion I have is an alternative to a switch statement: a lookup table of actions. Something like: const query_types = { 1: (x)=>{ frequencyArray[arr[1]] = (frequencyArray[arr[1]] || 0) + 1; }, 2: (y)=>{ ... }, 3: (z)=>{ ... } }; for(let i=0 ;...

2

I don't have much time, and don't see any quick performance suggestions, but, mat = [] for i in range(n): mat.append(input()) Can be written more terse as a list comprehension: mat = [input() for _ in range(n)] And note how you never use i. If you don't use a variable, you can indicate that it isn't needed by calling it _. That's a placeholder ...

1

You chose to represent the “list of sequences” as a dictionary var sequences: [Int: [Int]] = [:] and here you test if a sequence for the given index already exists, and then either append a new element or create the initial sequence for that index: if var sequence = sequences[seq] { sequence.append(y) sequences[seq] = sequence } else { ...

1

So, the time complexity of the solution posted in the question is O(n^2 log(n)). Answering each query takes n log(n), and we have n queries in total. We don't necessarily need to merge the left and right subtrees to find the inversion count; given that the sublists are sorted, we can exploit binary search. import bisect from functools import lru_cache ...

1

Is there a way to improve the time complexity of this solution without exceeding the space limitation? Yes, there's a way. We don't actually need any additional array of numbers because we can check all numbers from 1 to the maximum possible mask for given elements of the array. Then, we will perform AND of the current number candidate with all array ...

Only top voted, non community-wiki answers of a minimum length are eligible