GOOGLE HASHCODE 2020

s=list(map(int,input().split()))

n=s[0]
m=s[1]

a=list(map(int,input().split()))
l=[]
total=0
count=0
for i in sorted(a,reverse=True):
if(i+total>n):
continue
else:
l.append(i)
count+=1
total+=i
if total==n:
break

print(count)
l.sort()
for i in l:
print(a.index(i),end=" ")

I get WA. Why? Please help me

please dont share those solutions

In a case where sum has to 7 and if the array is 3,4,6, wouldn’t this approach return 6 even though 7 can be formed?

it will, cos here what I said :
“to make it perfect after ending. restart it but now remove the last element so the array will be”

before restarting it the old result must be stored and you should compared with the new and so on…

Why ?

The array is 3 3 4 10 , and the max is 16, your algorithm will yield 10 + 4 = 14, but we can get 10 + 3 + 3 = 16

it will work if you did removed elements, first time remove the last element second time remove the element before the last element…
the first array will be : 3 3 4 10 ==> 14
the second : 3 3 4 ==>>10
the third : 3 3 10 ==> 16
the forth : 3 4 10 ==> 14

and at the end we will take the best one.

The only issue you will got is with the execution time, and that what happened to me is that it took more than 40second

i keep getting this error please help?

Error: Invalid number of elements found at line 2

here is the contents of my output file for example A:
2
2 2 2 2 2 2 5

i dont understand what this error means

the a example file is this :
17 4
2 5 6 8

you can return the same element twice and you can’t return greater than 4 elements.
you did returned among the number : 5, it is impossible to find 5 there cos the possiblities to be returned are 0, 1, 2, 3.

so essentially this is what the output should be:
2
0 0 0 0 0 0 1

Nope the output should be :
3
0 2 3

but that gives 16 not 17

what would an optimal solution be?

Yes cos in that case 16 is the best result that you can get

And that’s the main purpose of that problem set, is to find the best closer result, so you should assume that it won’t be always the same as the max number

LOL this is depressing cause now my algorithm works for the last 3 data sets but not for the first 2

would :
3
2 0 3

also be accepted

1 Like

Yes it would, order isn’t important

i’m not able to open the test cases for the problem , what app do i need for that?

#include <bits/stdc++.h>
#include
#include
#include
#define ll long long int
#define ld double
#define l1(x,y) for(ll i=x;i<y;i++)
#define l2(x,y) for(ll j=x;j<y;j++)
#define l3(x,y) for(ll k=x;k<y;k++)
#define l4(x,y,uu) for(ll o=x;o<y;j+=uu)
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll ma , n ;
cin>>ma>>n;
ll a[n];
l1(0,n)
cin>>a[i];
vector v[2];
ll ptr = n-1;
ll scr=0;
ll temp=0;ll f=0;
while(ptr>=0)
{
scr+=a[ptr];
if(scr<=ma)
{
v[0].push_back(ptr);
ptr–;
continue;
}
scr-=a[ptr];
ptr–;
}

for(ll i=n-2;i>=0;i–)
{
ll pp=i;
temp=0;
v[1].clear();
while(pp>=0)
{
temp+=a[pp];

    if(temp<=ma)
      {

          v[1].push_back(pp);
          pp--;
          continue;
      }

        temp-=a[pp];
            pp--;

}

    if(temp>scr)
       {
           scr=temp;

v[0].clear();
for (auto i = v[1].begin(); i != v[1].end(); ++i)
v[0].push_back(*i);
}
}
cout<<v[0].size()<<endl;
for (auto ir = v[0].rbegin(); ir != v[0].rend(); ++ir)
cout << *ir << " ";
}

This is my codde
15 4
3 4 6 8
It gives me 2
2 3 max as 14
but i can go with max as 3 +6+8 as 15 but my code was acc how ??