👠 🚎 🕹️ Full analysis of the first part of the exam in SHAD 2020 💇🏾 🛤️ 📖

Hello! I’m Azat Kalmykov, curator at ShAD Helper. We continue our series of articles in which we analyze the tasks for entering the ShAD. This time we (I, Nikolai Proskurin and Alexander Kurilkin) will look at the decisions of the first stage of selection in the ShAD this year, which ended recently. So let's get started.

A. Local minimum

At what values of the parameter a antiderivative of the function

f (x) = (x^{4} - (a + 1) x^{3} + (a - 2) x^{2} + 2 a x) \exp^{\frac{\sin x^{2} + 2}{5 x^{2} + 2}}

$f(x)=\left(x^{4}-(a+1) x^{3}+(a-2) x^{2}+2 a x\right) \exp ^{\frac{\sin x^{2}+2}{5 x^{2}+2}}$ has at most one local minimum?

Decision

, — . , . , , ( ).

, , , ,

f (x) = x^{4} - (a + 1) x^{3} + (a - 2) x^{2} + 2 a x

$f(x) = x^4 - (a + 1)x^3 + (a - 2)x^2 + 2ax$ . , :

- 1, 0, 2, a

$-1, 0, 2, a$ . ,

f (x) = (x + 1) x (x - 2) (x - a)

$f(x) = (x + 1)x(x - 2)(x - a)$ .

,

+ \to - \to + \to - \to +

$+ \to - \to + \to - \to +$ , . ,

a = - 1, 0, 2

$a = -1, 0, 2$ . , .

B. Limit

Determine at what value

a

$a$ this limit is

\frac{1}{e}

$\frac{1}{e}$ :

lim_{x \to + inf} {(\cos \sqrt{\frac{1}{x}})}^{\frac{x}{a}}

$\lim _{x \rightarrow +\inf }\left(\cos \sqrt{\frac{1}{x}}\right)^{\frac{x}{a}}$

Decision

a = 1

$a = 1$ .

\sqrt{\frac{1}{x}} \to 0

$\sqrt{\frac{1}{x}} \to 0$ , :

\cos \sqrt{\frac{1}{x}} = 1 - \frac{1}{2! x} + \frac{1}{4! x^{2}} - \frac{1}{6! x^{3}} + \dots

$\cos{\sqrt{\frac{1}{x}}} = 1 - \frac{1}{2!x} + \frac{1}{4!x^2} - \frac{1}{6!x^3} + \ldots$

. , , , , . , . :

1 - \frac{1}{2 x} < \cos \sqrt{\frac{1}{x}} < 1 - \frac{1}{2 x} + \frac{1}{24 x^{2}}

$1 - \frac{1}{2x} < \cos{\sqrt{\frac{1}{x}}} < 1 - \frac{1}{2x} + \frac{1}{24x^2}$

x \to + \infty

$x \to +\infty$ ,

x

$x$ , . ,

e^{- 1 / 2}

$e^{-1/2}$ . , :

lim_{x \to + \infty} {(1 - \frac{1}{2 x} + \frac{1}{24 x^{2}})}^{x} = \exp (lim_{x \to + \infty} x \ln (1 - \frac{1}{2 x} + \frac{1}{24 x^{2}})) =

$\lim_{x \to +\infty} \left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)^x = \exp\left(\lim_{x \to +\infty} x \ln\left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)\right) =$

= \exp (lim_{x \to + 0} \frac{\ln (1 - \frac{x}{2} + \frac{x^{2}}{24})}{x})

$= \exp\left(\lim_{x \to +0} \frac{\ln\left( 1 - \frac{x}{2} + \frac{x^2}{24} \right)}{x}\right)$

, . :

lim_{x \to + \infty} {(\cos \sqrt{\frac{1}{x}})}^{x} = e^{- 1 / 2} \Rightarrow lim_{x \to + \infty} {(\cos \sqrt{\frac{1}{x}})}^{x / a} = e^{- 1 / 2 a}

