Matematické Fórum

ExSh00t napsal(a):

https://leetcode.com/problems/elimination-game/ rice purity test

Let res(n) = [final number from {1, 2, 3, ..., n} starting elimination from left]

1. Perform a left to right elimination round
=> res(n) = [final number from {2, 4, 6, ..., (n-1) or (n-2) whichever is even} starting elimination from right]

2. Extract common factor of 2
=> res(n) = 2 * [final number from [1, 2, 3, ... n/2] starting elimination from right]

3. Reversing both the direction and the sequence doesn't change anything
=> res(n) = 2 * [final number from {n/2, ..., 3, 2, 1} starting elimination from left]

4. Make the sequence align with original definition of res(n).
To convert {n/2, ..., 3, 2, 1} to {1, 2, 3, ..., n/2}, we could do a[i] = n/2 + 1 - a[i] but then result (which is one of these a[i])
also gets changed so we need to convert it back again by doing (n/2 + 1 - result).
=> res(n) = 2 * (n/2 + 1 - [final number from {1, 2, 3, ..., n/2} starting elimination from left])

5. Voila
=> res(n) = 2 * (n/2 + 1 - res(n/2))

V bode 4 som sa zasekol ako prebieha hlavna konverzia na rekurentny vztah. Co presne znamena a[i] = n/2 + 1 - a[i].
Dakujem

The key steps involve performing a left-to-right elimination, extracting a common factor, and converting the reversed sequence back to the original order using the formula a[i] = n/2 + 1 - a[i]. This leads to the final recursive formula res(n) = 2 * (n/2 + 1 - res(n/2)).