### riadwaw's blog

By riadwaw, history, 2 years ago, How to solve K? Comments (43)
 » How to solve F?
•  » » Consider s as combination of bits. Next calculate contribution of each (s[i]*2^i)^2 and (2*SI*sj*2^(i+j)) separately. And some binomial formula to compute these probabilities
•  » » » What does Si stand for?
•  » » » » ith bit of s
•  » » » » » And then one should just take the sum or difference?
•  » » » We wrote O(N*30*30) dynamic , but it gave TLE. Did you calc that probabilities in O(1)?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   I had to manually unroll loop in my N*30*30 solution to make it pass
•  » » » » Our solution passes from the first attempt, probably the only optimization which was needed to store only two levels of dp. code
•  » » » » » what time is reported for this solution?
•  » » » » » » 0.8
•  » » » » The subproblem "find the probability that you select an odd number of balls if you pick each ball independently with prob p" has a solution: $\frac{1 - (1 - 2p)^{balls}}{2}$
•  » » » » I calc each probability in O(n) time but my dynamic is O(1). I count how many numbers have forms 01, 10 and 11 and then apply all numbers of the same type simultaneously using O(n) precalculated probabilities. So my dynamic has only 3 steps. Counting is much faster than dynamics even though they are both O(n).
 » How to solve A?
•  » » Use dp[i][j] — minimal length of a palindrome according to positions in regex.
•  » » » What $i$ and $j$ mean here?Is it $dp[left][right]$ — minimal length of palindrome that fits pattern substring $[left; right]$?
•  » » » » Yes. We should consider several cases — whether left and right symbol are *, ? or usual letters. And case of one symbol of course.
 » How to solve C and E?
