WIPL - Editorial

CodeChef: Practical coding for everyone – sorry for messy code

thanks, man.

https://www.codechef.com/viewsolution/41449173
This is the link to my code. Can someone please inspect it and tell me where did I go wrong or what test cases are missing?

Approach: 1. Sorted the vector
2. Took a variable temp=k and looked for anything greater or equal to temp in the
vector.
3. If found increased sum1 by that value and decreased temp by that value. And delete
the included element from the vector.
4. If not found, I took the largest value and added it into sum1 and subtracted from
temp. And deleted the element.
5. Repeat this while sum1<k.
6. Did the same thing for the second tower.

Why this code got wrong …please help me to explain
#include
#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main()
{
ll t;
cin>>t;
while(t–)
{
vectorv;
ll n,s,m=0ll,k=0ll,c=0ll;
cin>>n>>s;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
v.push_back(x);
}
sort(v.rbegin(),v.rend());
/for(int i=0;i<n;i++)
cout<<v[i]<<" ";
cout<<endl;
/
ll i=0ll;
while(k<s||m<s)
{
while(k<=m&&i<n&&k<s)
{
k=k+v[i];
c++;
//cout<<"k "<<k<<endl;
//cout<<"c "<<c<<endl;
i++;
}
while(m<=k&&i<n&&m<s)
{
m=m+v[i];
c++;
//cout<<"m "<<m<<endl;
// cout<<"c "<<c<<endl;
i++;
}
if (i==n)
break;
}
if(m>=s&&k>=s)
cout<<c<<endl;
else cout<<-1<<endl;
}
}
Link this code CodeChef: Practical coding for everyone

Can anyone please suggest a single edge case for which my solution will not work ? I have solved this problem using greedy approach ! my solution is not accepted. This is my code.

This question has k^3 (k=4000) complexity in the worst case, how is it possible that it is not given TLE??

please help me in confusion

1 Like

Your solution fails at this TC, answer should be 10 but yours is giving 11

1
12 40
10 10 10 9 9 9 9 7 4 3 2 1

I tried kind of same approach as yours but was failing in 1 TC in subtask 2

3 Likes

How does it has k^3 complexity? The setter’s and tester’s solution runs in n^2 i.e < 2*10^6 times. Check in the setter’s solution there are 2 loops one runs n times another k times.

Thank you very much. I’ll try and correct my code.

@yogi_sleeping You had commented that there’s a case the setter is missing ? Can you share that please? I cannot see what did I miss

This is my code
https://www.codechef.com/viewsolution/41312992
Here I used subset sum DP inside do while loop,
I think it has k^3 complexity in worst case

1 Like

@shivam51 in my approach I first handled the case with two elements >= k and then the case of exactly one element >= k and then finally for the other cases. Partially accepted case. Here you can have a look at the if block starting at line 84. It is printing the answer for the case where only one integer is >= k and I missed putting continue at the end of that if block. So for such cases it was actually printing two answers for the same case. This error was caught in the 1st subtask but it seems like in 2nd subtask there was not such case with a single integer >= k. So it passed for 70 points. Completely accepted - the only change is continue statement at line 109. So seems like the second subtask didn’t have a single case with exactly 1 integer greater than or equal to k. I might be wrong but that doesn’t seem likely. Btw nice problem for knapsack :slight_smile:

1 Like

Can anyone tell me why this solution is getting WA in 3 test cases.
Or can anyone give me a testcase where this code will fail?
https://www.codechef.com/viewsolution/41393477

Can Someone please Explain why am I getting a TLE?? (in WIPL)
I tried the exact Editorial (editor’s) code but in python.
IS THIS SOME DRAWBACK OF PYTHON?
Here’s the link to my code- > My Code


Btw the question was really awesome!!

1 Like

understood :+1:
But can pls give an example!

This is my code for WIPL problem,
https://www.codechef.com/viewsolution/41248027
Can anyone share test cases my approach is ignoring.
I am basically adding to that tower which is lesser in height at each iteration.

I like the solution thanks. I hope you don’t mind if I ask where do I learn knapsack algorithm from.

Can you please explain the ans = a|b; and the next part in checkSubset function in your code mention in the blog. Please.

Yes. I did it in my blog. Please have a look.

https://www.codechef.com/viewsolution/41537480