codeforces-scrape

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

703.md (4625B)


      1 Source: https://codeforces.com/blog/entry/46434
      2 
      3 #### [703A — Mishka and Game](//codeforces.com/contest/703/problem/A)
      4 
      5 In this problem you had to do use the following algo. If Mishka wins Chris in the current round, then increase variable *countM* by 1. Otherwise (if Chris wins Mishka) increase variable *countC*. After that you had to compare this values and print the answer.
      6 
      7 #### [703B — Mishka and trip](//codeforces.com/contest/703/problem/B)
      8 
      9 Let's look at the first capital. Note that the total cost of the outgoing roads is *c*[*id*1] · (*sum* - *c*[*id*1]), where *sum* — summary beauty of **all** cities. Thus iterating through the capitals we can count the summary cost of roads between capitals and all the other cities. But don't forget that in this case we count the roads between pairs of capitals twice. To avoid this on each step we should update *sum* = *sum* - *c*[*id**cur*] , where *id**cur* is the position of current capital. In the end we should add to the answer the cost of roads between "non-capital" neighbour cities.
     10 
     11 Complexity — *O*(*n*).
     12 
     13 #### [703C — Chris and Road](//codeforces.com/contest/703/problem/C)
     14 
     15 Imagine that the bus stands still and we move "to the right" with a constant speed *v*. Then it's not hard to see that movement along the line *y* = (*u* / *v*) · (*x*  -  *v* · *t*0) is optimal, where *t*0 — time in which we begin our movement. In this way answer is *t* = *t*0 + (*w* / *u*).
     16 
     17 If *t*0 = 0, then we start our movement immediately. In this case we need to check that our line doesn't intersect polygon (either we can cross the road in front of a bus, or the bus is gone).
     18 
     19 Otherwise we need to find such minimal *t*0 that our line is tangent to the polygon. It can be done with binary search.
     20 
     21 Complexity — *O*(*n* *log* *n*).
     22 
     23 Exercise: Solve this problem in *O*(*n*).
     24 
     25 #### [703D — Mishka and Interesting sum](//codeforces.com/contest/703/problem/D)
     26 
     27 Easy to see, that the answer for query is XOR-sum of **all** elements in the segment xored with XOR-sum of **distinct** elements in the segment. XOR-sum of all numbers we can find in *O*(1) using partial sums. As for the XOR-sum of distinct numbers... Let's solve easier problem.
     28 
     29 Let the queries be like "find the number of distinct values in a segment". Let's sort all the queries according to their right bounds and iterate through all elements of our array. We also need to make a list *last*, where *last*[*value*] is the last position of *value* on the processed prefix of array. Assume we are at position *r*. Then the answer for the query in the segment [*l*,  *r*] (*l* ≤ *r*) is ![](https://espresso.codeforces.com/f6d6af9e762a7835c09dfa2da024cf7b521d6f3a.png), where *cnt*[*i*] = 1 if *last*[*a**i*] = *i* and 0 otherwise. It's easy to store and update such values in *cnt*. When moving to the next position we have to make the following assignments: *cnt*[*last*[*a**i*]] = 0, *cnt*[*i*] = 1, *last*[*a**i*] = *i*. To get described sum in *O*(*log* *n*) we can use segment tree (or Fenwick tree) instead of standard array.
     30 
     31 Now let's turn back to our problem. Everything we have to do is to change assignment *cnt*[*i*] = 1 to *cnt*[*i*] = *a**i* and count XOR-sum instead of sum. Now we can solve this problem in *O*(*n* *log* *n*).
     32 
     33 [Solution (with Fenwick)](http://pastie.org/10931832)
     34 
     35 P.S.: Also there is a solution with *O*(*n* *sqrt* *n*) complexity (using Mo's algo), but we tried to kill it :D
     36 
     37 #### [703E — Мишка и делители](//codeforces.com/contest/703/problem/E)
     38 
     39 Let's use dp to solve this problem.
     40 
     41 Suppose *dp*[*i*][*d*] is the minimal number of elements on prefix of size *i*, that their product is divisible by *d*. It's easy to see that *dp*[*i*][*d*] = *min*(*dp*[*i*  -  1][*d*],  *dp*[*i*  -  1][*d*  /  *gcd*(*d*,  *a**i*)]  +  1). That is so because it's optimal to take as much divisors of *a**i* as possible. Answer — *dp*[*n*][*k*].
     42 
     43 Let's imrove our solution. Notice, that as *d* we should use only divisors of *k* (which **in the worst** case would be 6720). As for *gcd*, we can easily find it in *O*(*primes*(*k*)), where *primes*(*k*) — number of primes in decomposition of *k*. We also need to renumber our divisors according to their prime decomposition.
     44 
     45 To get AC in this problem you had to optimize described dp and add minimization of used elements' sum. Final complexity — *O*(*n* · *divs*(*k*) · *primes*(*k*)).
     46 
     47 [Solution](http://pastie.org/10930676)