Biased Standing Problem

Solve a SPOJ problem based on the Greedy approach.

We'll cover the following

Problem statement

In a competition, each team is able to enter its preferred place in the rank list. Suppose that we already have a rank list. For each team, compute the distance between its preferred place and its actual place in the rank-list. The sum of these distances will be called the badness of this rank list. Given team names and their preferred placements in the rank list, find one rank list with minimal possible badness and print the badness.

Let us take an example to see what the inputs will be and how the result is defined.

We have the following input, where the string is the team name and the integer value defines the preferred placement of the team in the rank-list.

  • noobz 1
  • llamas 2
  • Winn3rz 2
  • 5thwheel 1
  • NotoricCoders 5
  • StrangeCase 7
  • WhoKnows 7

The output for this input ——which denotes the minimum badness of all possible rank lists — would look like this:

  • 5

The rank list could be:

  1. noobz
  2. llamas
  3. Winn3rz
  4. 5thwheel
  5. NotoricCoders
  6. WhoKnows
  7. StrangeCase

As we can see after summing the distance between the preferred and actual places in the rank list, we get the output as 5.

Solution: Greedy approach

We can apply the Greedy approach by sorting the desired ranks and calculating the distance between ith{i^{th}} desired rank and ith{i^{th}} actual rank.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.