Connection Status:
Competition Arena > SmilesTheFriendshipUnicorn

SmilesTheFriendshipUnicorn

SRM 682 · 2016-01-04 · by zxqfl

SRM 682 · 2016-01-04 · by zxqfl · Graph Theory
Class Name: SmilesTheFriendshipUnicorn
Return Type: String
Method Name: hasFriendshipChain
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

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.)

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
0)
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.)

1)
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

2)
6
{0, 0, 0, 0, 0}
{1, 2, 3, 4, 5}
Returns: ":("
3)
8
{1, 3, 4, 3, 4, 3, 0, 2}
{7, 7, 7, 4, 6, 5, 4, 7}
Returns: "Yay!"
4)
7
{0, 1, 1, 5, 4, 5}
{5, 2, 3, 6, 1, 1}
Returns: ":("

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

Coding Area

Language: C++17 · define a public class SmilesTheFriendshipUnicorn with a public method string hasFriendshipChain(int N, vector<int> A, vector<int> B) · 55 test cases · 2 s / 256 MB per case

Submitting as anonymous