TLE in CHEFNUMK COOK77

help
,
1

Can anyone help me to fix Tle in this code for the above problem. link . I used BIT and square root decomposition

2

problem is map:-)

unordered_map insertion takes constant time but map insertion takes logarithmic time.
also input methods should be faster use fast-io.
this is my TLE solution link:-https://www.codechef.com/viewsolution/12299117

i just switched to fast-io and unordered_map got ac:-
https://www.codechef.com/viewsolution/12299416

1 Like
3

Thanks but I think there is some other problem. Can you comment on the complexity of ur code during the query part if all integers are distinct and K=N and queries are balanced. Wont completely iterating over map everytime cause tle…though my approach is a bit different

4

I m not familiar with your approach!!!

It doesnt matter if k==n in my approach because i m counting for every query the map’s value.

Time Complexity:- O(n*sqrt(n)):- for MO’s algorithm

O(1) :- for insertion i.e every new element encountered(because it is unordered_map)

O(n) for counting numbers that are greater than k…

5

Btw ur complexity of the code is O(P^2) where P is the total number of distinct numbers in the array and K is very large. anyways waiting for some one to help

6

I have tried same approach during the contest as yours. I also got TLE. The reason I got to know is because of extra log(N) factor. This log(N) is due to two things , one because of map and other because of Fenwick Tree (BIT). This map factor can be reduced to some sense by using unordered_map but factor introduced by BIT can not be decreased.

Solution : Now how to reduce the factor of BIT. Instead of BIT just use brute force approach of prefix sum array. Here prefixSum[i] = sum[i] + sum[i+1] + … + sum[N] .

So add method of our MO’s will be as follows :

void add(int x)
   int count =  map[x];
   decrease 1 in prefix Sum array from index i = 1 to count
   increase 1 in prefix Sum array from index i = 1 to (count + 1)
   map[x]++

However just notice decrease and increase lines just merges and reduces to following code :

void add(int x)
       int count =  map[x];
       prefixSum[count+1]++;
       map[x]++

Similarly for remove(x).

Thus log(N) factor of BIT is removed.

The map log(N) factor can be more better reduced by using co-ordinate compression.

So the reason why our earlier implementation was giving TLE because of extra log(N) factor induced by BIT.

1 Like