•  » » C: one can see that a sufficiently large power of two satisfies the matrices equality condition. One can also see that every such number is divisible by $k$ hence $k$ is a power of two as well. Now we try each power of two until we find a good one.The easiest way to check the board state after $k$ operations is to consider inverse operations: before matrix $A$ the was matrix $B$ such that $B_{ij} = A_{ij} + A_{(i-1)j} + A_{i(j-1)} + A_{(i-1)(j-1)}$, and for any $k$ which is a power of two a board after $k$ inverse operations looks the same but every $1$ becomes $k$.
•  » » » Also the assumption that $k$ has to be a power of two could be freely believed in since there was no sample test with answer $42$ :)
•  » » E: for each b up to 512 create vector x_i -- number of times i appears in the array a. Now multiply all pairs b_i*b_j as polynomials and write to b_(i xor j). Now we have some representation of all pairs (a_i + a_j, b_i xor b_j) Now do it one more time and for each pair add to the answer
•  » » » My solution was the same as this one but it returns TL.But from what i understand this is about $512 \cdot 512 \cdot 2000 \cdot lg2000$ isn't this a bit much?
•  » » » » You can avoid doing most of FFTs and inverse FFTs, because you can add polynomials in FFT. form
•  » » E: we'll find cnt[x][y] being equal to the number of sets of 4 indices where sum of $a$'s is $x$ and xor of $b$-s is $y$. It can be done by a Walsh-Hadamard transform with NTT inside.
•  » » 2 years ago, # ^ | ← Rev. 2 →   C: There is another solution $DP[i][j]$ — answer for submatrix $((0,0), (i, j))$ transitions: let $x = lcm(DP[i - 1][j], DP[i][j - 1])$ clearly to make submatrix(i, j) equal to initial we must do $x \cdot k$ steps, where $k$ is integer and $k > 0$ But if have done $x$ steps and $val[i][j] != initial\ val[i][j]$ than next $x$ steps $val[i][j]$ will be simply xored, than $DP[i][j] = x$ or $DP[i][j] = 2 \cdot x$ here we can notice that DP is always power of two, than we will store only powers of two $x = max(DP[i - 1][j], DP[i][j - 1])$ Thus transition is $DP[i][j] = x$ or $DP[i][j] = x + 1$ but how to determine what transition to make $x$ or $(x + 1)$. To make choice we need to calculate $f(i, j, 2^x)$ — value of $(i, j)$ element after $2^x$ steps. I think it's hardest part of my solution. $f(i, j, k) = \sum\limits^{i}_{x = 0} \sum\limits ^{j}_{y=0} f(x, y, k - 1)$ So if we recursively open such sums we will reduce to $f(i, j, k) = \sum\limits^{i}_{x = 0} \sum\limits ^{j}_{y=0} f(x, y, 0) \cdot ways(x, y, i, j, k)$ where $ways(x, y, i, j, k)$ is how many times element $(x, y)$ will occurs in sum for $f(i, j, k)$ It looks like number of ways from $(x, y, 0)$ to $(i, j, k)$ in 3D grid but with some limitations of making way. let $dx = i - x$ and $dy = j - y$ Actually $ways(x, y, i, j, k)$ equals to numbef of ways to make two sequences of size k $a_i > 0$ and $b_i > 0$ such as $\sum a_i = dx$ and $\sum b_i = dy$ So it is well known combinatorics problem $ways(x, y, i, j, k) = C_{dx + k - 1}^{k - 1} \cdot C_{dy + k - 1}^{k - 1}$ Of course every calculation must be computed by (mod 2), and I just noticed that $C_{n + 2^x - 1}^{2^x - 1} (mod\ 2) = 1\ \ if\ \ n\ |\ 2^x\ \ else\ \ 0$ This immediately gives you solution $O((n \cdot m) ^ 2)$ Optimization to $O(n \cdot m \cdot \log(n \cdot m))$ is easier task. Implementation
 » 2 years ago, # | ← Rev. 2 →   I've already told OP how to solve K, but in case anyone else wonders:K: We assume that wlog $w\leq b$ and we don't need any knights. Consider two cases. $w\leq 15$. We have a predetermined harcoded set of $14$ cells with the same color such that if we put kings at these cells, they will attack all other cells. We fill the board in the following way: place a white queen at each of these $14$ cells (but if $w = 15$ then we place a queen at any other cell with the same color), place a black rook at each of the other cells with the same color, place black bishops at all other cells, remove some black figures from the bottom until there are $b$ black figures on the board. Now all black figures are under attack, and none of the white queens is. While the number of white attacked figures is less than $w$, we try to replace next black bishop by a black rook. It may be that we should consider the same bishop several times, but in the end it seems to be possible to replace some of them greedily so that exactly $w$ queens are under attack. $w\geq 16$ which means that $b\leq 3w$, in this case we divide the board into $2\times2$ squares, and in each square we place some number $x$ of black and $y$ of white queens so that either $x = y = 0$ or $x, y\neq 0$; $x + y\leq 4$, sum of all $x$ is $b$ and sum of all $y$ is $w$. It turns out that it's always possible to do so, and it's obvious that all placed figures will be under attack. Our 14 cells Q . . . . . Q Q Q Q Q . Q Q Q Q . . . . . . Q . Q . . Q . . Q . 
 » Is there a more clever way to solve problem I than to simulate all possible operations with some memorization?
•  » » Well, we precalculated answers for all numbers below $10^7$ and this is all memoization we used, now the number of operations is about $10^7 + t\cdot11\cdot10\cdot9\cdot8\cdot7$.
 » If $w\ge 9$ and $b\ge 9$, place queens like this: q..q..q. .Q..Q..Q ........ q..q..q. .Q..Q..Q ........ q..q..q. .Q..Q..Q Fill the rest with any $w-9$ white figures and $b-9$ black figures.If $64-9=55\ge b\ge w, w < 9$. Use this as a template: rbrrbrrb bQbbQbbQ rbrrbrrb rbrrbrrb bQbbQbbQ rbrrbrrb rbrrbrrb bQbbQbbQ  Remove some black figures to leave only $b$ black figures on board and leave all white queens. If $b\ge 9$, don't remove any bolded rooks. If $b < 9$, remove all black figures and add bolded rooks top to bottom, left to right. Replace $w$ bolded rooks with bishops. Replacement with bishops should be top to bottom, left to right, so one replacement adds only one white queen.
 » How to solve J?