$\lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^x = e^{-1/2} \Rightarrow \lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^{x/a} = e^{-1/2a}$

a = \frac{1}{2}

$a = \frac{1}{2}$ .

: , , .

C. Local minimum

At what minimum step length gradient descent cannot find the minimum function

x^{4} + \cos 2

$x^4+\cos 2$ , if

x_{0} = 1

$x_0=1$ ?

Decision

, :

x_{k} + 1 = x_{k} - λ ▽ f (x_{k})

$x_k+1 = x_k - \lambda \triangledown f(x_k)$

.

— , .

▽ f (x_{k}) = 4 x_{k}^{3}

$\triangledown f(x_k) = 4x_k^3$

x_{0}

$x_0$ ,

x_{1}

$x_1$ :

x_{1} = x_{0} - λ 4 x_{0}^{3} = 1 - 4 λ

$x_1 = x_0 - \lambda 4x_0^3 = 1 - 4\lambda$

x_{1} = - 1

$x_1=-1$ ,

x_{0}

$x_0$ , . , , «» -

1

$1$

- 1

$-1$ . , ,

x_{1} = - 1 \Leftrightarrow λ = 0.5

$x_1=-1 \Leftrightarrow \lambda=0.5$ (

0

$0$ ). ,

λ

$\lambda$ .

, .

| x_{n + 1} | \leq | x_{n} | | 1 - 4 λ |

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . ,

0.5 > λ > 0 \Rightarrow | 1 - 4 λ | < 1

$0.5 > \lambda > 0 \Rightarrow |1 - 4\lambda| < 1$

:

| x_{1} | = | 1 - 4 λ | \leq 1 | 1 - 4 λ | = x_{0} | 1 - 4 λ |

$|x_1| = |1 - 4\lambda| \leq 1 |1 - 4\lambda| = x_0 |1-4\lambda|$

.

| x_{n + 1} | = | x_{n} - 4 λ x_{n}^{3} | = | x_{n} | | 1 - 4 λ x_{n}^{2} |

$|x_{n+1}| = |x_n - 4\lambda x_n^3| = |x_n| |1-4\lambda x_n^2|$ .

x_{n} < 1 \Rightarrow x_{n}^{2} < 1

$x_n < 1 \Rightarrow x_n^2 < 1$ .

| x_{n + 1} | \leq | x_{n} | | 1 - 4 λ |

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . .

, ,

| x_{n} | \leq | x_{0} | | 1 - 4 λ |^{n} = | 1 - 4 λ |^{n}

$|x_n|\leq |x_0||1-4\lambda|^n = |1-4\lambda|^n$ . ,

| 1 - 4 λ | < 1

$|1-4\lambda| < 1$ ,

| x_{n} |

$|x_n|$ . .

D. Own vector

Determine at which values of the parameter a vector

(\begin{array}{l} 1 \\ 1 \\ a \end{array})

$\left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right)$ is an eigenvector of the matrix

(\begin{array}{ccc} a & 1 & - 1 \\ 1 & 2 & - 1 \\ 0 & 0 & 1 \end{array})

$\left(\begin{array}{ccc} a & 1 & -1 \\ 1 & 2 & -1 \\ 0 & 0 & 1 \end{array}\right)$

Decision

v \neq 0

$v \neq 0$

A

$A$ ,

\exists λ

$\exists \lambda$ :

A v = λ v

$Av = \lambda v$ . :

(\begin{matrix} a & 1 & - 1 \\ 1 & 2 & - 1 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 \\ 1 \\ a \end{matrix}) = (\begin{matrix} 1 \\ 3 - a \\ a \end{matrix}) = λ (\begin{matrix} 1 \\ 1 \\ a \end{matrix})

$\begin{pmatrix} a & 1 & -1 \\ 1 & 2 & -1\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 3 - a \\ a \\ \end{pmatrix} = \lambda \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix}$

