GOOGLE HASHCODE 2020

general
21 
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

22

please dont share those solutions

23

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?

24

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ā€¦

25

Why ?

26

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

27

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

28

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

29

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.

30

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

31

Nope the output should be :
3
0 2 3

32

but that gives 16 not 17

33

what would an optimal solution be?

34

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

35

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

36

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

37

would :
3
2 0 3

also be accepted

1 Like
38

Yes it would, order isnā€™t important

41

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

42

#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 ??