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
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 mn algo.
I think subset sum problem is no hard… if u model this problem in subset sum problem, whose complexity is O(nm).
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