λ = 1

$\lambda = 1$ , —

a = 2

$a = 2$ , , . ,

a = 2

$a = 2$ .

E. Qualifier

At what parameter values

a

$a$ maximum determinant of the matrix inverse to this?

(\begin{array}{ccc} a & - 7 & - 3 \\ 6 & - 10 & - a^{2} \\ 0 & a & 9 \end{array})

$\left(\begin{array}{ccc} a & -7 & -3 \\ 6 & -10 & -a^{2} \\ 0 & a & 9 \end{array}\right)$

Decision

det (a) = | \begin{matrix} a & - 7 & - 3 \\ 6 & - 10 & - a^{2} \\ 0 & a & 9 \end{matrix} | = a | \begin{matrix} - 10 & - a^{2} \\ a & 9 \end{matrix} | - 6 | \begin{matrix} - 7 & - 3 \\ a & 9 \end{matrix} | = a^{4} - 108 a + 376

$\det(a) = \begin{vmatrix} a & -7 & -3 \\ 6 & -10 & -a^2 \\ 0 & a & 9 \\ \end{vmatrix} = a \begin{vmatrix} -10 & -a^2 \\ a & 9 \\ \end{vmatrix} - 6 \begin{vmatrix} -7& -3 \\ a & 9 \\ \end{vmatrix} = a^4 - 108a + 376$

