Contest Duration: - (local time) (100 minutes) Back to Home
Official

## 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: