Last Updated: 7 Dec, 2025

Fair Value Distribution

Easy
Asked in company
Amazon

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.


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.