Krishna and Containers

[hacker9876]

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.

  #include<bits/stdc++.h>

 using namespace std;
 int main()  
 {
long long n,m,i,con,l,r,t;
cin>>n>>m;
int a[n+1]={0};

while(m--)
{
    cin>>l>>r;
    for(i=l;i<=r;++i)
      a[i]++;
}

sort(a,a+n+1);

cin>>t;

while(t--)
{
    cin>>con;
    for(i=1;i<=n;++i)
    {
        if(a[i]>=con)
           break;
    }
    cout<<(n-i+1)<<'\n';
}
}

[Repeater]

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.

[hacker9876]

@Repeater
Then every time i need to traverse upto total "n" value which further leads to TLE

[Repeater]

Then every time i need to traverse upto total "n" value which further leads to TLE

Don't traverse. It's a waste of time.

[hacker9876]

Sorry, I couldn't get u can u explain me briefly

[Repeater]

A sorted container is easy to search. Binary search.

But better than that, don't traverse. You know how many chocolates are in each box. You put them there. Remember the values as you go.

Basically, your algorithm for solving this puzzle is too slow. You need to think about better ways to do it.

[hacker9876]

Binary search works only when array is in sorted form

[Repeater]

Binary search works only when array is in sorted form

It is sorted. Didn't you notice yourself writing sort(a,a+n+1); into the code? Or is this someone else's code and you didn't notice it was sorted?

[ne555]

@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


@op

while(m--)
{
    cin>>l>>r;
    for(i=l;i<=r;++i)
      a[i]++;
}

suppose that all the ranges are [1; N], you'll end up traversing the entire array `m' times
that's too much

you need to think on another way to keep track of the chocolates

[Repeater]

@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.

Clear enough now? Hope so.

[jonnin]

Goodness lol.

- 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.

[ne555]

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

1	6-1+1 = 6
2	3-1+1 + 5-5+1 = 3+1 = 4
3	2-2+1 = 1
4	0

also notice that you are doing M operations, so there can't be any box with more than M chocolates.

[jonnin]

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>
 using namespace std;
 int main()  
 {
long long 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.

[jonnin]

with the summation for loop optimized out:

 int main()  
 {
long long 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;
}

[ne555]

 while(m--)
{	
    for(i=lx[dx];i<=rx[dx];++i)
      a[i]++;
    dx++;
}

for the third time, stop doing that, it's expensive. O(n*m)

[jonnin]

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]

If anyone has any query regarding this question pm me I have done help u in clearing doubts of this..

[shubhum]

@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

[ghostrideriit]

@shubhum

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

[287LhbRD]

@ghostrideriit
Its still giving tle