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.

what is your score??

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

Now!! I am going to do some DP based soln of thisâ€¦Give me best of luckâ€¦

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?

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.

But constraints are high to apply m*n 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