Codeforces Round #326 (Editorial)
Difference between en1 and en2, changed 116 character(s)
### [problem:588A]Div.2 A (Author: [user:Haghani,2015-10-01]) ↵

Idea is a simple greedy, buy needed meat for $i-th$ day when it's cheapest among days $1, 2, ..., n$.↵

So, the pseudo code below will work:↵


~~~~~↵
ans = 0↵
price = infinity↵
for i = 1 to n↵
      price = min(price, p[i])↵
      ans += price * a[i]↵
~~~~~↵

![ ](http://codeforces.com/predownloaded/64/4c/644c9930cf472ff1bdb48eb3a5f481cce5bbc04b.png)↵

Time complexity: $\mathcal O(n)$↵

[C++ Code](http://ideone.com/fa7rF5) by [user:PrinceOfPersia,2015-10-15]↵

[Python Code](http://ideone.com/Sh0hPp) by [user:Haghani,2015-10-15]↵

[Python Code](http://ideone.com/5J6Rew) by [user:Zlobober,2015-10-15]↵

### 
[problem:588B]Div.2 B (Author: [user:PrinceOfPersia,2015-10-01])↵

Find all prime divisors of $n$. Assume they are $p_1, p_2, ..., p_k$ (in $\mathcal O(\sqrt n)$). If answer is $a$, then we know that for each $1 \leq i \leq k$, obviously $a$ is not divisible by $p_i^2$ (and all greater powers of $p_i$). So $a \leq p_1 \times p_2 \times ... \times p_k$. And we know that $p_1 \times p_2 \times ... \times p_k$ is itself lovely. So,answer is $p_1 \times p_2 \times ... \times p_k$↵


![ ](http://codeforces.com/predownloaded/01/2d/012dd215c8c4fe26618c1deac16b705d6e91c093.png)↵

Time complexity: $\mathcal O(\sqrt n)$↵

[C++ Code](http://ideone.com/5vLYwi) by [user:PrinceOfPersia,2015-10-15]↵

[Python Code](http://ideone.com/Wh2Mrw) by [user:Haghani,2015-10-15]↵

[Python Code](http://ideone.com/1Ca7lj) by [user:Zlobober,2015-10-15]↵

### 
[problem:587A]A (Author: [user:PrinceOfPersia,2015-10-01])↵

Problem is: you have to find the minimum number of $k$, such there is a sequence $a_1, a_2, ..., a_k$ with condition $2^{a_1} + 2^{a_2} + ... + 2^{a_k} = S = 2^{w_1} + 2^{w^2} + ... + 2^{w_2}$. Obviously, minimum value of $k$ is the number of set bits in binary representation of $S$ (proof is easy, you can prove it as a practice :P).↵


![ ](http://codeforces.com/predownloaded/05/1c/051c344e6b9eb78f1f88fc810efa56b75a0ee02a.png)↵


Our only problem is how to count the number of set bits in binary representation of $S$? Building the binary representation of $S$ as an array in $\mathcal O(n + max(a_i))$ is easy: ↵


~~~~~↵
MAXN = 1000000 + log(1000000)↵
bit[0..MAXN] = {} // all equal to zero↵
ans = 0↵
for i = 1 to n↵
      bit[w[i]] ++ // of course after this, some bits maybe greater than 1, we'll fix them below↵
for i = 0 to MAXN - 1↵
      bit[i + 1] += bit[i]/2 // floor(bit[i]/2)↵
      bit[i] %= 2 // bit[i] = bit[i] modulo 2↵
      ans += bit[i] // if bit[i] = 0, then answer doesn't change, otherwise it'll increase by 1↵
~~~~~↵

Time complexity: $\mathcal O(n + max(a_i))$↵

[C++ Code](http://ideone.com/90m1nM) by [user:PrinceOfPersia,2015-10-15]↵

[C++ Code](http://ideone.com/UT3GoJ) by [user:Haghani,2015-10-15]↵


### 
[problem:587B]B (Author: [user:PrinceOfPersia,2015-10-01])↵

If we fix $x$ and $b_{i_x}\ mod\ n$, then problem will be solved (because we can then multiply it by the number of valid distinct values of $\lfloor \frac{i_x}{n} \rfloor$).↵

For the problem above, let $dp[i][j]$ be the number of valid subsequences of $b$ where $x = j$ and $\lfloor \frac{i_1}{n} \rfloor = 0$ and $\lfloor \frac{i_x}{n} \rfloor = i$. Of course, for every $i$, $dp[i][1] = 1$. For calculating value of $dp[i][j]$:↵

$dp[i][j] = \sum \limits_{0 \leq k \leq n-1, a_k \leq a_i} dp[k][j-1]$↵

For this purpose, we can sort the array $a$ and use two pointer:↵

if $p_0, p_1,... p_{n-1}$ is a permutation of $0,...,n-1$ where for each $0 \leq t < n-1$, $a_{p_t} \leq a_{p_{t+1}}$:↵


~~~~~↵
for i = 0 to n-1↵
      dp[i][1] = 1↵
for j = 2 to k↵
      pointer = 0↵
      sum = 0↵
      for i = 0 to n-1↵
            while pointer < n and a[p[pointer]] <= a[i]↵
                  sum = (sum + dp[p[pointer ++]][j - 1]) % MOD↵
            dp[i][j] = sum↵
~~~~~↵


![ ](http://codeforces.com/predownloaded/d9/6a/d96a1d796b1a39a0d56c51f4d1b92a9ecd72fff7.png)↵


Now, if $c = \lceil \frac{l}{n} \rceil$ and $x = l - 1\ mod\ n$, then answer equals to $\sum \limits_{i=0}^{x} \sum \limits_{j=1}^{min(c, k)} dp[i][j] \times (c - j + 1) \sum \limits_{i=x + 1}^{n-1} \sum \limits_{j=1}^{min(c - 1, k)} dp[i][j] \times (c - j)$ (there are $c - j + 1$ valid different values of $\lfloor \frac{i_x}{n} \rfloor$ for the first group and $c-j$ for the second group).↵


Time complexity: $\mathcal O(nk)$↵

[C++ Code](http://ideone.com/7QJJHJ) by [user:PrinceOfPersia,2015-10-15]↵

[C++ Code](http://ideone.com/WNYKEz) by [user:Haghani,2015-10-15]↵

[Java Code](http://ideone.com/hCsaDO) by [user:Zlobober,2015-10-15]↵

### 
[problem:587C]C (Author: [user:PrinceOfPersia,2015-10-01])↵

Solution is something like the fourth LCA approach discussed [here](http://codeforces.com/blog/entry/16221).↵

For each $1 \leq i \leq n$ and $0 \leq j \leq lg(n)$, store the minimum 10 people in the path from city (vertex) $i$ to its $2^j -th$ parent in an array.↵

Now everything is needed is: how to merge the array of two paths? You can keep the these 10 values in the array in increasing order and for merging, use `merge` function which will work in $\mathcal O(20)$. And then delete the extra values (more than 10).↵

And do the same as described in the article for a query (just like the preprocess part).↵

![ ](http://codeforces.com/predownloaded/d3/0b/d30bf401a5e9f5b2c5e8db0f56b736a1ae8d5018.png)↵

Time complexity: $\mathcal O((n + q)a. lg(n))$↵

[C++ Code](http://ideone.com/Rbr9TJ) by [user:PrinceOfPersia,2015-10-15]↵

[C++ Code](http://ideone.com/1NqglU) by [user:Haghani,2015-10-15]↵

[Java Code](http://ideone.com/pzVUMC) by [user:Zlobober,2015-10-15]↵

### 
[problem:587D]D (Author: [user:PrinceOfPersia,2015-10-01])↵

Run binary search on the answer ($t$). For checking if answer is less than or equal to $x$ (`check(x)`):↵

First of all delete all edges with destructing time greater than $x$. Now, if there is more than one pair of edges with the same color connected to a vertex(because we can delete at most one of them), answer is "No".↵

Use 2-Sat. Consider a literal for each edge $e$ ($x_e$). If $x_e = TRUE$, it means it should be destructed and it shouldn't otherwise. There are some conditions:↵

1. For each vertex $v$, if there is one (exactly one) pair of edges like $i$ and $j$ with the same color connected to $v$, then we should have the clause $x_i \vee x_j$.↵

2. For each vertex $v$, if the edges connected to it are $e_1, e_2, ..., e_k$, we should make sure that there is no pair $(i, j)$ where $1 \leq i < j \leq k$ and $x_{e_1} = x_{e_2} = True$. The naive approach is to add a clause $\urcorner x_{e_i} \vee \urcorner x_{e_j}$ for each pair. But it's not efficient.↵

![ ](http://codeforces.com/predownloaded/b0/ff/b0ff057dcba10957a3c229e857839d7c2330bdfa.png)↵

The efficient way tho satisfy the second condition is to use prefix or: adding $k$ new literals $p_1, p_2, ..., p_k$ and for each $j \leq i$, make sure $x_{e_j} \Rightarrow p_i$. To make sure about this, we can add two clauses for each $p_i$: $\urcorner x_{e_i} \vee p_i$ and $\urcorner p_{i-1} \vee p_i$ (the second one is only for $i > 1$).↵

And the only thing left is to make sure $\urcorner p_i \vee \urcorner x_{e_{i + 1}}$ (there are no two `TRUE` edges).↵

This way the number of literals and clauses are $\mathcal O(n + m)$. ↵

So, after binary search is over, we should run `check(t)` to get a sample matching.↵


Time complexity: $\mathcal O((n + m) lg(m))$ (but slow, because of the constant factor)↵

[C++ Code](http://ideone.com/KGepK0) by [user:PrinceOfPersia,2015-10-15]↵

[C++ Code](http://ideone.com/LvFDOX) by [user:Haghani,2015-10-15]↵

[Java Code](http://ideone.com/bx3QJ8) by [user:Zlobober,2015-10-15]↵



### 
[problem:587E]E (Authors: [user:PrinceOfPersia,2015-10-01] and [user:Haghani,2015-10-01])↵



**Lemma #1:** If numbers $b_1, b_2, ..., b_k$ are $k$ Kheshtaks of $a_1, ..., a_n$, then $b_1 \oplus b_2 \oplus ... \oplus b_k$ is a Kheshtak of $a_1, ..., a_n$.↵

**Proof:** For each $1 \leq i \leq k$, consider $mask_i$ is a binary bitmask of length $n$ and its $j-th$ bit shows a subsequence of $a_1, ..., a_n$ (subset) with xor equal to $b_i$.↵

So, xor of elements subsequence(subset) of $a_1, ..., a_n$ with bitmask equal to $mask_1 \oplus mask_2 \oplus ... \oplus mask_k$ equals to $b_1 \oplus b_2 \oplus ... \oplus b_k$. So, it's a Kheshtak of this sequence.↵

From this lemma, we can get another results: If all numbers $b_1, b_2, ..., b_k$ are $k$ Kheshtaks of $a_1, ..., a_n$, then every Kheshtak of $b_1, b_2, ..., b_k$ is a Kheshtak of $a_1, ..., a_n$↵

**Lemma #2:** Score of sequence $a_1, a_2, ..., a_n$ is equal to the score of sequence $a_1, a_1 \oplus a_2, a_2 \oplus a_3, ..., a_{n-1} \oplus a_n$.↵

**Proof:** If we show the second sequence by $b_1, b_2, ..., b_n$, then for each $1 \leq i \leq n$:↵

- $b_i$ = $a_{i-1} \oplus a_i$↵
- $a_i$ = $b_1 \oplus b_2 \oplus ... \oplus b_i$↵

$\Longrightarrow$ each element from sequence $b$ is a Kheshtak of sequence $a$ and vise versa. So, due to the result of Lemma #1, each Kheshtak of sequence $b$ is a Kheshtak of sequence $a$ and vise versa. So: ↵

- $score(b_1, ..., b_n) \leq score(a_1, ..., a_n)$↵
- $score(a_1, ..., a_n) \leq score(b_1, ..., b_n)$↵

$\Longrightarrow$ $score(a_1, ..., a_n) = score(b_1, ..., b_n)$↵

![ ](http://codeforces.com/predownloaded/fb/1f/fb1feb31747eb109aff4ec806075588f21e5d932.png)↵


Back to original problem: denote another array $b_2, ..., b_n$ where $b_i = a_{i-1} \oplus a_i$. Let's solve these two problems:↵

1- We have array $a_1, ..., a_n$ and $q$ queries of two types:↵

1. $upd(l, r, k)$: Given numbers $l, r$ and $k$, for each $l \leq i \leq r$, perform $a_i = a_i \oplus k$↵
2. $ask(i):$ Given number $i$, return the value of $a_i$.↵

This problem can be solved easily with a simple segment tree using lazy propagation.↵

2- We have array $b_2, ..., b_n$ and queries of two types:↵

1. $modify(p, k)$: Perform $b_p = k$.↵
2. $basis(l, r)$: Find and return the basis vector of $b_l , b_{l+1}, ..., b_r$ (using Gaussian Elimination, its size it at most 32).↵

This problem can be solved by a segment tree where in each node we have the basis of the substring of that node (node $[l, r)$ has the basis of sequence $b_l ,..., b_{r-1}$).↵

This way we can insert to a basis vector $v$:↵


~~~~~↵
insert(x, v)↵
for a in v↵
if a & -a & x↵
x ^= a↵
if !x↵
return↵
for a in v↵
if x & -x & a↵
a ^= x↵
v.push(x)↵
~~~~~↵

But size of $v$ will always be less than or equal to 32. For merging two nodes (of segment tree), we can insert the elements of one in another one.↵

For handling queries of two types, we act like this:↵

Type one: Call functions: $upd(l, r, k)$, $modify(l, b_l \oplus k)$ and $modify(r + 1, b_{r+1} \oplus k)$.↵

Type two: Let $b = basis(l + 1, r)$. Call $insert(a_l, b)$. And then print $2^{b.size()}$ as the answer.↵

Time complexity: $\mathcal O(n lg(n) \times 32^2)$ = $\mathcal O(n lg(n) lg^2(max(a_1,...,a_n)))$↵

[C++ Code](http://ideone.com/GnOXuG) by [user:PrinceOfPersia,2015-10-15]↵

[C++ Code](http://ideone.com/WnPXQ4) by [user:Haghani,2015-10-15]↵

[Java Code](http://ideone.com/XNsXoa) by [user:Zlobober,2015-10-15]↵


### 
[problem:587F]F (Author: [user:PrinceOfPersia,2015-10-01])↵

Use Aho-Corasick. Assume first of all we build the trie of our strings (function `t`). If $t(v, c) \ne -1$ it means that there is an edge in the trie outgoing from vertex $v$ written $c$ on it.↵

So, for building Aho-Corasick, consider $f(v)$ = the vertex we go into, in case of failure ($t(v, c) = -1$). i.e the deepest vertex ($u$), that $v \ne u$ and the path from root to $u$ is a suffix of path from root to $v$. No we can build an automaton (Aho-Corasick), function $g$. For each i, do this (in the automaton):↵


~~~~~↵
cur = root↵
for c in s[i]↵
cur = g(cur, c)↵
And then push i in q[cur] (q is a vector, also we do this for cur = root).↵

end[cur].push(i)  // end is also a vector, consisting of the indices of strings ending in vertex cur (state cur in automaton)↵
last[i] = cur // last[i] is the final state we get to from searching string s[i] in automaton g↵
~~~~~↵

Assume $cnt(v, i)$ is the number of occurrences of number $i$ in $q[v]$. Also, denote $count(v, i) = \sum_{u\ in\ subtree\ of\ v} cnt(u, i)$.↵

Build another tree. In this tree, for each $i$ that is not root of the trie, let $par[i] = f(i)$ (the vertex we go in the trie, in case of failure) and call it C-Tree.↵

So now, problem is on a tree. Operations are : Each query gives numbers $l, r, k$ and you have to find the number $\sum \limits_{i=l}^{r} count(last[i], k)$.↵


![ ](http://codeforces.com/predownloaded/68/39/6839a2df61c0aa1ea63eedb236e4c3c126a07644.png)↵


Act offline. If $N = 10^5$, then:↵

**1.** For each $i$ such that $s[i].size() > \sqrt N$, collect queries (like struct) in a vector of queries $query[i]$, then run `dfs` on the C-Tree and using a partial sum answer to all queries with $k = i$. There are at most $\sqrt n$ of these numbers, so it can be done in $\mathcal O(N \sqrt N)$. After doing these, erase $i$ from all $q[1], q[1], ..., q[N]$.↵

Code (in `dfs`) would be like this(on C-Tree):↵


~~~~~↵
partial_sum[n] = {}; // all 0↵
dfs(v, i){↵
cnt = 0;↵
for x in q[v]↵
if(x == i)↵
++ cnt;↵
for u in childern[v]↵
cnt += dfs(u);↵
for x in end[v]↵
partial_sum[x] += cnt;↵
return cnt;↵
}↵
calc(i){↵
dfs(root, i);↵
for i = 2 to n↵
partial_sum[i] += partial_sum[i-1]↵
for query u in query[i]↵
u.ans = partial_sum[u.r] - partial_sum[u.l - 1]↵
}↵
~~~~~↵

And we should just run `calc(i)` for each of them.↵

**2.** For each $i$ such that $s[i].size() \leq \sqrt N$, collect queries (like struct) in a vector of queries $query[i]$. (each element of this vector have three integers in it: $l, r$ and $ans$).↵

Consider this problem:↵

We have an array a of length $N$(initially all element equal to 0) and some queries of two types:↵

1. $increase(i, val)$: increase $a[i]$ by $val$↵
2. $sum(i)$: tell the value of $a[1] + a[2] + ... + a[i]$↵

We know that number of queries of the first type is $\mathcal O(N)$ and from the second type is $\mathcal O(N \sqrt N)$. Using Sqrt decomposition, we can solve this problem in $\mathcal O(N \sqrt N)$:↵


~~~~~↵
K = sqrt(N)↵
tot[K] = {}, a[N] = {} // this code is 0-based↵
increase(i, val)↵
while i < N and i % K > 0↵
a[i ++] += val↵
while i < K↵
tot[i/K] += val↵
i += K↵
sum(i)↵
return a[i] + tot[i/K]↵
~~~~~↵

Back to our problem now.↵

Then, just run `dfs` once on this C-Tree and act like this:↵


~~~~~↵
dfs(vertex v):↵
for i in end[v]↵
increase(i, 1)↵
for i in q[v]↵
for query u in query[i]↵
u.ans += sum(u.r) - sum(u.l - 1)↵
for u in children[v]↵
dfs(u)↵
for i in end[v]↵
increase(i, -1)↵
~~~~~↵


Then answer to a query $q$ is $q.ans$.↵



Time complexity: $\mathcal O(N \sqrt N)$↵

[C++ Code](http://ideone.com/kIQjcI) by [user:PrinceOfPersia,2015-10-15]↵

[C++ Code](http://ideone.com/3QyBHv) by [user:Haghani,2015-10-15]↵

[Java Code](http://ideone.com/f9ul21) by [user:Zlobober,2015-10-15]↵

![ ](http://viber.tsymbal.su/data/stickers/03900.png)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English DarthKnight 2016-03-05 19:25:29 315
en2 English DarthKnight 2015-10-15 22:04:37 116
en1 English DarthKnight 2015-10-15 22:01:48 15235 Initial revision (published)