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]↵
~~~~~↵

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$↵

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).↵

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$. 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↵
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↵
~~~~~↵

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]↵

###
[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).↵

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.↵

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)$↵

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)$.↵

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, q, ..., 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 + a + ... + 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 DarthKnight 2016-03-05 19:25:29 315
en2 DarthKnight 2015-10-15 22:04:37 116
en1 DarthKnight 2015-10-15 22:01:48 15235 Initial revision (published)