codeforces-scrape

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

439.md (9662B)


      1 Source: https://codeforces.com/blog/entry/12545
      2 
      3 **[439A - Devu, the Singer and Churu, the Joker](/contest/439/problem/A "Codeforces Round 251 (Div. 2)")**
      4 
      5 For checking whether there is a way to conduct all the songs of the singer, you can conduct the event in the following way.
      6 
      7 * First singer will sing a song.
      8 * Then during 10 minutes rest of the singer, the joker will crack 2 jokes(each of 5 minutes)
      9 * Then singer will again sing a song, then joker, etc.
     10 * After the singer has completes all his songs, the joker will keep on cracking jokes of 5 minutes each.
     11 
     12 Hence minimum duration of the even needed such that sing could sing all his songs will be *t*1 + 10 + *t*2 + 10 + ... +*t**n* = *sum* + (*n* - 1) * 10 where *sum* denote the total time of the songs of the singer.
     13 
     14 So for checking feasibility of the solution, just check whether *sum* + (*n* - 1) * 10 ≤ *duration* or not?.
     15 
     16 If it is feasible, then time remaining for joker will be the entire duration except the time when the singer is singing the song. Hence time available for the joker will be *duration* - *sum*. In that time joker will sing ![](https://espresso.codeforces.com/55978d470451477c7d0d89e23cd57d6105386b93.png) songs.
     17 
     18 **Solution codes**
     19 
     20 * [my solution](//codeforces.com/contest/439/submission/6814268)
     21 
     22 ---
     23 
     24 **[439B - Devu, the Dumb Guy](/contest/439/problem/B "Codeforces Round 251 (Div. 2)")**
     25 
     26 You can formulate the problem in following way. Given two arrays *a* and *b*. Find minimum cost of matching the elements of array *a* to *b*. For our problem the array *a* will be same as *b*. The array *b* will have content *x*, *x* — 1, , 1, 1. For a general version of this problem, we can use min cost max flow(min cost matching), but for this problem following simple greedy solution will work.
     27 
     28 * Sort the array *a* in increasing and *b* in decreasing order (or vice versa).
     29 * Now match *i**th* element of the array a with *i**th* element of array b.
     30 
     31 **Proof:**
     32 
     33 It can be easily proved by exchange argument.
     34 
     35 **Solution Codes**
     36 
     37 * [my solution](//codeforces.com/contest/439/submission/6814439)
     38 
     39 ---
     40 
     41 [439C - Devu and Partitioning of the Array](/contest/439/problem/C "Codeforces Round 251 (Div. 2)")
     42 
     43 Let us first try to find the condition required to make sure the existence of the partitions.
     44 
     45 Notice the following points.
     46 
     47 * If the parity of sum does not match with parity of number of odd partitions (*k* - *p*) , then we can't create the required partitions. eg. *a* = [1;2], *k* = 2, *p* = 0, Then you can not create two partitions of odd size, because then sum of the elements of the partitions of the array will be even whereas the sum of elements of the array is odd.
     48 * If number of odd elements in *a* are less than *k* - *p* (number of required partitions with odd sum), then we can not do a valid partitioning.
     49 * If number of even elements are less than *p*, then we can not create even partitions simply by using even numbers, we have to use odd numbers too. Notice the simple fact that sum of two odd numbers is even. Hence we will try to include 2 odd elements in our partitions too. So if we can create *oddsRemaining* / 2 partitions in which every partition contains 2 odd elements, then we can do a valid partitioning otherwise we can't. Here *oddsRemaining* denotes the number of odd elements which are not used in any of the partitions made up to now.
     50 
     51 Let *oddElements* denotes the number of odd elements in array *a*. Similarly *evenElements* denotes the number of even elements.
     52 
     53 So the answer exists if
     54 
     55 * Number of possible odd partitions are  ≥  *k* - *p* i.e. *oddElements* ≥ *k* - *p*.
     56 * Number of possible even partitions are  ≥  *p* i.e. *evenElements* + (*oddRemaining*) / 2 ≥ *p*. where *oddRemaining* is *oddElements* - (*k* - *p*).
     57 
     58 For generating the actual partitions, you can follow the same strategy used in detecting the existence of the partitions. We will first generate any valid *p* partitions (forget about the condition of using the entire array), then we can simply include the remaining elements of the array in the last partition and we are done.
     59 
     60 **Solution Codes**
     61 
     62 * [[user:Gerald]'s solution](//codeforces.com/contest/439/submission/6814269)
     63 * [my code](//codeforces.com/contest/439/submission/6814282)
     64 
     65 ---
     66 
     67 **[439D - Devu and his Brother](/contest/439/problem/D "Codeforces Round 251 (Div. 2)")**
     68 
     69 You can solve the problem in two ways.
     70 
     71 * **By using ternary search**
     72 
     73 Let us define a function f. Function f(k) = cost needed to make array a elements  ≥  k + cost needed to make array b elements  ≤  k
     74 
     75 Instead of proving it formally, try checking the property on many random test cases. You will realize that f is convex.
     76 
     77 **Claim: f is convex**:
     78 
     79 **Proof:**
     80 
     81 It is fairly easy to prove. See the derivative of f.
     82 
     83 ![](https://espresso.codeforces.com/acebe17e836737d1b9acca2d48f6093ede7c201e.png) = — (# of elements of b > k) + (# of elements of a < k)
     84 
     85 The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.
     86 
     87 So, ![](https://espresso.codeforces.com/b84b8a3386e25d5749839eeb209b43da23fb8e36.png)
     88 
     89 * **By using the fact that optimal values are attainable at the array values**:
     90 
     91 All the extremum points will lie in the elements from the any of the arrays because f is convex and ![](https://espresso.codeforces.com/0572da12d141bdbdd822edc1d9aaff975d93a52e.png) at the event points (or the points of array a and b).
     92 
     93 For learning more about ternary search, you can see following topcoder [discussion](http://apps.topcoder.com/forums/?module=Thread&threadID=506787&start=0&mc=27)
     94 
     95 **Another smart solution**
     96 
     97 Please see following [comment](//codeforces.com/blog/entry/12545#comment-172684) of [goovie](/profile/goovie "Specialist goovie") and proof is given in the [reply](//codeforces.com/blog/entry/12545#comment-172693) by [himank](/profile/himank "Specialist himank")
     98 
     99 **Solutions Code**
    100 
    101 * [ternary search solution](//codeforces.com/contest/439/submission/6814294)
    102 * [my solution using 2nd fact](//codeforces.com/contest/439/submission/6814314)
    103 * [[user:Gerald] solution](//codeforces.com/contest/439/submission/6814333)
    104 * [[user:triveni] solution using smart solution](//codeforces.com/contest/439/submission/6813224)
    105 
    106 ---
    107 
    108 **[439E - Devu and Birthday Celebration](/contest/439/problem/E "Codeforces Round 251 (Div. 2)")**
    109 
    110 There are two possible solutions.
    111 
    112 **dp solution**
    113 
    114 Let *P*(*n*, *f*) be total number of ways of partitioning *n* into *f* segments such that each *a**i* is positive. With some manipulations of the generating function, you can find that this is equal to ![](https://espresso.codeforces.com/043568bfa0e5f0eb5f90021b63172b0d9e049747.png).
    115 
    116 So ![](https://espresso.codeforces.com/25e9ecac69cd18c28ddb41be399fadd75696e8b4.png)
    117 
    118 Let *F*(*n*, *f*, *g*) denotes partitions of *n* into *f* parts such that gcd of all the *a**i*'*s* is *g*.
    119 
    120 Note that *F*(*n*, *f*, 1) = *P*(*n*, *f*) — sum of *F*(*n*, *f*, *g*) over all possible gcd *g*'*s*. So *g* will be a divisor of *n*.
    121 
    122 In other words, ![](https://espresso.codeforces.com/de0e059ef458c08d15999b8a3f172a1845a1676d.png)
    123 
    124 As ![](https://espresso.codeforces.com/0f8796f1ce9f45cd62869343d0b0c865b64fd84b.png).
    125 
    126 ![](https://espresso.codeforces.com/b50404260574037f3268436e8bc63aeac2e7fb4c.png)
    127 
    128 You can implement this solution by a simple dp.
    129 
    130 You can pre-calculate factorials which will help you to calculate ![](https://espresso.codeforces.com/52f41145102a57b7fb8168466b50806efeb81673.png).
    131 
    132 Complexity of this solution will be *nlogn* over all the test cases.
    133 
    134 Please note that this solution might get time limit exceeded in Java. Please read the [comment](//codeforces.com/blog/entry/12545#comment-173200).
    135 
    136 **Mathematical solution**
    137 
    138 Note that *F*(*n*, *f*, 1) = *P*(*n*, *f*) — sum of *F*(*n*, *f*, *g*) over all possible gcd *g*'*s* (*g* > 1 such that *g* is a divisor of *n*.
    139 
    140 In other words, ![](https://espresso.codeforces.com/9e2294a891ec5625369c50d3d60e1f940a93ca64.png)
    141 
    142 As *F*(*n*, *f*, *g*) = ![](https://espresso.codeforces.com/720730b902c5d8aaeae80d52331c71ff043f43ae.png).
    143 
    144 ![](https://espresso.codeforces.com/b50404260574037f3268436e8bc63aeac2e7fb4c.png)
    145 
    146 ![](https://espresso.codeforces.com/92a4aa49fa13119518adc7caa292586410cbd9e4.png)
    147 
    148 ![](https://espresso.codeforces.com/3947abaf62007e6a9463d22eef8302b2a4fd5fe8.png)
    149 
    150 Now you have to use [Möbius inversion formula.](https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula)
    151 
    152 **Theorem:**
    153 
    154 If *f* and *g* are two arithmetic functions satisfying
    155 
    156 ![](https://espresso.codeforces.com/fa39cd211340662a825c433be51437df565dbf59.png)
    157 
    158 then ![](https://espresso.codeforces.com/cdc60dc259eeb58eeb33bdbc1fdce33cabf3f540.png)
    159 
    160 So In our case: *g*(*n*) is *P*(*n*, *f*) and *f*(*n*) is *F*(*n*, *f*, 1).
    161 
    162 For proving complexity: Use the fact that total number of divisors of a number from 1 to *n* is ![](https://espresso.codeforces.com/629f7d5cb3dca2eddb260fa1b2d524631854c21c.png)
    163 
    164 Please also see [xorfire](/profile/xorfire "Candidate Master xorfire") [comment](//codeforces.com/blog/entry/12545#comment-172661) for understanding the relation between mobius function and the solution using inclusion exclusion principle.
    165 
    166 **Solution Codes**
    167 
    168 * [my solution using mobius function](//codeforces.com/contest/439/submission/6814328)
    169 * [[user:Gerald]'s code based on first solution](//codeforces.com/contest/439/submission/6814322)
    170 * [[user:Balajiganapathi,2014-06-05]'s inclusion exclusion principle](//codeforces.com/contest/439/submission/6814320)