I think this discussion should help:
comparator functions .
Have a look at the first 3 answers at least. Hope it helps. @devshiv
1 Like
Hi can anyone help point out the mistake in the following approach:
Reverse sorting the array and iterating over them. then taking two height variables and adding the loop variable to the minimum of the two heights. Keep looping till either both the heights are greater than K or number of elements in loop are exhausted.
can anyone help me to find a problem in my solution it is passing some subtasks but fails in some?
#include
using namespace std;
void insertion_sort (long long int array_sort[], long long int size);
long long int find_smallest_element (long long int array_sort[],long long int index,long long int size);
void swap_value (long long int array_sort[],long long int i_1, long long int index_2);
int main()
{
int number_of_testcases;
cin >> number_of_testcases;
for (int abcd=0; abcd <number_of_testcases;abcd++)
{
long long int n,k;
cin >> n >> k;
long long int blocks[n];
for (long long int i=0; i<n; i++)
{
cin >> blocks[i];
}
long long int i=0;
long long int a=0;
long long int b=0;
for ( i; (a<k)||(b<k)&& i<n ; i++)
{
insertion_sort(blocks,n);
if (a<k)
{
if(a==0)
{
a+=blocks[n-1];
blocks[n-1]=0;
insertion_sort(blocks,n);
continue;
//cout << a << " \n";
}
long long int j=0;
for ( j;a<k&&j<n;++j)
{
if (blocks[j]+a>=k||j==n-1)
{
a=a+blocks[j];
blocks[j]=0;
//cout << a << "\n";
break;
}
// cout << " " << j << "\n";
}
}
else
{
if (b==0)
{
b+=blocks[n-1];
blocks[n-1]=0;
continue;
insertion_sort(blocks,n);
}
long long int j=0;
for ( j;b<k&&j<n;j++)
{
if (blocks[j]+b>=k||j==n-1)
{
b=b+blocks[j];
blocks[j]=0;
break;
}
}
//cout << j << "\n";
//cout << b << "\n";
}
}
if (a>=k&&b>=k)
{
cout << i << "\n";
}
else
{
cout << "-1\n";
}
}
}
void insertion_sort(long long int array_sort[],long long int size)
{
for (long int i=0;i<size;i++)
{
long long int index =find_smallest_element(array_sort, i, size);
swap_value (array_sort, i, index);
}
}
long long int find_smallest_element(long long int array_sort[],long long int index, long long int size)
{
long long int index_of_smallest_value =index;
for (long int i = index +1; i<size;i++)
{
if (array_sort[i]<array_sort[index_of_smallest_value])
{
index_of_smallest_value=i;
}
}
return index_of_smallest_value;
}
void swap_value(long long int array_sort[], long long int i_1,long long int index_2)
{
long long int temp =array_sort[i_1];
array_sort[i_1]=array_sort[index_2];
array_sort[index_2]=temp;
}
//The above is the code I have tried to work with.
//I have done insertion_sort and then tried to optimally assign the values.
thanks in advance
https://www.codechef.com/viewsolution/41535464
here my solution somewhat does the same thing as yours.
the problem in this reverse sorting approach is that it won’t land the optimal solution every time.
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 
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 
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.