rss rss hh new
rss_rss_hh_new

 -

rss_rss_hh_new

 - e-mail

 

 -

LiveInternet.ru:
: 17.03.2011
:
:
: 51

:


. 2017

, 27 2017 . 14:45 +

. 2017 . 25 . 2013, 2014 2015 . , . : 300 , 150 , 90 .




2017 4840 . 60% . , , . , , , .


.


A.


: (, ).


: : : :
5 (13 Java) 512

, . , , , .


$n$ , $1$ $n$. $i$ $h_i$, . , $s$ $t$. $m$ , .


, $u$ $v$, , $h_u - h_v$. , $v_1, v_2, \ldots, v_k$, , $h_{v_1} - h_{v_2}, h_{v_2} - h_{v_3}, \ldots, h_{v_k} - h_{v_{k - 1}}$.


, , , , . , $x$ $1$ $n - 1$ $s$ $t$, $x$.



$n$, $m$, $s$ $t$ ($2 \leq n \leq 100\,000$, $1 \leq m \leq 200\,000$, $1 \leq s, t \leq n$, $s \ne t$) , , .


$n$ $h_1, h_2, \ldots, h_n$ ($0 \leq h_i \leq 100\,000$) , .


$m$ , . $i$- $u_i$ $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$), , $i$- $u_i$ $v_i$. , , $u_i$ $v_i$, $s$ $t$.



$n - 1$ , $i$- $s$ $t$, $i$. $i$ $i$, $-1$.



4 4 2 4
3 4 2 1
2 4
2 1
1 3
3 4		 3
1
1
3 2 1 3
3 2 1
1 2
1 3
 2
-1
5 10 1 5
8 6 4 3 1
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
 7
3
2
1


. $3$, $1$. $3$, $2$, $1$, $3$ $4$, c $1$. $x = 2$ $3$, $2$.


A


, , . (, ) .


. : $x$ , $(u, v)$, $h_u - h_v \geq x$ $s$ $t$, . $O(mC)$, $C = h_s - h_t + 1$. : $d(v, len)$ $len$ $v$ $t$. $d(v, len)$ $(v, u)$ $d(v, len) = max(d(v, len), min(d(u, len - 1), h_v - h_u))$. $O(nm)$.


, , , . , $x$ , $C / x$, , $y$ , $C / y$. $k = \sqrt{C}$. $s$ $t$ , , $k$. , $c \leq k$, $len \leq k$. : $O(m\sqrt{C})$. , $O(m)$ .



B.


: (, , ).


: : : :
4 512

: , , .


, , , , . . , .


$n$ , $n - 1$ . $1$ $n$, $1$- . , , , , , .


, . , , $i$, $a_i$ . , . .


. . $i$, $j$ $t$ , $t$ $j$. , . .


, - , , , . .



$n$ ($1 \leq n \leq 200\,000$) .


$a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^6$), $a_i$ , $i$.


$n - 1$ , $u_i$ $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$) .



, , . $-1$.



7
0 3 0 2 4 3 3
1 2
1 3
3 4
1 5
5 6
6 7
 9
4
0 1 1 2
1 2
2 3
1 4
 -1


, , :


  • 2 4, 4, .
  • 3 2, 2, .
  • 2 5, 5, 2 .
  • 2 7, 7, 1 .

9 .


B


, . , , , 1 .


, , 1 , : $i$ $a_i$ , , .


, - . , . , ( ), . .


, , . , , , , , , .


, , .. , , , .


, ( ) $2n - 2$ ( ), , , , , . , , ( , ), . , .


$E$ , $B$ , $s(e)$ $e \in E$ , , $e$ ( , $b \in s(e)$ , $e$ $e$ $b$). , , $A \subseteq E$ $A$ , $E$:

$|A| \leq \left| \bigcup\limits_{e \in A} s(e)\right|$


$s(A)$. , , , $A$. , , .

-, $A$ , $A$ , $e_1$ $e_2$, "" , $s(A)$ , , $A$, . , , , $A$ $E$, , , . $(1)$.

, . $e \in A$, $E$ , $e$ , $e$ ( , , ). , , , .


, $A$ $s(A)$. $A$ , , , $s(A)$ . , $A$ ( , $|A| > |s(A)|$), $A$ , , $A$ .


, , $A$ : $2n - 2$ , "" $e$, , $e$ $e$. , , , ( ). $e$ $(2_e)$.


$(1)$ . $(2_e)$ , .


, . , . , $t$, , , $t$ $1$. $1$, - , $t$ $1$.