•  » » DFS the tree to get the DFS order. A vertex's subtree is an interval $[l_i,r_i]$ of this sequence. When two intervals $[l_1,r_1],[l_2,r_2]$ have intersection, this pair is counted into the answer. This means $l_1\leq r_2$ and $r_1\geq l_2$.Consider a huge binary matrix $g_{i,j}$, where $g_{i,j}$ denotes whether interval $[l_i,r_i]$ intersects with interval $[l_j,r_j]$. The answer of query $[l,r]$ is the sum of a $g$'s submatrix.Brute force solution runs in $O(n^2)$, but we can easily speed it up using bitset. My bitset solution got OK in 1.8 seconds.
•  » » » I don`t understand yet, how to calculate a sum in a submatrix quickly?
•  » » » » We can precompute $s_{x,y}$ denoting $\sum g_{i,j}(i\leq 32x,j\leq 32y)$ and $h_{x,y}$ denoting $\sum g_{x,j}(j\leq 32y)$, this needs $O(\frac{n^2}{32})$.Assume we want to calculate $\sum g_{i,j}(i\leq x,j\leq y)$. First set $ans=s_{\lfloor\frac{x}{32}\rfloor,\lfloor\frac{y}{32}\rfloor}$, then we just need to sum up no more than $32\times 2$ elements in $h$ and do no more than $32^2$ brute force check operations. A query costs $O(32^2)$.
•  » » 2 years ago, # ^ | ← Rev. 4 →   I believe $O((n + q) \sqrt n \log n)$ passes but my coding abilities are too low to squeeze it.Let's do sqrt decomposition on positions, we will learn to ask $get\_subtree(v, l, r)$ and have $a[i][j]$ precalced — the number of vertices from the $i$-th block that have $j$ in the subtree.The first part can be computed with persistent segtree which stores 1 at position $i$ if vertex $i$ is in the subtree. Let's build it from the bottom using small-to-large in $O(n \log^2 n)$.The second part can be computed with another persistent segtree which stores 1 at position $i$ if vertex $i$ is the ancestor. This is built from the top in $O(n \log n)$. After that we'll iterate through blocks, through all vertices and set $a[i][j] = get\_ancestors(j, i * BL, (i + 1) * BL)$. This is $O(n \sqrt n \log n)$.Finally query works in $O(\sqrt n \log n)$ with this.
•  » » » Too many persistent data structures :)Let's do a bit different sqrt-decomposition. Divide vertices into blocks of size $B$, for each block $[l_i, r_i]$ calculate vector $x_i = (x_{i1}, x_{i2}, \ldots, x_{in})$ where $x_ij$ is the number of vertices of block $[l_i, r_i]$ such that $j$ is their ancestor. Store this vector as a Fenwick tree allowing us to query it in $O(\log n)$.Now in order to answer query $[l, r]$, first process all blocks that fit completely inside range $[l, r]$, for each block make a range query for its Fenwick tree for range $[l, r]$.Now we need to somehow deal with $\leq 2B$ vertices uncovered with blocks. For each vertex we need to find out how many of its ancestors is within range $[l, r]$. Note that in the given tree vertex indices decrease as we go from any vertex to the root, so for each vertex $v$ we consider, only some prefix of its path to the root belongs to $[l, r]$. Find the borderline ancestor using binary lifting (i.e. store parents of order $1, 2, 4, 8, ...$ for each vertex).So, we got a solution in $\Theta(n / B \log n + B \log n) \geq \Theta (\sqrt{n} \log n)$ for $B = \sqrt{n}$ which uses $n^2 / B$ memory.
•  » » » » Note that in the given tree vertex indices decrease as we go from any vertex to the root. Was this true? The problem statement didn't specify it, but the sample satisfies it. We couldn't tell. You can do this in the general case using a very simple persistent segment tree, no need for merge-smaller-into-bigger.Also, you can preprocess the $x_i$ and compute prefix sums in $O(n^2 / B)$ time to get $O(1 + B \log n)$ query time. That way, you can get $O(n \sqrt{n \log n})$ runtime overall.
•  » » » » » The subtree values can be calculated without small-to-large?
•  » » » » » » We're calculating the segment tree of the path to root, not of the subtree. You calculate the subtree part (the $x_i$ above) in $O(n^2 / B)$ total time, so no segtree at all.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   Yeah, that's obvious. I thought maybe there is some cool idea to do subtree one in $O(n \log n)$. The ancestor one I did without small-to-large, of course.
•  » » » » » » » » Yeah, it turns out that it's better to drop the segment tree entirely because you have to get/store the values for each block anyways.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   Was this true? Considering the fact I got my OK, apparently it was. But I agree that there is nothing in the statement that makes this assumption legitimate, so I can consider myself to be lucky bastard :) You can do this in general case using a very simple persistent segment tree; Yes, it was exactly my initial intent, but during the implementation I somehow switched to thinking that the tree is monotonic and decided to take a shorter route. Considering the fact we solved two last problems during last 20 minutes, it might have been a crucial decision.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   BTW, this problem can be solved in $O((n+q)\sqrt{n})$.First DFS the tree to get the DFS order. A vertex's subtree is an interval $[l_i,r_i]$ of this sequence. $A$ is $B$'s ancestor means $l_A\leq l_B\leq r_A$.Divide the $n$ indices into $O(\sqrt{n})$ blocks, and precompute $s_{i,j}$ denoting the number of vertices $x$ satisfying $x$ is in the first $i$ blocks and $l_x\leq j$. This precompute is a simple 2D prefix sum, and we can do it in $O(n\sqrt{n})$. When we want to calculate the number of vertices within $x$'s subtree, the answer is just equal to $s_{t,r_x}-s_{t,l_x-1}$.Similarly, if we mark $tmp_{l_x}=1$ and $tmp_{r_x}=-1$, the number of ancestors of $y$ is just equal to $\sum_{i\leq l_y} tmp_i$. It is very similar to the subtree query, so we just talk about subtree query below.We can also precompute $g_{l,r}$ denoting the answer of block $l$ to block $r$.Now for a query, we need to deal with several vertices in two uncovered blocks $L$ and $R$. Their contributions to answer are below: Contribution within $L\cup R$. Contribution between $L$ and blocks $[L+1,R-1]$. Contribution between $R$ and blocks $[L+1,R-1]$. 2 and 3 can be easily calculated by iterating vertex $x$ in $L$ or $R$ and count the number of ancestors of $x$ and number of vertices within $x$'s subtree using $s$ in $O(1)$. So it's not hard to calculate 2 and 3 in $O(\sqrt{n})$.Next we hope to calculate 1. We can solve it by doing some sorts in $L\cup R$. But if we sort each block in advance and just do merging in each query, we can get rid of sort in queries. Thus we can also calculate 1 in $O(\sqrt{n})$.
 » How to solve B?
•  » » Regard all $a_i$ as strings and append character 'z' to each string. Then add enough zeroes to the set $S$ to ensure $|S|=\sum |a_i|$.Assume the final answer is $x_1,x_2,\dots,x_n$. Let's assign digits in the set from $0$ to $9$ one by one. Always assign the current digit to the current highest bit of $x_k$, where $a_k$ is the string with the smallest lexicographical order. Assume the highest bit of $a_k$ is $A$, and now we are assigning digit $B$. If $B>A$ then there is no solution. If $B=A$ then we just erase the highest bit of $a_k$. If \$B