We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- All Contests
- HourRank 1
- Beautiful Array
- Discussions
Beautiful Array
Beautiful Array
Sort by
recency
|
7 Discussions
|
Please Login in order to post a comment
My approach is of complexity O (kn), where k = range (min (array) to max (array)) (inclusive) and n = size of the array. It passed all the test cases.
REMEMBER: The point of convergence doesn't HAVE to be an element from the array. It can be any number in the range of min to max, so I applied exhaustive search.
def get_optimal (array, size, pivot, op1, op2):
inc = dec = cost = 0
for i in array:
if (i < pivot):
inc += (pivot - i);
elif (i > pivot):
dec += (i - pivot);
size, op1, op2 = [int (i) for i in input ().split ()];
array, optimal = [int (i) for i in input ().split ()], float ('inf');
for i in range (min (array), max (array) + 1):
temp = get_optimal (array, size, i, op1, op2);
optimal = temp if optimal > temp else optimal;
print (optimal);
Hi I am trying to solve this by first sorting the elements and consider each element as median ( the number to which we should convert all other number) and trying to get the coins for other elements to convert to the median and finally will display the minimum coins that we get.
First trying to calculate the difference between the median and its right side(elements that are higher than the median) elements. Then add the difference. Getting this sum of difference to caluclate the cost for performing the first operation. Cost will be directly multiply the sum of difference with the value k.
Then getting the sum of difference on the left side. This will be used to calculate to perform second operation. I'll subract the sum of median's right side difference from left side as we already used them for performing the first opertaion. The cost for performing second operation will be remaining difference multiplied by l.
The sum of the above two will give the answer. Similarly will do the steps for all elements as median then will display the minimum value as the cost. What am I missing in this.
int upperMedianDiff = 0; for (int i = medianIndex + 1; i < n; i++) { if (elementsList.get(i) != median) { upperMedianDiff += (elementsList.get(i) - median); } } int lowerMedianDiff = 0; for (int i = 0; i < medianIndex; i++) { if (elementsList.get(i) != median) { lowerMedianDiff += (median - elementsList.get(i)); } } if (upperMedianDiff <= lowerMedianDiff) { tempAns += (upperMedianDiff * k); tempAns += (lowerMedianDiff - upperMedianDiff) * l; } if (tempAns != 0) { ans = Math.min(ans, tempAns); }
Answer doesn't have to be median number. Look at following example :
4 10 1
3 3 7 6
Optimal solution for beautiful array is :
7 7 7 7
Answer 9.
Yes .. I am considering each element as median and trying to find the cost of coins and return minimum coins.
For the above example It will first consider 3 at index 0 as median do the operation, will consider 3 at index 1 as median do the operation similarly if we take six it will return 15 and for 7 it will return 9.
Current Median Index - 0, median value - 3, upperMedianDiff - 7, LowerMedian Diff - 0, cost of coins - 2147483647, cost of coins to convert to 3 - 0
Current Median Index - 1, median value - 3, upperMedianDiff - 7, LowerMedian Diff - 0, cost of coins - 2147483647, cost of coins to convert to 3 - 0
Current Median Index - 2, median value - 6, upperMedianDiff - 1, LowerMedian Diff - 6, cost of coins - 2147483647, cost of coins to convert to 6 - 15
Current Median Index - 3, median value - 7, upperMedianDiff - 0, LowerMedian Diff - 9, cost of coins - 15, cost of coins to convert to 7 - 9.
I handled this case but yet some problem with the soultion. If possible i am ready to upload the entire code. Can you please help me to find the mistake in this logic ??
Sorry, maybe I don't understand your solution... You must check all possible numbers in interval [0...maxAi] for 'median'. You can not check only elements from array. Example :
2 1 1
4 2
Array is: 3 3
Answer 1
How can anyone solve this problem in less then 3 or even 5 mins. It takes me more than that just to read and understand the requirments. Then, I think about the approach then I start coding. Can anyone explain me how those top 10 could solve this problem, in less than 5 mins?!!
I think they notice that the n k l values are very small, so a bf approach would be good enough to solve the problem, not necessary to find the best solution.
Below is the bf approach I wrote in java passed all cases in less than 0.2s, max is the max value, target can be the median, you just need to loop through all values between target and max value to find the min cost.
INCLUDED INCLUDED INCLUDED
while(max >= target){
In editorial problem setter talked about 'size' h. What did he mean by h? Size of array is n, so what is 'h'
He think that h is size of elements in the final-beautiful array. The question is: how much coins we should spend to make all elements eqaul with h. Because all numbers are in range [1,1000] we can iterate over all possible solutions for the size of elements in the final array. We will check all possible h in the given range.
What's the approach to solve this problem?
Editorial is published you can read solution :)
so by reading the Editorial, you just can't resubmit for more points? or does it remove the points you already have entirly?