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: