Todai Entrance Exam: Subject 2017 – Problem 3

(1)

Let L_{i} be the values of L after processing A[i].

    \[ L_{1} = \{ 11 \} \]

    \[ L_{2} = \{ \} \]

    \[ L_{3} = \{ 11 \} \]

    \[ L_{4} = \{ 11, 11 \} \]

    \[ L_{5} = \{ 11 \} \]

    \[ L_{6} = \{ 11, 11 \} \]

    \[ L_{7} = \{ 11, 11, 11 \} \]

    \[ L_{8} = \{ 11, 11 \} \]

    \[ L_{9} = \{ 11 \} \]

(2)

We use induction proof: If a list L has the number of varieties of user IDs being at most one then \text{var}(L) = 0.

Base case: L_{0} = { }, so \text{var}(L_{k}) = 0 when k = 0.

Induction step: At the (k + 1)th iteration, we assume that \text{var}(L_{k}) = 0. We prove that if \text{var}(L_{k}) = 0, \text{var}(L_{k + 1}) = 0.

If L_{k} is empty then L_{k + 1} = { A[k] }, so \text{var}(L_{k + 1}) = 0.

In the case L_{k} is not empty, A[k] is added to L_{k + 1} if it is already included in L_{k}, so \text{var}(L_{k + 1}) = \text{var}(L_{k}) = 0. If A[k] is not already included in L_{k}, it will not be added to L_{k+1}, moreover one number of L_{k} will be excluded in L_{k + 1}, so \text{var}(L_{k + 1}) \leq \text{var}(L_{k}) \Rightarrow \text{var}(L_{k + 1}) = 0.

So the statement follows.

(3)

If u_{\text{majority}} exists then frequencies of u_{\text{majority}} must be larger than \frac{| L |}{2}, which implies \forall A[i] \neq u_{\text{majority}}, \exists A[j] = u_{\text{majority}}.

So if numbers in the list L are not u_{\text{majority}}, then they are guaranteed to be removed all in step ii-(b) by the corresponding numbers u_{\text{majority}} (or by other numbers of different values).

If the numbers in list L are u_{\text{majority}}, then it is guaranteed to have at least one number u_{\text{majority}} left for step iii as the total number of values different from u_{\text{majority}} must be less than the frequency of u_{\text{majority}} by definition.

So the statement follows.

(4)

a = read_log()

L = -1

while a != -1:

if L == -1:

L = a

else:

if L != a:

L = -1

a = read_log()


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *