Editorial for TLE '17 Contest 8 P1 - Artificial Intelligence


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

First, note that a linear transformation is not the same as a function with a linear graph, that is, a function in the form of f(x) = mx+b.

We deduce a few properties about T. First, we see that T(0) = T(0x) = 0T(x) = 0. Also, T(x) = T(1x) = xT(1). If we let m = T(1), then we see that T(x) = mx for some m. It can be easily proven that the first property T(x+y) = T(x)+T(y) still holds.

Exercise: show that when T only satisfies the first condition, then it does not need to be in the form T(x) = mx. Would this solution still be correct?

Therefore, we simply need to check if all points are on the same graph T(x) = mx for some m. The implementation is not very difficult, but do be wary of the corner case where x = 0.

Failing to resolve the x = 0 corner case resulted in 25\% of the points, and a slow all-pairs comparison of slope was awarded 50\% of the points.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.