Connection Status:
Competition Arena > PrivateD2party

PrivateD2party

SRM 660 · 2015-05-01 · by subscriber

SRM 660 · 2015-05-01 · by subscriber · Brute Force
Class Name: PrivateD2party
Return Type: int
Method Name: getsz
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Hero is inviting his friends to the party.

He has n friends, numbered 0 through n-1. For each of his friends there is at most one other person the friend dislikes. You are given this information as a int[] a with n elements. For each i, a[i] is either the number of the person disliked by friend i, we have a[i]=i if friend i likes everybody else.

Hero is inviting his friends one at a time. Whenever he invites friend i, they will accept if and only if the friend a[i] didn't accept an earlier invitation. (That includes two cases: either Hero didn't invite friend a[i] yet, or he did but the friend rejected the invitation.)

Hero noticed that the order in which he invites his friends matters: different orders may produce different numbers of accepted invitations.

Find an order that will produce the most accepted invitations, and return their number.

Constraints

  • a will contain exactly n elements.
  • n will be between 1 and 50, inclusive.
  • Each element of a will be between 0 and n - 1, inclusive.
Examples
0)
{0,1}
Returns: 2

Each of the friends likes the other. Regardless of the order in which Hero asks them, they will both accept the invitation.

1)
{1,0}
Returns: 1

Friend 0 dislikes friend 1 and vice versa. The first friend Hero asks will accept the invitation but then the other friend will certainly reject it.

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

Here is what would happen if Hero invited the friends in the order (0,1,2,3,4,5): Friend 5 didn't accept yet, so friend 0 would accept. Friend 2 didn't accept yet, so friend 1 would accept. Friend 2 likes everybody and therefore they would accept. Friend 4 didn't accept yet, so friend 3 would accept. Friend 5 didn't accept yet, so friend 4 would accept. Friend 0 did already accept, therefore friend 5 would reject. It turns out that this solution happens to be optimal: there is no order such that all six friends would accept the invitations.

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

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

Coding Area

Language: C++17 · define a public class PrivateD2party with a public method int getsz(vector<int> a) · 150 test cases · 2 s / 256 MB per case

Submitting as anonymous