, . , , - , $(1')$: , , , . , $2n - 2 - depth(t)$ , , $t$: $depth(t) \geq 2n - 2 - |B|$ (, , $2n - 2 \leq |B|$).


, , , - , - . , $e$ , , ( , ). $e$ , , $t$ $e$ ( ), , , $e$ , $e$. , $depth(lca(e, t))$, $lca(e, t)$ $e$ $t$ $1$.


, :


$ 2n - 2 - depth(t) \leq |B| \quad (1') $


, :


$ |edgesBelow(e)| + 1 \leq |buttonsBelow(e)| \quad (2_{e\downarrow}') $


, :


$ |edgesAbove(e)| + 1 - depth(lca(e, t)) \leq |buttonsAbove(e)|~\text{}~t~\text{ }~e \quad (2_{e\uparrow}') $


$(2_{e\downarrow}')$ , $t$. $t$. $(1')$, , , $t$ , , $2n - 2 - |B|$. $(2_e')$, , $t$ : , $(2_{e\uparrow}')$ $depth(lca(e, t))$, , $t$ $e$. , $t$ ($|edgesAbove(e)| + 1 - |buttonsAbove(e)|$)- $s$ $e$, .


, "$t$ " , , , .


, , $(1')$, . .



C. ,


: (, , ).


: : : :
3 512

, . , , , (, , - ), , , . , , .


, $n$ , $1$ $n$, $m$ $(u_{1}, v_{1}), (u_{2}, v_{2}), \ldots, (u_{m}, v_{m})$. $n$ $x_1, x_2, \ldots, x_n$, $x_1 + \ldots + x_n = 1$. :


$\lambda = \sum \limits_{i=1}^{m} \min\{x_{u_i}, x_{v_i}\}$


, $\lambda$. , $A \subseteq \{1, 2, \ldots, n\}$, $\frac{|E(A)|}{|A|} \geq \lambda$, $E(A) = \{(u_i, v_i)~\mid~u_i, v_i \in A\}$.



$n$ $m$ ($1 \leq n \leq 200\,000$, $0 \leq m \leq 200\,000$), .


$n$ $x_1, x_2, \ldots, x_n$ ($x_i \geq 0$, $x_1 + \ldots + x_n = 1$), .


$i$- $m$ $u_i, v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), , $i$- . , .


, , .



$k$ ($1 \leq k \leq n$) $A$.


$k$ $d_1, d_2, \ldots, d_k$ , $\lambda$.


, , $\lambda - 10^{-7}$. . , .



4 4
0.2 0.1 0 0.7
1 2
2 3
3 1
3 4
 3
1 2 4
5 6
0.25 0 0.25 0.25 0.25
2 1
1 3
3 5
5 4
4 1
1 5
 4
1 5 3 4


: $\lambda = \min\{0.2, 0.1\} + \min\{0.1, 0\} + \min\{0, 0.2\} + \min\{0, 0.7\} = 0.1 + 0 + 0 + 0 = 0.1$


, $1$, $2$ $4$, $(1, 2)$, $1/3 > 0.1$.


:


$\begin{eqnarray} \lambda = \min\{0, 0.25\} + \min\{0.25, 0.25\} + \min\{0.25, 0.25\} + \min\{0.25, 0.25\} + \min\{0.25, 0.25\} + \min\{0.25, 0.25\} \nonumber \\ = 0 + 0.25 + 0.25 + 0.25 + 0.25 + 0.25 = 1.25 \nonumber \end{eqnarray}$


, $1, 5, 3, 4$, 5 $(1, 3), (3, 5), (5, 4), (4, 1), (1, 5)$, $5/4 = 1.25$.


C


: , $x_i$ ( , ). , , , , - $x_i$ .


. $A(t) = \{v~\mid~x_v \leq t\}$. , $A(t)$, , , - $x_i$ $\lambda$. .


, , $E(t) = E(A(t)) = \{(u, v)~\mid~x_u \leq t, x_v \leq t\}$. $f(t) = |E(t)| - \lambda |A(t)|$. , $[0, M)$ ( , $t$ $A(t)$, $\frac{|E(t)|}{|A(t)|}$ $\lambda$).


$M$ $x_i$. $\int\limits_{0}^{M} f(t) dt < 0$. :


$\begin{eqnarray} \int\limits_{0}^{M} f(t) dt = & \int\limits_{0}^{M} |E(t)| - \lambda \int\limits_{0}^{M} |A(t)| \nonumber \\ = & \int\limits_{0}^{M} \sum\limits_{(u, v) \in E} \mathbf{1}\{x_u \leq t, x_v \leq t\}~dt - \lambda \int\limits_{0}^{M} \sum\limits_{v=1}^{n} \mathbf{1}\{x_v \leq t\}~dt \nonumber \\ = & \sum\limits_{(u, v) \in E} \int\limits_{0}^{M} \mathbf{1}\{x_u \leq t, x_v \leq t\}~dt - \lambda \sum\limits_{v=1}^{n} \int\limits_{0}^{M} \mathbf{1}\{x_v \leq t\}~dt \nonumber \\ = & \sum\limits_{(u,v) \in E} \min\{x_u, x_v\} - \lambda \sum\limits_{v=1}^n x_v \nonumber \\ = & \lambda - \lambda = 0 \nonumber \end{eqnarray}$


, , , $[0, M)$ $f(t) > 0$, .


, : $x_i$, . $\lambda$, . $O(n \log n + m)$.



D.


: ()


: : : :
2 512

$n$ , $1$ $n$. : , . , , .


. , - , - . , . , - , .


:  

— — : [1] []
 

:
: 

: ( )

:

  URL