GOOGLE HASHCODE 2020

whats your approach to Google hashcode 2020 practise round
My Code fail in last testcase

I just randomly shuffled the input array for a 1000 times and each time I checked for the largest subarray whose sum is less than equal to m.

ohk what i did is check if the arr element is less then max slices then select it and subtract that many slices from the max slices and do it till max slices becomes zero or the array ends. start the loop from the back. I know this is very vague explanation.

1 Like

what is your score??

Its 16 for the first test case and then exactly equal to m for the rest

2 Likes

Now!! I am going to do some DP based soln of this…Give me best of luck…:grinning::grinning::grinning:

I think it is similar to minimum coin change problem with condition that you have only one single coin of each type

40
4 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

Can u tell the complexity of your solution…
Is this np problem?

I just used the greedy approach by picking the elements from the end of the given array.

Its not NP hard, It can be done deterministically by a DP in O(n*m). My solution is a randomized algorithm tho done in O(k*n*logn) where k is the times you wanna run your algo.

4 Likes

But constraints are high to apply mn algo.
I think subset sum problem is no hard… if u model this problem in subset sum problem, whose complexity is O(n
m).
Is there any time limit in hash code

One doubt why you only check subarray not subsequence…

is this AC?

How to find whether we got AC or not? I m extremely new to hash code. Please help

but, is there any proof for correctness that will say that your solution is correct ?
can you please tell me?

There isn’t a proof of correctness, This is just a heuristic which outputs a good enough solution.

lol i am really gready and i am brute forcing every possible combination

just wondering do all the data sets have a perfect solution

Here is how I got it :

Lets assume that we have that list and lets consider it an array :
2 3 5 8 16 22 26 34 40 63

the max that we are looking for is 140

if we did 63 + 40 + 26 + 22 = 151 so it is false and more than expected (sort the array and iterate inversely)

we will only take out 63 + 40 + 26 = 129 and will store them on safe place

140 - 129 = 11
and our array become 2 3 5 8 16 22 and we are looking for 11

and we will repeat the same thing on new array.

to make it perfect after ending. restart it but now remove the last element so the array will be
2 3 5 8 16 22 26 34 40

1 Like