Yes I have done it using greedy
1 Like
Here’s my blog for this problem if anyone’s having trouble understanding the editorial.
11 Likes
My solution is also like this editorial but instead of sorting the heights in non-decreasing, I sorted in non-increasing order and then traversed from start, and kept all height combination less than <K in a set, and also kept track of minimum height combination >=K, (min_k), and if at any index prefixSum[i]-min_k >= k I returned the (i+1).
still in 10 days i couldn’t find what i was doing wrong.HELP.
my Solution:-CodeChef: Practical coding for everyone
Bro please tell me what is the prob with my code??? 3 test cases was failing or provide me the test cases.
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes heresi
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt();
int k=sc.nextInt();
int[] list=new int[n];
for(int j=0;j<n;j++){
list[j]=sc.nextInt();
}
for(int j=0;j<n;j++)
list[j]=(-1)*list[j];
Arrays.sort(list);
for(int j=0;j<n;j++)
list[j]=(-1)*list[j];
/*for(int z:list)
System.out.print(z+" ");*/
int c=0,count=0;
int h1=0,h2=0;
while(true){
if(h1>=k && h2>=k){
System.out.println(count);
break;
}
else if((h1<k || h2<k) && c>=n){
System.out.println("-1");
break;
}
int dh1,dh2,c1,c2;
dh1=h1+list[c];
dh2=h2+list[c];
c1=k-dh1;
c2=k-dh2;
if(c1<0 && c2<0){
if(c1>c2){
h1=h1+list[c];
count++;
}
else{
h2=h2+list[c];
count++;
}
}
else if(c1>=0 && c2>=0){
if(c1<c2){
h1=h1+list[c];
count++;
}
else{
h2=h2+list[c];
count++;
}
}
else if(c1>=0 && c2<=0){
h1=h1+list[c];
count++;
}
else{
h2=h2+list[c];
count++;
}
c++;
}
}
}
}
1 Like
This problem can be solved with a recursive approach
https://www.codechef.com/viewsolution/41189741
3 Likes
Well explained. Thanks a lot!
81 27
21 50 45 50 39 14 34 17 40 28 8 21 27 35 16 31 37 44 24 39 39 16 24 47 41 7 19 32 4 27 8 22 26 3 38 30 30 37 13 35 30 18 6 7 18 19 3 4 12 40 40 17 21 29 29 11 34 13 41 3 37 14 22 29 30 25 8 10 12 18 42 39 34 45 11 49 29 27 19 39 16
Your answer is:
1
Correct answer is:
2
I ran it against my solution. I am not sure whether it will solve your problem. But anyway I have posted it. Another thing, that strikes is: How can “1” box ever be the answer. It has to be greater than 1. Hope you will find the error now. [Note: your code was good for small testcases(N<50)]. @devshiv
2 Likes
Very clean explanation. Thanks
I just changed Comparator
from
bool cmp(int a, int b) { return a >= b; }
to
bool cmp(int a, int b) { return a > b; }
and it got AC.and I don’t have the simplest clue why?
1 Like
Amazing Question, & Amazing Explanation, thanks, Authors!
1 Like
will you please share your code?
I want to see greedy approch…please
Anybody will you please help me out, where this approach is getting dumped
arr.sort(reverse=True)
mark, tracy, i = 0, 0, 0
while i < n:
if mark < k:
if mark + arr[i] > k:
for j in range(i, n):
# swapping elements so that the sum is closest to k
if mark + arr[j] < k:
arr[i], arr[j-1] = arr[j-1], arr[i]
break
elif mark + arr[j] == k:
arr[i], arr[j] = arr[j], arr[i]
break
mark += arr[i]
tracy += arr[i+1]
i += 2
elif mark >= k and tracy < k:
tracy += arr[i]
i += 1
elif mark >= k and tracy >= k:
print(i)
breakI 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