Codeforces Round #704 Almost Fault-Tolerant Database - Enumeration + Implementation

Solution

Let's consider the scenario $n=2$. Because at most change two elements. So the most number of different points is 4.

Then, no matter what's the $n$ is. We just use the first one as template, and compare it to others. If we found the different points more than 4, then we just return No directly. Otherwise, we find the most different one. And solve this case by case:

  1. If the number of maximum differences is 4. Then we can enumerate the final result by $C_4^2=6$ way. And just need check this final result with others.
  2. If the number of maximum differences is $leq{2}$. Then just return the first one.

Now we only have a tough case which is maximum differences is 3.

Because only can change 2 elements. So in these 3 points, at least two of them will use the number from the two templates.

For example, the 3 points is $(1,2,3)$ and $(4,5,6)$. At least you need collect one from first one (which mean one from $(1,2,3)$). At the same time, you also need collect one from second one (which means one from $(4,5,6)$).

Now we can enumerate the two collected point in $A_3^2=6$ way. And mark the point which not collected any number as $unkown$.

Finally, we use this result to scan each template. We change the $unkown$ to some number when the first time we found we have to change it.

If we found any issue on this process, we just need return "No". Otherwise we can return the final result.

Just too many different scenarios in this problem.


Code

Submission #112160721 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge