Problem Link: CodeChef: Practical coding for everyone
How to solve this?
Thanks in advance!
Yep I too have same question, just waiting for the editorial. I am getting TLE by using python, can anyone please help on this problem.
for _ in range(int(input())):
n,q = map(int,input().split())
p = list(map(int,input().split()))
p.sort()
for _ in range(q):
c = 0
x = int(input())
for i in p:
if x>i:
c += 1
x = 2*(x-i)
print(c)During the contest, I could realise one thing that this can be solved using Binary Search but I wasn’t able to formulate it. So, after the contest I read the accepted submissions and here is what the approach is-
- Use Binary Search to find the smallest possible power that can kill all the monsters.
- Let the above power be x, then find the monsters that can be killed using this power - 1, i.e. x - 1, simply do a naive linear search over the array for this.
- Now, for answering each query, we can have power given in the queries with three cases. Let power given in the query be p. Then either p >= x, for which the answer will be n or p = x - 1 for which we computed the answer in step 2. Now for the case 3, i.e. when p < x - 1, all the accepted solutions seem to do a naive linear search to find the answer.
Now, I get that Binary Search is applicable and should be used for the first two cases, but I am not sure why this solution gets accepted because if for all the queries p < x - 1 then we will end up having worst time complexity to be O(N*Q) which should time-out according to the constraint. But it’s gets accepted.
So, to summarise-
- Find smallest power x such that it can kill all the monsters.
- Find the number of monsters that can be killed with power x - 1.
- For answering query if power given in the query p is >= x or = x - 1 then use the precomputed answer else find the answer naively.
3 Likes
I used a DP to calculate the minimum power required to kill x warriors and the health that will be left after killing them for 1 \le x\le n.
Link to my solution
2 Likes
can you explain a bit …
First, I sorted the powers of all the warriors.
Now,
dp[0] = {v[0], 0};
Note that dp[i] = \{ minimum power required to kill i+1 warriors, final power remaining after killing i+1 warriors with the minimum power \}.
For i>0 :
If dp[i-1].second >= v[i],
dp[i].first = dp[i-1].first;
dp[i].second = 2 * (dp[i-1].second - v[i]);
Else,
min_extra_power_required = v[i] - dp[i-1].second;
min_extra_initial_power_required = ceil(min_extra_power_required / (1<<i)); \* Because increment of 1 in our initial power will increase our power against warrior i by (1<<i) points*\
dp[i].first = dp[i-1].first + min_extra_initial_power_required;
dp[i].second = 2 * (dp[i-1].second + min_extra_initial_power_required * (1<<i) - v[i]);
Note that this implementation will have dp[i].second = 0 for some i, which is incorrect because we need to be alive as well after killing any number of warriors, therefore we can just increase dp[i].first by 1 for such i, dp[i].second is irrelevant at this point.
Now, we have the minimum powers required to kill x warriors for 1 \le x \le n. Therefore, we can easily find the answers for any query by a simple binary search.
This wraps up the explanation of the code, but we need to prevent overflows as well, since we are dealing with powers of 2 which can grow very large. For the implementation of the same, please go through my code linked in my previous comment.
7 Likes
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
long long n,q,i,X;
cin>>n>>q;
long long a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
while(q–)
{
long long cnt=0,j;
cin>>X;
for(i=0;i<1;i++)
{
if(X>a[i])
{
cnt=cnt+1;
X=2*(X-a[i]);
j=1;
while(X>a[j]&&j<n)
{
cnt=cnt+1;
j++;
}
}
}
cout<<cnt<<endl;
}
}
return 0;
}
can you please tell me whats wrong with my code ??
@rdx0067 You don’t update the value of X inside the while loop. Btw, The outer for loop seems completely unnecessary.
Good luck 
https://www.codechef.com/viewsolution/26021738
I’ve been trying to debug this for a while. Can you please help me find the issue.
my testcases are passed but whats wrong in my soluiton .Can someone pls tell me.
https://www.codechef.com/viewsolution/25992998
I am facing same problem ,and I cant think of anything .
https://www.codechef.com/viewsolution/26007128
i am getting TLE .Can u please tell what’s wrong in this.
How was this problem placed in the Easy section of practice? It literally got lowest correct submissions in division 2.
@shubham_avasth
Thanks a lot for the explanation. I understood the gist of it. However, there is just one small confusion.
Your definition of dp[i] is as follows
but you’ve defined dp[0] = {v[0], 0};
According to your definition, I think it should be dp[0] = {v[0] + 1, 0}.
because in case of power = v[i], the warrior will kill you. So the minimum power should be 1 more than that.
Although you’re taking care of that by incrementing dp[i].first by 1 when dp[i].second = 0. Am I right? If not, then please correct me.
Thanks again for the explaination!
I noticed the remaining alive constraint after I coded my solution, so added a fix for it later.
You can take care of this from the starting as well with slight modifications to the code. So, you can set dp[0] to \{ v[0]+1, 2 \}.
Note that dp[0].second = 2 \ * \ (v[0]+1 - v[0]) = 2
1 Like
@shubham_avasth
Why do we need an array of pairs, anyways ?
We could just store the maximum of both (which is the minimum power required to kill the warrior) in the dp array.
We can store the 2(x-y) depending upon the dp[i-1] for all in a separate array.
Makes it easier for binary search.
[CodeChef: Practical coding for everyone ]
I couldn’t get it ACed though. Idk why ?
That’s your way of implementing it. You can definitely do that.
https://www.codechef.com/viewsolution/26037090
Where is my understanding wrong here?
Since killing low power enemy means more power saving, we can sort the list of enemy powers and kill them greedily from low power to high.
Only problem here is, power can become almost twice if enemy has low power. This will cause in overflow in most cases. But since power can increase if enemy has less than half power, we can assume all the enemies can be taken over if the power reaches more than twice of the maximum power among the enemies. In such case, we can break the checking and return the number of enemies.
Why am I wrong here?
arr[n] causes undefined behaviour. Maybe try replacing it with a vector.
Also, the solution you linked has #if 0 in it, which causes the else part to run, which is incorrect.