{det}^{'} (a) = 4 a^{3} - 108 = 0 \Leftrightarrow a = 3

$\det'(a) = 4a^3 - 108 = 0 \Leftrightarrow a = 3$

, , , , ,

det (a)

$\det(a)$ ,

det (a) \geq det (3) > 0

$\det(a) \geq \det(3) > 0$

a = 3

$a = 3$ . ,

det (A^{- 1}) = det (A)^{- 1}

$\det(A^{-1}) = \det(A)^{-1}$ , ,

a = 3

$a = 3$ .

F. Projections

Given points

B (1, 2, - 3)

$B(1,2,−3)$ and

C (2, 2, 1)

$C(2,2,1)$ as well as the plane

α

$\alpha$ :

2 x - 2 y + z = 0

$2x−2y+z=0$ and

β

$β$ :

- x + 2 y + 3 z = 0

$−x+2y+3z=0$ . Find the coordinates of the point

A

$A$ if it is known that its orthogonal projection onto

α

$\alpha$ coincides with the projection of the point

B

$B$ but on

β

$\beta$ - with point projection

С

Decision

A = (x, y, z)

$A = (x, y, z)$ ,

B

$B$ , ,

B

$B$ . , ,

α

$\alpha$

{\bar{n}}_{1} (2, - 2, 1)

$\overline{n}_1(2, -2, 1)$ . :

{\begin{cases} x = 2 t_{1} + 1 \\ y = - 2 t_{1} + 2 \\ z = t_{1} - 3 \end{cases}

$\begin{cases} x = 2t_1 + 1\\ y = -2t_1 + 2\\ z = t_1 - 3\\ \end{cases}$

A

$A$ ,

C

$C$

β

$\beta$ . :

{\bar{n}}_{2} (- 1, 2, 3)

$\overline{n}_2(-1, 2, 3)$ , :

{\begin{cases} x = - t_{2} + 2 \\ y = - 2 t_{2} + 2 \\ z = 3 t_{2} + 1 \end{cases}

$\begin{cases} x = -t_2 + 2\\ y = -2t_2 + 2\\ z = 3t_2 + 1\\ \end{cases}$

t_{1}

$t_1$

t_{2}

$t_2$ , :

{\begin{cases} 2 t_{1} + 1 = - t_{2} + 2 \\ - 2 t_{1} + 2 = 2 t_{2} + 2 \end{cases} \Leftrightarrow {\begin{cases} 3 = t_{2} + 4 \\ - 2 t_{1} + 2 = 2 t_{2} + 2 \end{cases} \Leftrightarrow {\begin{cases} t_{2} = - 1 \\ t_{1} = 1 \end{cases}

$\begin{cases} 2t_1 + 1 = -t_2 + 2\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} 3 = t_2 + 4\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} t_2 = -1\\ t_1 = 1\\ \end{cases}$

, ,

A (3, 0, - 2)

$A(3, 0, -2)$ , .

G. Domino

In the distant constellation of Tau Ceti, on each half of the knuckle of dominoes is from

0

$0$ before

N

$N$ points, and for each pair of numbers

(a, b)

$(a,b)$ such that

a

$a$ and

b

$b$ whole from

0

$0$ before

N

$N$ , there is exactly one domino containing both of these numbers. The space tourist flew in and picked up an inverted knuckle at random. At what

N

$N$ the mathematical expectation of the module of the difference in the number of points on one and the other half of this domino will be equal

2

$2$ ?

Decision

ξ

$\xi$ ,

Ω

$\Omega$

ξ (Ω)

$\xi(\Omega)$ . :

E (ξ) = \sum_{k \in ξ (Ω)} k Pr [ξ = k] = 2

$E(\xi) = \sum_{k \in \xi(\Omega)} k \Pr[\xi = k] = 2$

A_{k}

$A_k$ — ,

K

$K$ ,

Pr [ξ = k] = \frac{| A_{k} |}{| Ω |}

$\Pr[\xi = k] = \frac{|A_k|}{|\Omega|}$ .

| Ω |

$|\Omega|$ , :

\sum_{k \in ξ (Ω)} k | A_{k} | = 2 | Ω |

$\sum_{k \in \xi(\Omega)} k |A_k|= 2 |\Omega|$

| Ω |

$|\Omega|$ . -, . -, , . ,

| Ω | = n + 1 + \frac{n (n + 1)}{2}

$|\Omega| = n + 1 + \frac{n(n + 1)}{2}$

.

. , 0

n

$n$ .

k

$k$ ?

n - k + 1

$n - k + 1$ : —

(0, k), (1, k + 1), \dots, (n - k, n)

$(0, k), (1, k + 1), \ldots, (n - k, n)$ . :

\sum_{k \in ξ (Ω)} k | A_{k} | = \sum_{k = 0}^{n} k (n - k + 1) = (n + 1) \sum_{k = 0}^{n} k - \sum_{k = 0}^{n} k^{2} = \frac{n (n + 1)^{2}}{2} -

$\sum_{k \in \xi(\Omega)} k |A_k| = \sum_{k = 0}^n k(n - k + 1) = (n + 1)\sum_{k = 0}^n k - \sum_{k = 0}^n k^2 = \frac{n(n + 1)^2}{2} -$

- \frac{n (n + 1) (2 n + 1)}{6} = \frac{n (n + 1) (n + 2)}{6}

$- \frac{n(n + 1)(2n + 1)}{6} = \frac{n(n + 1)(n + 2)}{6}$

\frac{n (n + 1) (n + 2)}{6} = (n + 1) (n + 2)

$\frac{n(n + 1)(n + 2)}{6} = (n + 1)(n + 2)$

n > 0

$n > 0$ , ,

n = 6

$n = 6$ .

H. Exam

Two friends decided to go together for exams at the SHAD and agreed to meet at the entrance from 14:00 to 15:00, but did not agree on what time. The moment of arrival of each of them is distributed evenly over this period of time, but the friends are impatient, so after 15 minutes of waiting they despair to wait and come in alone. It is known that they met.

Find the likelihood that both came before 14:45.

Decision

, , . , 60x60. x , y — .

« » . « 14:45» 2 . , , , , « 14:45» , « » 3 . ,

\frac{5}{7}

$\frac{5}{7}$ .

I. Random variable

Distribution density of a random variable

ξ

$\xi$ is equal to

p (x) = \frac{1}{\sin x}

$p(x)=\frac{1}{\sin x}$ at

x

$x$ from

π / 2

$\pi/2$ before

2 \arctan e

$2 \arctan e$ and zero for all the others

x

$x$ .

Find a value that this random variable does not exceed with probability

\frac{1}{2}

$\frac{1}{2}$ .

Decision

Pr (ξ \leq x) = \int_{π / 2}^{x} \frac{d t}{\sin t} = \int_{1}^{\tan x / 2} \frac{d u}{u} = \ln \tan \frac{x}{2}

$\Pr(\xi \leq x) = \int\limits_{\pi/2}^x \frac{dt}{\sin{t}} = \int\limits_{1}^{\tan{x/2}} \frac{du}{u} = \ln{\tan{\frac{x}{2}}}$

\ln \tan \frac{x}{2} = \frac{1}{2} \Leftrightarrow \tan \frac{x}{2} = e^{1 / 2} \Leftrightarrow x = 2 \tan^{- 1} e^{1 / 2}

$\ln{\tan{\frac{x}{2}}} = \frac{1}{2} \Leftrightarrow \tan{\frac{x}{2}} = e^{1/2} \Leftrightarrow x = 2 \tan^{-1}{e^{1/2}}$

J. Find the mean

Condition

	2
	256Mb
	input.txt
	output.txt

. : n

a_{0}, a_{1}, \dots, a_{n - 1}

$a_0, a_1, \dots, a_{n-1}$ .

- !

l r. .

l

$l$

r

$r$ :

\sqrt[r - l + 1]{a_{l} \cdot a_{l + 1} \cdot \dots \cdot a_{r}}

$\sqrt[r-l+1]{a_{l} \cdot a_{l+1} \cdot \ldots \cdot a_{r}}$

n

$n$ (

1 \leq n \leq 300 000

$1 \leq n \leq 300 000$ ).

n

a_{i}

$a_i$ (

0.01 \leq a_{i} \leq 100

$0.01 \leq a_i \leq 100$ ) .

q

$q$ (

1 \leq q \leq 100 000

$1 \leq q \leq 100 000$ ) — .

q

$q$

l_{i}

$l_i$

r_{i}

$r_i$ (

0 \leq l_{i} \leq r_{i} < n

$0 \leq l_i \leq r_i < n$ ) —

i

$i$ - .

6 .

.

1


8 79.02 36.68 79.83 76.00 95.48 48.84 49.95 91.91 10 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 1 7 2 7	79.020000 53.837288 61.391865 64.756970 69.986085 65.913194 63.352986 66.369195 64.735454 71.164108

2


1 1.00 1 0 0	1.000000

3


8 1.34 1.37 1.40 1.44 1.91 1.95 1.96 1.97 5 1 4 2 7 4 6 0 3 2 6	1.515518 1.752724 1.939879 1.387008 1.712233

x y = e^{\ln x + \ln y}

$xy = e^{\ln x + \ln y}$ . .

Decision

О (1)

$(1)$ ,

O (1)

$O(1)$ .

. sums,

s u m s [i] = a [0] + a [1] + \dots + a [i]

$sums[i] = a[0] + a[1] + \dots + a[i]$ .

s u m s [i] = s u m s [i - 1] + a [i]

$sums[i] = sums[i - 1] + a[i]$ ,

O (n)

$O(n)$ .

l

$l$

r

$r$ —

s u m s [r] - s u m s [l - 1]

$sums[r] - sums[l - 1]$ . ,

r - l + 1

$r - l + 1$ .

O (1)

$O(1)$

O (n)

$O(n)$ .

. , , , . , ,

e

$e$ . ,

\ln ((a [l] \cdot . . . \cdot a [r])^{\frac{1}{r - l + 1}}) = \frac{\ln a [l] \cdot \dots \cdot a [r]}{r - l + 1} = \frac{\ln a [l] + \dots + \ln a [r]}{r - l + 1}

$\ln ((a[l] \cdot ... \cdot a[r])^{\frac{1}{r - l + 1}}) = \frac{\ln a[l] \cdot \dots \cdot a[r]}{r - l + 1} = \frac{\ln a[l] + \dots + \ln a[r]}{r - l + 1}$ ,

О (1)

$(1)$ .

: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f

K. Delete last

Condition

	2
	256Mb
	input.txt
	output.txt

a

$a$

n

$n$ . .

, .

, , .

n

$n$ (

1 \leq n \leq 300 000

$1 \leq n \leq 300 000$ ).

n

$n$

a_{i}

$a_i$ (

0 \leq a_{i} \leq 1 000 000 000

$0 \leq a_i \leq 1 000 000 000$ ).

m

$m$ (

0 \leq m < n

$0 \leq m < n$ ) — , .

m

$m$ — , . , , .

1


10 1 1 5 2 4 3 3 4 2 5	5 1 5 2 4 3

2


1 1000000000	0

3


10 1 2 3 3 2 1 4 1 2 0	5 1 2 3 2 1

Decision

unordered_set (C++) / HashSet (Java) / set (Python), . , , . , . , -. reverse

O (n)

$O(n)$ . -

О (1)

$(1)$ ,

O (n)

$O(n)$ .

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

L. Bulletin board

Condition

	3
	256Mb
	input.txt
	output.txt

, .

W \times H

$W × H$ , a b. , . , .

. , , . , .

.

(0, 0)

$(0, 0)$ , —

(W, H)

$(W, H)$ . .

, .

W

$W$ ,

H

$H$

a

$a$ ,

b

$b$ (

1 \leq W

$1 \leq W$ ,

H \leq 100 000

$H \leq 100 000$ ,

1 \leq a \leq W

$1 \leq a \leq W$ ,

1 \leq b \leq H

$1 \leq b \leq H$ ).

n

$n$ (

0 \leq n \leq 100

$0 \leq n \leq 100$ ) — .

n

$n$

(x_{l d}, y_{l d})

$(x_{ld}, y_{ld})$

(x_{r u}, y_{r u})

$(x_{ru}, y_{ru})$ (

0 \leq x_{l d} < x_{r u} \leq W, 0 \leq y_{l d} < y_{r u} \leq H

$0 \leq x_{ld} < x_{ru} \leq W, 0 \leq y_{ld} < y_{ru} \leq H$ ). , .. .

(x_{l d}, y_{l d})

$(x_{ld}, y_{ld})$

(x_{r u}, y_{r u})

$(x_{ru}, y_{ru})$ , .

a

$a$ (,

b

$b$ ). .

.

, .

1


11 8 2 7 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	9 0 11 8

2


11 8 7 3 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	4 0 11 3

3


11 8 4 4 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	7 4 11 8

Decision

, . ,

W * n

$W * n$ .

x

$x$ (

0

$0$

W - a

$W - a$ ), . ,

x

$x$

x + a

$x + a$ , . , «»

x

$x$

x + a

$x + a$ ,

y

$y$ - . ,

(y_{1}, y_{2})

$(y_1, y_2)$ ,

y_{1}

$y_1$

y_{2}

$y_2$ —

y

$y$ - , .

y_{2}

$y_2$ —

y_{1}

$y_1$ .

,

(0, 0)

$(0, 0)$

(h, h)

$(h, h)$ , . , , , . , , . , , .

.

O (W * n * \log n)

$O(W * n * \log n)$

O (n)

$O(n)$ .

: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7

Full analysis of the first part of the exam in SHAD 2020

A. Local minimum

B. Limit

C. Local minimum

D. Own vector

E. Qualifier

F. Projections

G. Domino

H. Exam

I. Random variable

J. Find the mean

1

2

3

K. Delete last

1

2

3

L. Bulletin board

1

2

3

More articles: