I am getting time limit exceeded for the following problem.Can anyone optimize my code. Is it because of sorting i am getting TLE or is there any other reason
Statement:
Krish loves chocolates very much. He has N containers numbered from 1 to N.Everyday, he used to select two indices [l,r] and adds 1 chocolate to each box starting from l to r (both inclusive).He repeats the same activity for M days.
After M days, he asked his friend Nakshatra Q queries. Each query can be described as: How many containers have atleast K chocolates.
Help Nakshatra to answer these queries.
Constraints:
1 <= N <= 100000
1 <= M <= 1000
1 <= l <= r <= N
1 <= Q <= 100000
1 <= K <= N
Input:
7
4
1 3
2 5
1 2
5 6
4
1
7
4
2
Output:
6
0
0
4
Input Format:
First line contains an integer N that denotes the number of containers.
Second line contains an integer M denoting the number of days.
Each of the next M lines consists of two space separated integers l and r.
Followed by an integer Q denoting the number of queries.
Each of next Q lines contain a single integer K.
Sorting does seem like a waste of time. You know how many chocolates are in every box because your code put them there. Keep track of those numbers as you go and you can answer the queries directly instead of having to do a sort and then having to traverse the sorted array.
While I'm here, this: int a[n+1]={0};
is illegal in C++. You're not allowed variable sized arrays on the stack.
@Repeater: you said «Sorting does seem like a waste of time. (...) you can answer the queries directly instead of having to do a sort»
and then go talking about binary search
you are not explaining yourself
@Repeater: you said «Sorting does seem like a waste of time. (...) you can answer the queries directly instead of having to do a sort»
and then go talking about binary search
you are not explaining yourself
I'll be clearer.
Sorting is a waste of time.
If you insist on sorting, then searching the sorted array with a binary search will be faster than simply traversing it.
- What you are doing is akin to having a few jars and a sack of rocks. You can put, say, 5 rocks in the first jar, 10 rocks in the second jar, and 4 rocks in the third jar.
Now I can ask you how many rocks are in the second jar. You have 2 choices.
you can tell me 10, because you wrote it down, or you can count them. Then I can ask you again how many are in jar 2, and you can count them again, or you can tell me, and a third time, .... at some point, you are spending a lot of time counting rocks if you do it that way.
That is what you are doing here, effectively. Searching and sorting aside, all that is a waste of time. Just track how many are in each bucket, and report that upon demand.
That is what he was trying to say. Sorting and searching are expensive things to be avoided as much as possible, even when they solve the problem, there is often a better way that avoids all that extra work. Here, its a really easy way to avoid the extra work -- count what you add to a bucket. What we are saying then is that while sort & search works, its a terrible way to solve the problem, so don't do that.
it seems that you don't understand the problem or the code
the array `a' does keep track of how many chocolates are in each box
but the question is «How many boxes have at least K chocolates»
that's what being counted, and what could be avoided with a upper_bound search
the reason for the time limit exceed is because that tracking is too expensive, O(nm)
@OP:
if you work on the range [l; r], then you are working on r-l+1 boxes
consider your input example and look at your array
2 3 2 1 2 1 0
wich you may represent as
1 [ [
2 . . []
3 . ]
4 .
5 . []
6 ]
7
now to answer the query you go to the K column and compute the range of the []
so
Maybe I don't get it. Sometimes I can be a little thick.
Is this remotely akin to what you are trying to do?
edit: mostly fixed. variable names messed me up first try. I put the test values in so it can just run. I did not try to optimize it, there is a lot that could be done once all the constants have been put back to variables.
#include<bits/stdc++.h>
usingnamespace std;
int main()
{
longlong n,m,i,con,l,r,t;
//cin>>n>>m;
n = 7; m = 4;
int a[8]={0}; //8 is n+1
int lx[] = {1,2,1,5};
int rx[] = {3,5,2,6};
int tx[] = {1,7,4,2};
int dx = 0;
while(m--)
{
//cin>>l>>r;
for(i=lx[dx];i<=rx[dx];++i)
a[i]++;
dx++;
}
//sort(a,a+n+1);
int mc[1001] = {0}; //count how many buckets have each value.
for(int z = 0; z < n+1; z++) //that is if 3 buckets have 5 in them, [5] = 3.
mc[a[z]]++;
for(dx = 0; dx < 4; dx++) //this is the '4' input for # of queries.
{
t = tx[dx];
int result = 0;
for(int g = t; g <8; g++) //8 is n+1 as above
result += mc[g]; //add up buckets that have t or more.
cout << result << endl;
}
return 0;
}
I ran out of steam last night. After this, you can eliminate the for loop to sum them as well. Ill do that over lunch break or something.
int main()
{
longlong n,m,i,con,l,r,t;
//cin>>n>>m;
n = 7; m = 4;
int a[8]={0}; //8 is n+1
int lx[] = {1,2,1,5};
int rx[] = {3,5,2,6};
int tx[] = {1,7,4,2};
int dx = 0;
while(m--)
{
//cin>>l>>r;
for(i=lx[dx];i<=rx[dx];++i)
a[i]++;
dx++;
}
//sort(a,a+n+1);
int mc[1001] = {0}; //count how many buckets have each value.
for(int z = 0; z < n+1; z++) //that is if 3 buckets have 5 in them, [5] = 3.
mc[a[z]]++;
int rt = 0;
for(int z = 8; z >=0; z--)
{
rt += mc[z];
mc[z] = rt;
}
for(dx = 0; dx < 4; dx++) //this is the '4' input for # of queries.
{
t = tx[dx];
int result = 0;
//for(int g = t; g <8; g++) //8 is n+1 as above
// result += mc[g]; //add up buckets that have t or more.
//cout << result << endl;
cout << mc[t] << endl;
}
return 0;
}
Yea i didnt fool with that segment. You can probably (not 100% sure) rewrite what I did to do it all at once rather than 2-passes to collapse it as well. Hes got a lot to do to convert what we said to something to submit, but mine shows what I was trying to say for those segments.
@ghostrideriit
i have made the python dictionary for the queries . suppose 1 3 2 5
then it will add the count first from 1 to 3 with their keys 1 to 3 similarly for 2 to 5.
then after that i wiil query by their counts present in the dictionary for their various keys.
what is worng in that .
i am getting time limit exceed
u have to found all digits greater than k. so just check in array after sort that u get k and break from there becoz rest elements willl be greater than that element must be greater than k this will remove tle