Biased Standings Problem Using C++

Today, we’ll learn to solve the greedy problem biased standings using C++. The biased standings problem is one of the most popular greedy problems present on SPOJ(Sphere Online Judge). There are multiple solutions to this problem. however, we’ll go for the most efficient one. So without wasting any time, let’s go through the problem statement.

Also read: Greedy Problem Join The Ropes Using C++

Problem Statement

Suppose that we already have a rank list. For each team, compute the distance between their preferred place and their place in the rank list. The sum of these distances will be called the badness of this rank list. Find the minimum possible badness for a given rank list.

For example,

Number of teams: 7
Desired rank list:
(rank - name)
1. noobz
2. llamas
2. Winn3rz
1. 5thwheel
5. NotoricCoders
7. StrangeCase
7. WhoKnows

Minimum possible badness for current list: 5

Explaination:
The rank list with the minimum badness will be:
1. noobz: badness = 0
2. llamas: badness = 0
3. Winn3rz: badness = 1
4. 5thwheel: badness = 3
5. NotoricCoders: badness = 0
6. WhoKnows: badness = 1
7. StrangeCase: badness = 0

Total badness = 5

Number of teams: 3
Desired rank list:
1. ThreeHeadedMonkey
1. MoscowSUx13
1. NeedForSuccess

Minimum possible badness for current list: 3

Explaination:
The rank list with the minimum badness will be:
1. ThreeHeadedMonkey: badness = 0
2. MoscowSUx13: badness = 1
3. NeedForSuccess: badness = 2

Total badness = 3

Approach for Solving This Problem

The general approach to dealing with greedy problems is the following.

• Make a greedy choice. (Local Optimum)
• Verify that it’s a valid greedy choice.
• Sort the items based on greedy selection.
• Start the selection from the sorted items. (Local optimum at each step leads to global optimum)

Key To Solving This Problem

Note that, this is a minimization problem. It is not possible to allot the same rank to multiple teams. Thus, we’ll give the closest rank to the desired rank to each team.

Logic for Solving Biased Standings Problem Using C++

• Start with the actual rank as 1.
• The variable sum denotes the total badness based on this rank list.
• We’ll iterate once for each team
  • for(int i = 1; i <= N; i++)
  • Until the freq of the rank becomes 0, we’ll do the following computation
  • while(freq[i])
    • The badness will become: abs(actual_rank – i).
    • Once you allocate a particular rank to a team, decrease the freq[i]
    • Increase the value of the actual rank as actual_rank++;

    int actual_rank = 1;
	int sum = 0;

	for(int i = 1; i <= N; i++)
	{
		while(freq[i])
		{
			sum += abs(actual_rank - i);
			freq[i]--;
			actual_rank++;
		}
	}

Biased Standings Problem Using C++ Program

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int freq[10000] = {0};

	// take input the name of the team
	// and the rank that the particular
	// team is expecting
	cout << "Enter the total number of teams" << endl;
	int N;
	cin >> N;

	vector <pair<string, int>> team_rank_pair(N);

	// input the details of all the teams
	cout << "Enter the name and the rank of each team" << endl;
	for(int i = 0; i < N; i++)
	{
		string name;
		int rank;
		cin >> name >> rank;

		// increase the frequency of each rank
		// as the demand increases
		freq[rank] ++;

		team_rank_pair[i] = make_pair(name, rank);
	}

	// once the input is done and the frequency
	// array is ready, let's move towards the logic
	int actual_rank = 1;
	int sum = 0;

	for(int i = 1; i <= N; i++)
	{
		while(freq[i])
		{
			sum += abs(actual_rank - i);
			freq[i]--;
			actual_rank++;
		}
	}

	cout << "The minimum possible badness based on the best ranklist is: " << sum << endl;

	return 0;
}

Output

Conclusion

In this article, we learned to solve the greedy problem biased standings using C++. We used the counting sort method to solve this problem in O(N) time complexity. This is the most efficient solution available for this problem. In the end, we implemented a C++ program to demonstrate the working of our solution. Thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/56574/first-occurrence-last-occurrence-functions-cpp

https://www.journaldev.com/61222/prime-factorization-sieve-of-eratosthenes-cpp