codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

587.md (18696B)


      1 Source: https://codeforces.com/blog/entry/20971
      2 
      3 ### Div.2 A (Author: [Haghani](/profile/Haghani "International Grandmaster Haghani"))
      4 
      5 Idea is a simple greedy, buy needed meat for *i* - *th* day when it's cheapest among days 1, 2, ..., *n*.
      6 
      7 So, the pseudo code below will work:
      8 
      9 ```
     10 ans = 0
     11 price = infinity
     12 for i = 1 to n
     13       price = min(price, p[i])
     14       ans += price * a[i]
     15 ```
     16 
     17 ![ ](/predownloaded/fc/81/fc812d42646e9c87226be91b508756380c3f951c.png)
     18 
     19 Time complexity: ![](https://espresso.codeforces.com/68e031801404c070f09a1e222bc08242850b89a8.png)
     20 
     21 [C++ Code](http://ideone.com/fa7rF5) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
     22 
     23 [Python Code](http://ideone.com/Sh0hPp) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
     24 
     25 [Python Code](http://ideone.com/5J6Rew) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
     26 
     27 ### Div.2 B (Author: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia"))
     28 
     29 Find all prime divisors of *n*. Assume they are *p*1, *p*2, ..., *p**k* (in ![](https://espresso.codeforces.com/7d8ce961def026226deae6fbe74a70c2c34944ef.png)). If answer is *a*, then we know that for each 1 ≤ *i* ≤ *k*, obviously *a* is not divisible by *p**i*2 (and all greater powers of *p**i*). So *a* ≤ *p*1 × *p*2 × ... × *p**k*. And we know that *p*1 × *p*2 × ... × *p**k* is itself lovely. So,answer is *p*1 × *p*2 × ... × *p**k*
     30 
     31 ![ ](/predownloaded/34/59/34595ab76633b26678b06353e5ec365db73b93cb.png)
     32 
     33 Time complexity: ![](https://espresso.codeforces.com/7d8ce961def026226deae6fbe74a70c2c34944ef.png)
     34 
     35 [C++ Code](http://ideone.com/5vLYwi) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
     36 
     37 [Python Code](http://ideone.com/Wh2Mrw) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
     38 
     39 [Python Code](http://ideone.com/1Ca7lj) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
     40 
     41 ### A (Author: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia"))
     42 
     43 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).
     44 
     45 ![ ](/predownloaded/8a/68/8a6891e334219c67c144953863345663c90c6a25.png)
     46 
     47 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 ![](https://espresso.codeforces.com/93e86222c15da186cf7fc1a2efe109b4e35da829.png) is easy:
     48 
     49 ```
     50 MAXN = 1000000 + log(1000000)
     51 bit[0..MAXN] = {} // all equal to zero
     52 ans = 0
     53 for i = 1 to n
     54       bit[w[i]] ++ // of course after this, some bits maybe greater than 1, we'll fix them below
     55 for i = 0 to MAXN - 1
     56       bit[i + 1] += bit[i]/2 // floor(bit[i]/2)
     57       bit[i] %= 2 // bit[i] = bit[i] modulo 2
     58       ans += bit[i] // if bit[i] = 0, then answer doesn't change, otherwise it'll increase by 1
     59 ```
     60 
     61 Time complexity: ![](https://espresso.codeforces.com/93e86222c15da186cf7fc1a2efe109b4e35da829.png)
     62 
     63 [C++ Code](http://ideone.com/90m1nM) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
     64 
     65 [C++ Code](http://ideone.com/UT3GoJ) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
     66 
     67 ### B (Author: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia"))
     68 
     69 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 ![](https://espresso.codeforces.com/a245ec35a18eb7c878054fdc5b368c536145a0e2.png)).
     70 
     71 For the problem above, let *dp*[*i*][*j*] be the number of valid subsequences of *b* where *x* = *j* and ![](https://espresso.codeforces.com/0852a3a71090aaeaad8ca7a783e8fc589fee6aeb.png) and ![](https://espresso.codeforces.com/68da51cfbd38d6f2fd1a773ab0d147c7622ee321.png). Of course, for every *i*, *dp*[*i*][1] = 1. For calculating value of *dp*[*i*][*j*]:
     72 
     73 ![](https://espresso.codeforces.com/99a7b35cacd072c87821e06fa46f80cdd264dc7a.png)
     74 
     75 For this purpose, we can sort the array *a* and use two pointer:
     76 
     77 if *p*0, *p*1, ...*p**n* - 1 is a permutation of 0, ..., *n* - 1 where for each 0 ≤ *t* < *n* - 1, *a**p**t* ≤ *a**p**t* + 1:
     78 
     79 ```
     80 for i = 0 to n-1
     81       dp[i][1] = 1
     82 for j = 2 to k
     83       pointer = 0
     84       sum = 0
     85       for i = 0 to n-1
     86             while pointer < n and a[p[pointer]] <= a[i]
     87                   sum = (sum + dp[p[pointer ++]][j - 1]) % MOD
     88             dp[i][j] = sum
     89 ```
     90 
     91 ![ ](/predownloaded/b1/8a/b18a83b6a141efc2b69dd91788ae02e5cbc21a7b.png)
     92 
     93 Now, if ![](https://espresso.codeforces.com/eff324af994bac40b33c7adfab63f78e97d071c2.png) and *x* = *l* - 1 *mod* *n*, then answer equals to ![](https://espresso.codeforces.com/9f0c79c0bb5bec79a82e501bd1d3e7f6d3eba839.png) (there are *c* - *j* + 1 valid different values of ![](https://espresso.codeforces.com/a245ec35a18eb7c878054fdc5b368c536145a0e2.png) for the first group and *c* - *j* for the second group).
     94 
     95 Time complexity: ![](https://espresso.codeforces.com/3f22548338fe0e8aede6bfd22df71ed7081a6135.png)
     96 
     97 [C++ Code](http://ideone.com/7QJJHJ) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
     98 
     99 [C++ Code](http://ideone.com/WNYKEz) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
    100 
    101 [Java Code](http://ideone.com/hCsaDO) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    102 
    103 ### C (Author: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia"))
    104 
    105 Solution is something like the fourth LCA approach discussed [here](//codeforces.com/blog/entry/16221).
    106 
    107 For each 1 ≤ *i* ≤ *n* and 0 ≤ *j* ≤ *lg*(*n*), store the minimum 10 people in the path from city (vertex) *i* to its 2*j* - *th* parent in an array.
    108 
    109 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 ![](https://espresso.codeforces.com/05f9b47d1d19dd86ad6171a9f88f606609572474.png). And then delete the extra values (more than 10).
    110 
    111 And do the same as described in the article for a query (just like the preprocess part).
    112 
    113 ![ ](/predownloaded/9b/65/9b652b15045b007b28da01e60acaeae6d6dba3ea.png)
    114 
    115 Time complexity: ![](https://espresso.codeforces.com/80c19c71f987e4330f8eee2839750a25d178f87b.png)
    116 
    117 [C++ Code](http://ideone.com/Rbr9TJ) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
    118 
    119 [C++ Code](http://ideone.com/1NqglU) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
    120 
    121 [Java Code](http://ideone.com/pzVUMC) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    122 
    123 ### D (Author: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia"))
    124 
    125 Run binary search on the answer (*t*). For checking if answer is less than or equal to *x* (`check(x)`):
    126 
    127 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".
    128 
    129 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:
    130 
    131 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 ![](https://espresso.codeforces.com/cb3dd25378e3ed816bdf25133fbf6f1b813a3aa3.png).
    132 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 ≤ *i* < *j* ≤ *k* and *x**e*1 = *x**e*2 = *True*. The naive approach is to add a clause ![](https://espresso.codeforces.com/ecefbfc00c042a32123cee554ede9f745b913066.png) for each pair. But it's not efficient.
    133 
    134 ![ ](/predownloaded/1a/c6/1ac6ad26831a1ebf8fac5b2b6fd0858e9426eb8a.png)
    135 
    136 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* ≤ *i*, make sure ![](https://espresso.codeforces.com/4165d0dfcd49d1197c05f6ce631aa1ed6b98ba71.png). To make sure about this, we can add two clauses for each *p**i*: ![](https://espresso.codeforces.com/5bfc3c2c3cde0df8b506168de084fb4ff8000744.png) and ![](https://espresso.codeforces.com/9e6b60d87e58fda172c72d7d405e826329014fa7.png) (the second one is only for *i* > 1).
    137 
    138 And the only thing left is to make sure ![](https://espresso.codeforces.com/9aea6c0cd6c002a8307d986f197e0a76386ee6ce.png) (there are no two `TRUE` edges).
    139 
    140 This way the number of literals and clauses are ![](https://espresso.codeforces.com/7dadd382d2142475e4c74cdd48330ddf76a8ef65.png).
    141 
    142 So, after binary search is over, we should run `check(t)` to get a sample matching.
    143 
    144 Time complexity: ![](https://espresso.codeforces.com/ddd5a284e8107dfc7aceb1e428617d2b0d69dae5.png) (but slow, because of the constant factor)
    145 
    146 [C++ Code](http://ideone.com/KGepK0) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
    147 
    148 [C++ Code](http://ideone.com/LvFDOX) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
    149 
    150 [Java Code](http://ideone.com/bx3QJ8) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    151 
    152 ### E (Authors: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia") and [Haghani](/profile/Haghani "International Grandmaster Haghani"))
    153 
    154 **Lemma #1:** If numbers *b*1, *b*2, ..., *b**k* are *k* Kheshtaks of *a*1, ..., *a**n*, then ![](https://espresso.codeforces.com/107f8f5eb29fedb2134602731b44e34101772f60.png) is a Kheshtak of *a*1, ..., *a**n*.
    155 
    156 **Proof:** For each 1 ≤ *i* ≤ *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*.
    157 
    158 So, xor of elements subsequence(subset) of *a*1, ..., *a**n* with bitmask equal to ![](https://espresso.codeforces.com/9a9a8e8f14bf3c1d594a5ca67dcb54717f27afeb.png) equals to ![](https://espresso.codeforces.com/107f8f5eb29fedb2134602731b44e34101772f60.png). So, it's a Kheshtak of this sequence.
    159 
    160 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*
    161 
    162 **Lemma #2:** Score of sequence *a*1, *a*2, ..., *a**n* is equal to the score of sequence ![](https://espresso.codeforces.com/28a683a472e4dd22b293fe0268e173a77b32fa45.png).
    163 
    164 **Proof:** If we show the second sequence by *b*1, *b*2, ..., *b**n*, then for each 1 ≤ *i* ≤ *n*:
    165 
    166 * *b**i* = ![](https://espresso.codeforces.com/d749eb6a277b42f079a6e01dfe86195b1ce4f18e.png)
    167 * *a**i* = ![](https://espresso.codeforces.com/628d909edc0f5d3f7329f6fcd17ec1614264579c.png)
    168 
    169 ![](https://espresso.codeforces.com/9b6d3419f9beba91c1d5382375c3d93a29f6122f.png) 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:
    170 
    171 * *score*(*b*1, ..., *b**n*) ≤ *score*(*a*1, ..., *a**n*)
    172 * *score*(*a*1, ..., *a**n*) ≤ *score*(*b*1, ..., *b**n*)
    173 
    174 ![](https://espresso.codeforces.com/9b6d3419f9beba91c1d5382375c3d93a29f6122f.png) *score*(*a*1, ..., *a**n*) = *score*(*b*1, ..., *b**n*)
    175 
    176 ![ ](/predownloaded/07/0c/070cfe11e58d4bf9ed54178a0c5220a87581e046.png)
    177 
    178 Back to original problem: denote another array *b*2, ..., *b**n* where ![](https://espresso.codeforces.com/10920a541e39d413554582cae7af04bcd340a653.png). Let's solve these two problems:
    179 
    180 1- We have array *a*1, ..., *a**n* and *q* queries of two types:
    181 
    182 1. *upd*(*l*, *r*, *k*): Given numbers *l*, *r* and *k*, for each *l* ≤ *i* ≤ *r*, perform ![](https://espresso.codeforces.com/27c8ed4094a545433bfe9d1b4f6bc07014c4c107.png)
    183 2. *ask*(*i*):  Given number *i*, return the value of *a**i*.
    184 
    185 This problem can be solved easily with a simple segment tree using lazy propagation.
    186 
    187 2- We have array *b*2, ..., *b**n* and queries of two types:
    188 
    189 1. *modify*(*p*, *k*): Perform *b**p* = *k*.
    190 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).
    191 
    192 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).
    193 
    194 This way we can insert to a basis vector *v*:
    195 
    196 ```
    197 insert(x, v)
    198 	for a in v
    199 		if a & -a & x
    200 			x ^= a
    201 	if !x
    202 		return
    203 	for a in v
    204 		if x & -x & a
    205 			a ^= x
    206 	v.push(x)
    207 ```
    208 
    209 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.
    210 
    211 For handling queries of two types, we act like this:
    212 
    213 Type one: Call functions: *upd*(*l*, *r*, *k*), ![](https://espresso.codeforces.com/27866b849f3124b415c4672620928bb02a814689.png) and ![](https://espresso.codeforces.com/3a6c7e319fc91189209c32e29ca7e98f28b6eff2.png).
    214 
    215 Type two: Let *b* = *basis*(*l* + 1, *r*). Call *insert*(*a**l*, *b*). And then print 2*b*.*size*() as the answer.
    216 
    217 Time complexity: ![](https://espresso.codeforces.com/cddae6bb3eb529c60fadd4e6ffaa45b47b088b8f.png) = ![](https://espresso.codeforces.com/c3d77d96ccf42360308dad49c12c28b7aea5c961.png)
    218 
    219 [C++ Code](http://ideone.com/GnOXuG) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
    220 
    221 [C++ Code](http://ideone.com/WnPXQ4) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
    222 
    223 [Java Code](http://ideone.com/XNsXoa) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    224 
    225 ### F (Author: [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia"))
    226 
    227 Use Aho-Corasick. Assume first of all we build the trie of our strings (function `t`). If *t*(*v*, *c*) ≠  - 1 it means that there is an edge in the trie outgoing from vertex *v* written *c* on it.
    228 
    229 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* ≠ *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):
    230 
    231 ```
    232 cur = root
    233 for c in s[i]
    234 	cur = g(cur, c)
    235 	And then push i in q[cur] (q is a vector, also we do this for cur = root).
    236 
    237 end[cur].push(i) 	// end is also a vector, consisting of the indices of strings ending in vertex cur (state cur in automaton)
    238 last[i] = cur // last[i] is the final state we get to from searching string s[i] in automaton g
    239 ```
    240 
    241 Assume *cnt*(*v*, *i*) is the number of occurrences of number *i* in *q*[*v*]. Also, denote ![](https://espresso.codeforces.com/f174f41f356d88aed4a0401867032fca64511687.png).
    242 
    243 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.
    244 
    245 So now, problem is on a tree. Operations are : Each query gives numbers *l*, *r*, *k* and you have to find the number ![](https://espresso.codeforces.com/c6724367eb0b78d4db932ee7f897b3fece0523d4.png).
    246 
    247 ![ ](/predownloaded/d2/87/d28705d57b86d33ba5ca0ef16415f939dbf07de6.png)
    248 
    249 Act offline. If *N* = 105, then:
    250 
    251 **1.** For each *i* such that ![](https://espresso.codeforces.com/deb3ebf6db7bce342d9bac8723b0e9caa1d16510.png), 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 ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png) of these numbers, so it can be done in ![](https://espresso.codeforces.com/449c6bed69ad17b080b559cbe0c9206bf57e80fd.png). After doing these, erase *i* from all *q*[1], *q*[1], ..., *q*[*N*].
    252 
    253 Code (in `dfs`) would be like this(on C-Tree):
    254 
    255 ```
    256 partial_sum[n] = {}; // all 0
    257 dfs(v, i){
    258 	cnt = 0;
    259 	for x in q[v]
    260 		if(x == i)
    261 		++ cnt;
    262 	for u in childern[v]
    263 		cnt += dfs(u);
    264 	for x in end[v]
    265 		partial_sum[x] += cnt;
    266 	return cnt;
    267 }
    268 calc(i){
    269 	dfs(root, i);
    270 	for i = 2 to n
    271 		partial_sum[i] += partial_sum[i-1]
    272 	for query u in query[i]
    273 		u.ans = partial_sum[u.r] - partial_sum[u.l - 1]
    274 }
    275 ```
    276 
    277 And we should just run `calc(i)` for each of them.
    278 
    279 **2.** For each *i* such that ![](https://espresso.codeforces.com/62cbb0ee60f19d52f3441c14d12f0c45f4ae10bd.png), 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*).
    280 
    281 Consider this problem:
    282 
    283 We have an array a of length *N*(initially all element equal to 0) and some queries of two types:
    284 
    285 1. *increase*(*i*, *val*): increase *a*[*i*] by *val*
    286 2. *sum*(*i*): tell the value of *a*[1] + *a*[2] + ... + *a*[*i*]
    287 
    288 We know that number of queries of the first type is ![](https://espresso.codeforces.com/84f66262c3cd9dc11c61f3b73655e8abcb72c1d5.png) and from the second type is ![](https://espresso.codeforces.com/449c6bed69ad17b080b559cbe0c9206bf57e80fd.png). Using Sqrt decomposition, we can solve this problem in ![](https://espresso.codeforces.com/449c6bed69ad17b080b559cbe0c9206bf57e80fd.png):
    289 
    290 ```
    291 K = sqrt(N)
    292 tot[K] = {}, a[N] = {} // this code is 0-based
    293 increase(i, val)
    294 	while i < N and i % K > 0
    295 		a[i ++] += val
    296 	while i < K
    297 		tot[i/K] += val
    298 		i += K
    299 sum(i)
    300 	return a[i] + tot[i/K]
    301 ```
    302 
    303 Back to our problem now.
    304 
    305 Then, just run `dfs` once on this C-Tree and act like this:
    306 
    307 ```
    308 dfs(vertex v):
    309 	for i in end[v]
    310 		increase(i, 1)
    311 	for i in q[v]
    312 		for query u in query[i]
    313 			u.ans += sum(u.r) - sum(u.l - 1)
    314 	for u in children[v]
    315 		dfs(u)
    316 	for i in end[v]
    317 		increase(i, -1)
    318 ```
    319 
    320 Then answer to a query *q* is *q*.*ans*.
    321 
    322 Time complexity: ![](https://espresso.codeforces.com/449c6bed69ad17b080b559cbe0c9206bf57e80fd.png)
    323 
    324 [C++ Code](http://ideone.com/kIQjcI) by [PrinceOfPersia](/profile/PrinceOfPersia "Grandmaster PrinceOfPersia")
    325 
    326 [C++ Code](http://ideone.com/3QyBHv) by [Haghani](/profile/Haghani "International Grandmaster Haghani")
    327 
    328 [Java Code](http://ideone.com/f9ul21) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    329 
    330 ![ ](/predownloaded/45/c4/45c47b9c7787093e8df9739bfda5d617d333e55b.png)