Connection Status:
Competition Arena > PieOrDolphin

PieOrDolphin

SRM 617 · 2013-12-22 · by dolphinigle

SRM 617 · 2013-12-22 · by dolphinigle · Graph Theory
Class Name: PieOrDolphin
Return Type: int[]
Method Name: Distribute
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

In this problem, some test cases have more than one correct output. We are using a special checker to verify that the output of your program is correct.

In a far away land, there are 50 programmers who work together in an office. As it is usual among programmers, they are numbered 0 through 49.

Mr. Ivan is the town's celebrity. The programmers like Mr. Ivan very much, so they invited him to the office. Flattered, Ivan decided to visit the office each day for the next N days. (We will number those days 0 through N-1, in order.)

Each day, Ivan brought two new toys with him to the office: one dolphin toy and one pie toy. And each day, the programmers held a meeting in which two programmers were selected as the most productive ones that day. One of them received a dolphin from Ivan, and the other one received a pie. (Ivan made the choice who gets which toy.)

Today was the day of Ivan's last visit to the office. After he handed over the last dolphin and the last pie, the programmers invited him to a farewell dinner. During the dinner, each programmer calculated the absolute difference between the number of dolphins and the number of pies he or she received. Then, they computed the sum of those differences. Amazingly, it turned out to be the case that the sum of all those differences was the smallest sum possible (given the particular set of choices of pairs of programmers on each day). The programmers were very amazed by Ivan's skill, but when they asked him about this, he modestly claimed that he just got lucky.

You are given two int[]s choice1 and choice2, each with N elements. For each i, the programmers who received toys on day i were the programmers choice1[i] and choice2[i].

Find one way how to distribute the toys in such a way that the sum defined above is minimized. Return a int[] with N elements. For each i, element i of the returned int[] should be either 1 or 2. The value 1 means that on day i the programmer choice1[i] should get the dolphin and the programmer choice2[i] should get the pie. The value 2 is the opposite assignment of toys.

If there are multiple optimal distributions, you may return any of them.

Constraints

  • choice1 will contain between 1 and 1000 elements, inclusive.
  • Each element in choice1 will be between 0 and 49, inclusive.
  • choice2 will contain the same number of elements as choice1.
  • Each element in choice2 will be between 0 and 49, inclusive.
  • For each i, choice1[i] will not be equal to choice2[i].
Examples
0)
{10, 20, 10}
{20, 30, 20}
Returns: {2, 2, 1 }

According to the return value shown in the example, the toys were distributed as follows: Day 0: programmer 10 gets a pie, programmer 20 gets a dolphin. Day 1: programmer 20 gets a pie, programmer 30 gets a dolphin. Day 2: programmer 10 gets a dolphin, programmer 20 gets a pie. Here is what the programmers compute during the farewell dinner: Programmer 10 got 1 dolphin and 1 pie. The absolute difference is |1-1| = 0. Programmer 20 got 1 dolphin and 2 pies. The absolute difference is |1-2| = 1. Programmer 30 got just 1 dolphin. The absolute difference is |1-0| = 1. Each of the other 47 programmers did not receive anything, so they compute |0-0| = 0. At the end of the dinner, they sum all those results and obtain the sum 2. This is the smallest possible sum for the given input, hence the return value is correct.

1)
{0, 0}
{1, 1}
Returns: {2, 1 }
2)
{0, 1, 2, 3, 5, 6, 7, 8}
{8, 7, 6, 5, 3, 2, 1, 0}
Returns: {2, 2, 2, 2, 2, 2, 2, 2 }
3)
{49, 0, 48, 1}
{3, 4, 5, 6}
Returns: {2, 2, 2, 2 }
4)
{0, 1, 2}
{3, 3, 3}
Returns: {2, 2, 1 }

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

Coding Area

Language: C++17 · define a public class PieOrDolphin with a public method vector<int> Distribute(vector<int> choice1, vector<int> choice2) · 98 test cases · 2 s / 256 MB per case

Submitting as anonymous