Fair Value Distribution

Easy

0/40

Contributed by

0 upvote

Asked in company

Problem statement

You are the system architect for a new online gaming platform. You need to design an algorithm to distribute rewards to players based on their scores in a tournament.

You are given two lists:

- points: A list of the final scores for all n players. Multiple players can have the same score.

- values: A large pool of available reward items, each with a specific "value" (e.g., 100 gems, 200 gems).

The reward allocation must follow these strict rules to ensure fairness and prestige:

- Group by Score: All players with the same score must receive the same reward value.

- Consume Rewards: If k players achieve a certain score, you must assign them a reward value that is available at least k times in the values pool.

- Increasing Prestige: A higher score must always receive a reward with a strictly greater value than a lower score.

- Minimal Assignment: To conserve valuable rewards, you must always assign the smallest possible value that satisfies the rules above.

Your task is to return a list showing the reward value assigned to each player in the original points list. If a fair assignment is impossible, you should return an empty list.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer n, the number of players (length of points).

The second line contains n space-separated integers for the points array.

The third line contains an integer m, the number of rewards (length of values).

The fourth line contains m space-separated integers for the values array.

Output Format:

The output should be a single line containing n space-separated integers, representing the assigned value for each corresponding player in the original points list.

If no valid assignment is possible, output a single empty line.

Sample Input 1:

3
10 20 10
5
100 200 100 300 300

Sample Output 1:

100 200 100

Explanation for Sample 1:

Scores {10: 2, 20: 1}. Values {100: 2, 200: 1, 300: 2}.

- Assign to score 10 (needs 2): Smallest value with count >= 2 is 100.     

- Assign 100. last_value=100.

- Assign to score 20 (needs 1): Smallest value > 100 with count >= 1 is 200. Assign 200.

Map {10:100, 20:200}. Final array is [100, 200, 100].

Sample Input 2:

2
10 10
3
100 200 200

Sample Output 2:

200 200

Explanation for Sample 2:

Score 10 needs 2. Smallest value with count >= 2 is 200. Assignment is possible.

Sample Input 3:

2
10 20
3
100 100 100

Sample Output 3:

(empty line)

Explanation for Sample 2:

Score 10 needs 1. Assign 100. last_value=100. Score 20 needs 1. No value > 100 is available. Impossible.

Expected Time Complexity:

O(N log N + M log M), where N and M are the lengths of the points and values arrays.

Constraints:

1 <= n, m <= 10^5
1 <= points[i], values[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Greedy Assignment with Sorted Iteration

Time Complexity

Space Complexity

(100% EXP penalty)

Fair Value Distribution

Console