Register Jayy__07

dp

can you share your code?

same here

deduced the logic of D in like less than 5 minutes but was stuck on C for around 25 minutes but couldnt think of anything

thought of another dp solution

dp[index][last char 0/1][len], does it work? Although prefix and suffix would be easier and better and also this is a very standard problem.

C is just bruteforce

You might be relating it with Angry Cows problem from USACO but I couldnt figure out a binary search solution for this since the power of each station is different, instead I came up with another very simple solution, sort the houses and then think about it then the problem becomes, "There are n elements in an sorted array and we have to from k sub arrays such that the sum of (max-min) of each sub array is minimized."

I got that but couldnt really figure out how to compute it optimally since n is till 1e12?

So I submitted a brute force solution to check if it was correct and around 20 cases were passed and rest got TLE so yeah its correct.

Sort the houses and then think about it then the problem becomes, "There are n elements in an sorted array and we have to from k sub arrays such that the sum of (max-min) of each sub array is minimized."