B - Unique Nicknames Editorial by en_translator


Let us first consider how to determine if “it is possible to give Person \(i\) a nickname.”
Person \(i\)’s nickname \(a_i\) should satisfy the following two conditions:

  • \(a_i = s_i\) and/or \(a_i = t_i\) holds;
  • for every integer \(j\) such that \(1 \leq j \leq N, i \neq j\), it holds that \(a_i \neq s_j\) and \(a_i \neq t_j\).

By the first condition, the candidates of \(a_i\) are limited to \(s_i\) and \(t_i\). Therefore, if at least one of \(s_i\) or \(t_i\) satisfies the second condition, then we can give a nickname two Person \(i\). Whether a string \(S\) is an appropriate nickname for Person \(i\) can be determined by iterating \(j\) with a for loop to check if there is \(s_j\) or \(t_j\) coincides with it, in a total of \(\mathrm{O}(N |s_i|)\) time (where \(|S|\) denotes the length of string \(S\)).

By implementing the algorithm above, we can determine if “it is possible to give Person \(i\) a nickname.” By doing this for every person, Person \(1\), Person \(2\), \(\dots\), Person \(N\), we can determine if we can give nicknames to all the people.

The time complexity is \(\mathrm{O} \left(N^2 (\max(|s_i|)+\max(|t_i|)) \right)\). The following is a sample code in Python.

N = int(input())
s, t = [], []
for i in range(N):
  u, v = input().split()
  s.append(u)
  t.append(v)

for i in range(N):
  can_give_a_nickname = False
  for S in [s[i], t[i]]:
    s_ok = True
    for j in range(N):
      if i != j:
        if S == s[j] or S == t[j]:
          s_ok = False
    if s_ok == True:
      can_give_a_nickname = True
  if can_give_a_nickname == False:
    print("No")
    exit()

print("Yes")

posted:
last update: