prafull_vrsh's blog

By prafull_vrsh, 6 weeks ago, In English

Hello everyone, This question was asked in Hackwithinfy (9 May 3 pm slot). Please share a possible solution.

You are the manager of the hotel and you have N customers to serve. Each customer has a happiness quotient (Ci) if the food is served to him at time x. The unhappiness of a customer is defined by |Ci — x|. You must serve all the customers and you can serve them in any order. You have to find the minimum sum of unhappiness.

Note: At a particular time only one customer is served and Each customer takes one unit of time.

Contraint:

1 <= N <=10^3 1<= Ci <=N

Sample input:

4 2 2 3 3

Sample output: 2

Sample input:

4 1 1 1 1

Sample output: 6

Please give suggestions on how to solve this problem efficiently.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Problem can be solved using DP. In the case with minimum unhappiness, customers will be served in sorted order according to their happiness quotient(C). dp[i][j] is the minimum unhappiness when we are time i and have served j people. DP has n^2 states

Transition

Do comment if you feel something is wrong

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I understand the approach.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I don't understand the need of DP after sorting the array. Can't we simply add all the absolute difference with the index to get the answer?

    sort(C,C+n)
    for(i=0;i<n;i++)
       ans+=abs(i+1-C[i]);
    

    Can you give a test case where this might fail?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      3 3 3 Time served is not bounded by N, actual answer is (2 3 4).

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why is there dp[i-1][j] in the transition?

    Edit: Sorry, I get it. You had i as time, I was thinking the opposite way.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the order of serving in sample input #2 to get the minimum unhappiness as 6?

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

How is the output of 2nd tc 6?
Any arragemenet you do, the minimum will be 7 I guess.
$$$4,1,1,1,1 -13$$$
$$$1,4,1,1,1 -11$$$
$$$1,1,4,1,1 -9$$$
$$$1,1,1,4,1 - 7$$$
$$$1,1,1,1,4 - 7$$$

How is it 6?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Hi dca, First number is size of array. Explanation of test case 2: |1-1| + |1-2| + |1-3| + |1-4| = 6

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh sorry my bad. I didn't look at it clearly. Thanks for the explanation.

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

1437C - Chef Monocarp Exactly same Problem.