chonq
Chef went to the store and saw a long queue. There are N people in the queue (numbered 1 through N from the front of the queue to the back); as it usually happens in such a situation, each person has a certain anger level. Let's denote the anger level of the i-th person by ai.
Chef wants to finish shopping as fast as possible, so he decided to try jumping the queue instead of just standing at its back. However, he cannot make the people already standing in the queue much angrier, since that would not end well for him. Chef may stand in the queue directly in front of person p only if the expression
⌊ap1⌋+⌊ap+12⌋+⌊ap+23⌋+…+⌊aNN−p+1⌋
does not exceed a given integer K. Here, ⌊x⌋ denotes the floor function - the largest integer which does not exceed x.
When Chef joins the queue, his position in the queue is the number of the person directly behind him, or N+1 if he stands at the back of the queue. Find the minimum position at which Chef should join the queue, either by cutting in front of someone or (if it is impossible to cut in front of anyone without violating the condition above) standing at the back of the queue.
Chef wants to finish shopping as fast as possible, so he decided to try jumping the queue instead of just standing at its back. However, he cannot make the people already standing in the queue much angrier, since that would not end well for him. Chef may stand in the queue directly in front of person p only if the expression
⌊ap1⌋+⌊ap+12⌋+⌊ap+23⌋+…+⌊aNN−p+1⌋
does not exceed a given integer K. Here, ⌊x⌋ denotes the floor function - the largest integer which does not exceed x.
When Chef joins the queue, his position in the queue is the number of the person directly behind him, or N+1 if he stands at the back of the queue. Find the minimum position at which Chef should join the queue, either by cutting in front of someone or (if it is impossible to cut in front of anyone without violating the condition above) standing at the back of the queue.
Can you solve it un-optimally?
Can you solve it for simple cases, like say when n=1 or n=2 ?
Can you solve it at all?
Remember, we're not a problem analysis and code writing service.
Can you solve it for simple cases, like say when n=1 or n=2 ?
Can you solve it at all?
Remember, we're not a problem analysis and code writing service.
of course for simple test cases just brute force,but i am getting TLE for other cases.
Any hints?
Any hints?
Yes, post your code so we can see what your approach is, and perhaps offer alternatives.
If someone wants to get better on programing he must do alone problems .There is a little or no point in just using other peoples code without understanding the task.If someone encounters some problems while coding he can put his code and ask the questions about the problems he have.But I do not believe people will start doing other peoples assignments without their will to even try to do a problem.The best way to improve yourself is hard-work , dedication and trying to do problems alone.
long long n,k;
cin>>n>>k;
vector<long long>arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=0;i<n;i++)
{
long long c=0,d=1;
for(int j=i;j<n;j++)
{
c+=(arr[j])/d;
d++;
if(c>k)break;
}
if(c<=k){
cout<<i+1<<"\n";
exit();
}
cout<<n+1;
}
//needs optimization
cin>>n>>k;
vector<long long>arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=0;i<n;i++)
{
long long c=0,d=1;
for(int j=i;j<n;j++)
{
c+=(arr[j])/d;
d++;
if(c>k)break;
}
if(c<=k){
cout<<i+1<<"\n";
exit();
}
cout<<n+1;
}
//needs optimization
Last edited on
Needs code tags.
> //needs optimization
It needs a better algorithm, not minor tweaks to what you have.
Here's a practical exercise in problem solving.
Write out 10 "anger levels" on 10 bits of paper, then arrange them in a queue.
On an 11th bit of paper, write "chef".
Now you're chef, so look at your queue in front of you and figure out the best way to insert chef into the queue.
"Work smarter, not harder!".
I'll tell you my approach when you've had chance to think about it for a while.
|
|
> //needs optimization
It needs a better algorithm, not minor tweaks to what you have.
Here's a practical exercise in problem solving.
Write out 10 "anger levels" on 10 bits of paper, then arrange them in a queue.
On an 11th bit of paper, write "chef".
Now you're chef, so look at your queue in front of you and figure out the best way to insert chef into the queue.
"Work smarter, not harder!".
I'll tell you my approach when you've had chance to think about it for a while.
Yeah I have also tried binsearch but the non-monotonicity of the function didn't help.
The exercise you told to do gave idea of storing some kind of prefixes in memory,but that would also give TLE.
No transition between states so no dp .
What is the time complexity of your approach?
The exercise you told to do gave idea of storing some kind of prefixes in memory,but that would also give TLE.
No transition between states so no dp .
What is the time complexity of your approach?
Usually codechef problems are more about math than they are about programming. Look at the problem and see if you can come up with a faster way to solve it. I confess that I haven't thought of anything too promising but here are some ideas:
Is there a fast way to determine the wait time at position p if you already know the wait time at position p+1 or p-1? I couldn't think of any.
Can you manipulate the wait time algebraically into something that's easier to compute? You could clear the fractions by multiplying each term by N! but what does that get you?
Can you do a binary search somehow?
Can you put an upper and/or lower bound on the wait time at position p? That might let you rule out some positions.
You compute the wait times from the beginning of the line. Would it help to compute them from the end instead? Or, since the person closest to you contributes the most anger, start by cutting in front of the person with the least anger level.
Once you find any position that results in a total anger level < K, you don't have to check any higher position. So maybe a sort of binary search can work. Start at the middle and work towards the front of the line until you find a position that works. If you find none then check the other half of the line. But if you DO find a position, then you've narrowed the remaining search space.
Good luck.
Dave
Is there a fast way to determine the wait time at position p if you already know the wait time at position p+1 or p-1? I couldn't think of any.
Can you manipulate the wait time algebraically into something that's easier to compute? You could clear the fractions by multiplying each term by N! but what does that get you?
Can you do a binary search somehow?
Can you put an upper and/or lower bound on the wait time at position p? That might let you rule out some positions.
You compute the wait times from the beginning of the line. Would it help to compute them from the end instead? Or, since the person closest to you contributes the most anger, start by cutting in front of the person with the least anger level.
Once you find any position that results in a total anger level < K, you don't have to check any higher position. So maybe a sort of binary search can work. Start at the middle and work towards the front of the line until you find a position that works. If you find none then check the other half of the line. But if you DO find a position, then you've narrowed the remaining search space.
Good luck.
Dave
Let assume you put anger levels in array ,but first element in array is anger of the last person,second element in array is anger of person N-1 and so on.Now you can make a function that calculates anger from a position you have passe to the end.You place chef on the N+1 position.Now in a while loop you are decreasing chefs position in queue while K(number user has inputed is greater than sum of anger of other people that are behind.You can try something like this.
Topic archived. No new replies allowed.