SmilesTheFriendshipUnicorn | Topcoder Archive

Problem Statement

Smiles the Friendship Unicorn lives in the Friendship Kingdom. There are N people in the Friendship Kingdom, numbered from 0 to N-1. Some of them are friends with each other: you are given these pairs in the int[] A and the int[] B. For each valid i, the person numbered A[i] is friends with the person numbered B[i]. Friendship is two-way, so the person numbered B[i] is also friends with the person numbered A[i]. For every group containing between 1 and N-1 people (inclusive), at least one person in the group is friends with someone outside the group.

Smiles would like to know whether there exists a friendship chain. A friendship chain is a sequence of 5 distinct people A, B, C, D, and E such that:

A is friends with B.
B is friends with C.
C is friends with D.
D is friends with E.

(In the language of graph theory: a friendship chain is a simple path of length 4.)

If a friendship chain exists, output "Yay!". Otherwise, output ":(". (All quotes are for clarity only.)

Definition

Class:: SmilesTheFriendshipUnicorn
Method:: hasFriendshipChain
Parameters:: int, int[], int[]
Returns:: String
Method signature:: String hasFriendshipChain(int N, int[] A, int[] B)
(be sure your method is public)

Constraints

N will be between 5 and 2000, inclusive.
A will contain between 1 and 2000 elements, inclusive.
A and B will contain the same number of elements.
Each element of A and B will be between 0 and N-1, inclusive.
No one will be friends with themselves.
The same friendship will not be given twice in the input.
For every group containing between 1 and N-1 people (inclusive), at least one person in the group is friends with someone outside the group.

Examples

```
5
```
```
{0, 1, 2, 3}
```
```
{1, 2, 3, 4}
```
```
Returns: "Yay!"
```
A friendship chain is formed by: Person 0 Person 1 Person 2 Person 3 Person 4 in that order. (The reverse order 4-3-2-1-0 is also a valid friendship chain.)
```
5
```
```
{0, 1, 2, 3, 1}
```
```
{1, 2, 3, 0, 4}
```
```
Returns: "Yay!"
```
One example of a valid friendship chain is: Person 4 Person 1 Person 2 Person 3 Person 0

{0, 0, 0, 0, 0}

{1, 2, 3, 4, 5}

Returns: ":("

{1, 3, 4, 3, 4, 3, 0, 2}

{7, 7, 7, 4, 6, 5, 4, 7}

Returns: "Yay!"

{0, 1, 1, 5, 4, 5}

{5, 2, 3, 6, 1, 1}

Returns: ":("

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 0}

Returns: "Yay!"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.