Connection Status:
Competition Arena > AlienSkiSlopes

AlienSkiSlopes

SRM 687 · 2016-04-01 · by lg5293

SRM 687 · 2016-04-01 · by lg5293 · Graph Theory
Class Name: AlienSkiSlopes
Return Type: int[]
Method Name: raise
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have been transported into an alien universe. After some wandering around you have stumbled upon an alien ski resort. In front of you, you see n aliens waiting to ski. (Each alien is currently in a different location.) In addition, you see n destinations in the ski resort. Both the aliens and the destinations are numbered from 0 to n-1.

You are given a int[] h with n*n elements. For each i and j, h[i*n+j] is the height difference between alien i and destination j. All the given height differences are nonnegative integers, meaning that each alien is currently at least as high as each destination. Since this is a strange universe, the height differences can be arbitrary: it is not guaranteed that they can be realized in our own physical universe.

Each alien will choose one of the destinations and ski there. The higher the height difference, the more fun will the alien have. As all aliens are greedy, each alien will always choose a destination that maximizes their own fun. If there are ties, the alien will be happy with any of the destinations that are tied for being the most fun.

A skiing accident may happen if two aliens choose the same destination. Sometimes it is possible to make sure there are no accidents by assigning a unique destination to each alien. However, note that the above rule takes precedence: no alien will compromise their own fun by choosing a suboptimal destination. Therefore, sometimes they have no way to avoid accidents.

This is where you can help them. You just realized that in this universe you have been granted the power to raise the heights of destinations in an arbitrary way. Raising the height of the j-th destination will cause the height difference from all aliens to this destination to decrease by 1.

After the changes, some height differences may become negative. This is allowed. However, note that an alien cannot ski to a destination that has a negative height difference. Therefore, after your changes the optimal destination for each alien must still have a nonnegative height difference.

If you raise the heights of some destinations, you may change the set of optimal choices for some aliens. In this way, you may be able to produce a configuration in which it is possible to prevent all skiing accidents. (In other words, a configuration where the aliens can choose their destinations in such a way that no two aliens choose the same destination and each alien chooses one of the destinations that gives them the most fun.)

You would like to use your powers to help make the aliens safe. If it is not possible to complete this task, return the int[] {-1}. Otherwise, return a int[] with exactly n elements: for each i, element i of the return value must be a nonnegative integer specifying the amount by which you raise the height of destination i.

If there are multiple solutions, return any of them. Note that each of the returned amounts must fit into an int. (If there is a valid solution, there is always a valid solution with this property.)

Constraints

  • n will be between 2 and 50 elements, inclusive.
  • h will have exactly n*n elements.
  • Each element of h will be between 0 and 10^9, inclusive.
Examples
0)
{1,0,0,
 0,1,0,
 0,1,0}
Returns: {1, 1, 0 }

There are three aliens. In the current situation, alien 0 would choose destination 0 and aliens 1 and 2 would each choose destination 1. This is bad, because aliens 1 and 2 may have an accident. One possible way in which you can help them is to raise the heights of destinations 0 and 1 by one each. This will change the table of height differences to the following one: { 0,-1, 0, -1, 0, 0, -1, 0, 0} After the change, alien 0 wants destination 0 or 2, and aliens 1 and 2 each want destination 1 or 2. This is a good situation because there is a safe set of choices. For example, alien 0 will choose destination 0, alien 1 will choose destination 2, and alien 2 will choose destination 1. Another correct answer is {0, 1, 0}: you only raise the height of destination 1 by one.

1)
{1,2,3,4,
 2,3,4,1,
 3,4,1,2,
 4,1,2,3}
Returns: {2, 2, 2, 2 }

The answer of {0,0,0,0} will also be accepted. The aliens' safety is your only concern, the amount of fun they have does not matter to you.

2)
{91, 19, 50, 21, 56,
 22, 96, 16, 30, 26,
 85, 1, 87, 63, 31,
 44, 25, 8, 94, 78,
 46, 55, 88, 41, 52}
Returns: {44, 13, 46, 22, 10 }
3)
{1000000000,0,0,
 1000000000,0,0,
 1000000000,0,0}
Returns: {1000000000, 0, 0 }
4)
{3,1,4,1,5,
 9,2,6,5,3,
 5,8,9,7,9,
 3,2,3,8,4,
 6,2,6,4,3}
Returns: {1, 0, 1, 0, 1 }

Submissions are judged against all 171 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AlienSkiSlopes with a public method vector<int> raise(vector<int> h) · 171 test cases · 2 s / 256 MB per case

Submitting as anonymous