codeforces-scrape

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

645.md (20118B)


      1 Source: https://codeforces.com/blog/entry/43868
      2 
      3 ## [645A - Amity Assessment](/contest/645/problem/A "CROC 2016 - Elimination Round")
      4 
      5 **Idea:** [yummy](/profile/yummy "International Master yummy")
      6 
      7 One solution is to just brute force and use DFS to try all the possibilities. Alternatively, note that two puzzles can be changed to each other if and only if the *A*, *B*, and *C* have the same orientation—clockwise or counterclockwise—in the puzzle. A third option, since the number of possibilities is so small, is to simply classify all of the 4! = 24 configurations by hand.
      8 
      9 **Code**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 string b, b1, b2, e, e1, e2;
     16 
     17 int main(){
     18   cin >> b1 >> b2 >> e1 >> e2;
     19   swap(b2[0], b2[1]);
     20   swap(e2[0], e2[1]);
     21   b = b1 + b2;
     22   e = e1 + e2;
     23   b.erase(b.find('X'), 1);
     24   e.erase(e.find('X'), 1);
     25   if((b + b).find(e) != string::npos){
     26 	cout << "YESn";
     27   } else {
     28 	cout << "NOn";
     29   }
     30 }
     31 ```
     32 
     33 ## [645B - Mischievous Mess Makers](/contest/645/problem/B "CROC 2016 - Elimination Round")
     34 
     35 **Idea: [ksun48](/profile/ksun48 "Master ksun48")**
     36 
     37 Loosely speaking, we’re trying to reverse the array as much as possible.
     38 
     39 Intuitively, the optimal solution seems to be to switch the first and last cow, then the second and second-to-last cow, and so on for *k* minutes, unless the sequence is reversed already, in which case we are done. But how can we show that these moves give the optimal messiness?
     40 
     41 It is clear when 2·*k* ≥ *n* - 1 that we can reverse the array with this method.
     42 
     43 However, when 2·*k* < *n* - 1, there are going to be cows that we must not have not moved a single time. Since in each move we swap at most 2 cows, there must be at least *n* - 2·*k* cows that we have not touched, with *p**i* = *i*. Two untouched cows *i* and *j* must have *p**i* < *p**j*, so there must be at least ![](https://espresso.codeforces.com/d21f52f2bd0094d162e5844a9bfcbeb5404d882f.png) pairs of cows which are ordered correctly.
     44 
     45 In fact, if we follow the above process, we get that *p**i* = (*n* + 1) - *i* for the first *k* and last *k* cows, while *p**i* = *i* for the middle *n* - 2·*k* cows. From this we can see that the both *i* < *j* and *p**i* < *p**j* happen only when *i* and *j* are in the middle *n* - 2·*k* cows. Therefore we know our algorithm is optimal.
     46 
     47 An *O*(*k*) solution, therefore, is to count how many incorrectly ordered pairs (*i*, *j*) are created at each step and add them up. When we swap cow *i* and (*n* + 1) - *i* in step *i*, this creates 1 + 2·(*n* - 2*i*) more pairs. So the answer will be ![](https://espresso.codeforces.com/ec7d47224527928305821eb1194e32cc6e0f7682.png).
     48 
     49 We can reduce this to *O*(1) by using our earlier observation, that every pair except those ![](https://espresso.codeforces.com/d21f52f2bd0094d162e5844a9bfcbeb5404d882f.png) pairs are unordered, which gives ![](https://espresso.codeforces.com/0c15cf272f68429ac57c834c276eff748510f317.png) total pairs (*i*, *j*). Note that this does always not fit in a 32-bit integer.
     50 
     51 **Code**
     52 
     53 ```
     54 #include<bits/stdc++.h>
     55 using namespace std;
     56 typedef long long LL;
     57 
     58 int main(){
     59 	LL n, k;
     60 	cin >> n >> k;
     61 	LL c = max(n-2*k,0LL);
     62 	LL a = n*(n-1)/2-c*(c-1)/2;
     63 	cout << a << endl;
     64 }
     65 ```
     66 
     67 ## [645C - Enduring Exodus](/contest/645/problem/C "CROC 2016 - Elimination Round")
     68 
     69 **Idea: [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP")**
     70 
     71 First, observe that the *k* + 1 rooms that Farmer John books should be consecutive empty rooms. Thus we can loop over all such sets of rooms with a sliding window in linear time. To check the next set of rooms, we simply advance each endpoint of our interval to the next empty room. Every time we do this, we need to compute the optimal placement of Farmer John’s room. We can maintain the position of his room with two pointers—as we slide our window of rooms to the right, the optimal position of Farmer John’s room should always move to the right or remain the same. This solution runs in *O*(*n*).
     72 
     73 Alternatively, we can use binary search or an STL set to find the best placement for Farmer John’s room as we iterate over the intervals of rooms. The complexity of these approaches is ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png).
     74 
     75 **Code**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 using namespace std;
     80 
     81 int N, K, res = 1e9;
     82 string S;
     83 
     84 int next(int i){ // finds the next empty room
     85   do {
     86     i += 1;
     87   } while(i < N && S[i] == '1');
     88   return i;
     89 }
     90 
     91 int main(){
     92   cin >> N >> K >> S;
     93   int l = next(-1), m = l, r = l;
     94   for(int i = 0; i < K; i++){ // sets up the sliding window
     95     r = next(r);
     96   }
     97   while(r < N){
     98     while(max(m - l, r - m) > max(next(m) - l, r - next(m))){
     99       m = next(m);
    100     }
    101     res = min(res, max(m - l, r - m));
    102     l = next(l);
    103     r = next(r);
    104   }
    105   cout << res << 'n';
    106 }
    107 ```
    108 
    109 ## [645D - Robot Rapping Results Report](/contest/645/problem/D "CROC 2016 - Elimination Round")
    110 
    111 **Idea: [abacadaea](/profile/abacadaea "Candidate Master abacadaea")**
    112 
    113 The robots will become fully sorted if and only if there exists a path with *n* vertices in the directed graph defined by the match results. Because it is guaranteed that the results are not contradictory, this graph must be directed and acyclic—a DAG. Thus we can compute the longest path in this DAG via dynamic programming or a toposort.
    114 
    115 We now have two cases. First, if the longest path contains *n* vertices, then it must uniquely define the ordering of the robots. This means the answer is the time at which the last edge was added to this path. Otherwise, if the longest path has fewer than *n* vertices, then multiple orderings satisfy the results and you should print  - 1. Note that this algorithm runs in *O*(*n* + *m*).
    116 
    117 Another solution to this problem binary searches on the answer. For some *k*, consider only those edges that were added before time *k*. We can determine if the robots could be totally ordered at time *k* by running a toposort and checking if the longest path covers all *n* vertices. This might be more intuitive for some, but has a complexity of ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png).
    118 
    119 **Code**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 using namespace std;
    124 
    125 const int MAXN = 1000005;
    126 int N, M, dp[MAXN], res[MAXN];
    127 vector<pair<int,int>> adj[MAXN];
    128 
    129 int check(int v){
    130   if(dp[v]) return dp[v];
    131   dp[v] = 1;
    132   for(auto p : adj[v]){
    133     int n = p.first;
    134     if(check(n) + 1 > dp[v]){
    135       dp[v] = dp[n] + 1;
    136       res[v] = max(res[n], p.second);
    137     }
    138   }
    139   return dp[v];
    140 }
    141 
    142 int main(){
    143   scanf("%d%d", &N, &M);
    144   for(int i = 0; i < M; i++){
    145     int a, b;
    146     scanf("%d%d", &a, &b);
    147     a -= 1, b -= 1;
    148     adj[a].push_back({b, i + 1});
    149   }
    150   for(int i = 0; i < N; i++){
    151     if(check(i) == N){
    152       printf("%dn", res[i]);
    153       return 0;
    154     }
    155   }
    156   printf("-1n");
    157 }
    158 ```
    159 
    160 ## [645E - Intellectual Inquiry](/contest/645/problem/E "CROC 2016 - Elimination Round")
    161 
    162 **Idea: [yummy](/profile/yummy "International Master yummy")**
    163 
    164 For simplicity, let’s represent the letters by 1, 2, ..., *k* instead of actual characters. Let *a*[*i*] denote the number of distinct subsequences of the string that end in the letter *i*. Appending the letter *j* to a string only changes the value of *a*[*j*]. Note that the new *a*[*j*] becomes ![](https://espresso.codeforces.com/c7edf894a914849579e45d3d86aa027649f48771.png)—we can have the single letter *j*, or append *j* to any of our old subsequences.
    165 
    166 The key observation is that no matter what character *j* we choose to append, *a*[*j*] will always end up the same. This suggests a greedy algorithm—always appending the character *j* with the smallest *a*[*j*]. But how do we know which *a*[*j*] is minimal while maintaining their values modulo 109 + 7?
    167 
    168 The final observation is that if the last occurrence of *j* is after the last occurrence of *j*' in our string, then *a*[*j*] > *a*[*j*']. This is true because appending *j* to the string makes *a*[*j*] larger than all other *a*[*i*]. So instead of choosing the minimum *a*[*i*], we can always choose the letter that appeared least recently. Since the sequence of letters we append becomes periodic, our solution runs in ![](https://espresso.codeforces.com/3637f1eccbdb1c0b0ab23fd397b679a406e9e78b.png). Of course, we can also find the least recently used letter with less efficient approaches, obtaining solutions with complexity *O*((*L* + *n*)*k*).
    169 
    170 **Code**
    171 
    172 ```
    173 #include <bits/stdc++.h>
    174 using namespace std;
    175 
    176 typedef long long ll;
    177 
    178 const ll MOD = 1000000007;
    179 const int MAXK = 26;
    180 int N, K, last[MAXK], ord[MAXK];
    181 ll dp[MAXK], sum;
    182 string S;
    183 
    184 bool comp(int a, int b){
    185   return last[a] < last[b];
    186 }
    187 
    188 void append(int c){
    189   sum = (sum - dp[c] + MOD) % MOD;
    190   dp[c] = (dp[c] + sum + 1) % MOD;
    191   sum = (sum + dp[c]) % MOD;
    192 }
    193 
    194 int main(){
    195   cin >> N >> K >> S;
    196   fill(last, last + K, -1);
    197   for(int i = 0; i < S.size(); i++){
    198     int c = S[i] - 'a';
    199     last[c] = i;
    200     append(c);
    201   }
    202   iota(ord, ord + K, 0);
    203   sort(ord, ord + K, comp);
    204   for(int i = 0; i < N; i++){
    205     int c = ord[i % K];
    206     append(c);
    207   }
    208   cout << (sum + 1) % MOD << 'n';
    209 }
    210 ```
    211 
    212 ## [645F - Cowslip Collections](/contest/645/problem/F "CROC 2016 - Elimination Round")
    213 
    214 **Idea: [desert97](/profile/desert97 "Master desert97")**
    215 
    216 After each query, the problem is essentially asking us to compute the sum of ![](https://espresso.codeforces.com/cd7483d3847d48f93a6326e1bab9d15a6d56487e.png) for each choice of *k* flowers. One quickly notes that it is too slow to loop over all choices of *k* flowers, as there could be up to ![](https://espresso.codeforces.com/eca84b293f083780b73a20a007ddcb2181fa3151.png) choices of *k* species.
    217 
    218 So how can we compute a sum over ![](https://espresso.codeforces.com/eca84b293f083780b73a20a007ddcb2181fa3151.png) terms? Well, we will definitely need to use the properties of the gcd function. If we figure out for each integer *a* ≤ 106 how many times ![](https://espresso.codeforces.com/00e945fdfd28fbb44e7c68b0081f986b394ce44b.png) occurs in the sum (let this be *g*(*a*)), then our answer will be equal to ![](https://espresso.codeforces.com/fbcd6882a5d4bd39ca61a2866600e061a32ac784.png) overall all *a*.
    219 
    220 It seems that if *d*(*a*) is the number of multiples of *a* in our sequence, then there are ![](https://espresso.codeforces.com/84308455eef51133bdc404d915a909c5e0175ecc.png) *k*-tuples which have gcd *a*. Yet there is something wrong with this reasoning: some of those *k*-tuples can have gcd 2*a*, or 3*a*, or any multiple of *a*. In fact, ![](https://espresso.codeforces.com/3fe61b43650120c845f6bc02d78e75bdbb2d668b.png), the number of gcds which are a multiple of *a*.
    221 
    222 We will try to write ![](https://espresso.codeforces.com/fbcd6882a5d4bd39ca61a2866600e061a32ac784.png) as a sum of these ![](https://espresso.codeforces.com/2dbb1cf2ef4725f0896032842be34c7b3d39900b.png). We’ll take an example, when *a* ranges from 1 to 4. The sum we wish to compute is *g*(1) + 2*g*(2) + 3*g*(3) + 4*g*(4) which can be written as
    223 
    224 (*g*(1) + *g*(2) + *g*(3) + *g*(4)) + (*g*(2) + *g*(4)) + 2(*g*(3)) + 2(*g*(4)), 
    225 
    226 or
    227 
    228 ![](https://espresso.codeforces.com/dc1f9d1625374319b107d06712dd59e1b5c28739.png)
    229 
    230 In general, we want to find coefficients *p**i* such that we can write ![](https://espresso.codeforces.com/fbcd6882a5d4bd39ca61a2866600e061a32ac784.png) as ![](https://espresso.codeforces.com/2deafb263e540c8afeca519649db8c764752e8eb.png). Equating coefficients of *g*(*a*) on both sides, we get that ![](https://espresso.codeforces.com/8871e7c7f9e21657fad7096b093da4064378d320.png). (The mathematically versed reader will note that *p**i* = φ(*i*), Euler's totient function, but this is not necessary to solve the problem.)
    231 
    232 We can thus precalculate all *p**i* in ![](https://espresso.codeforces.com/f015c286d2e5c88e8f1810d526c23bc54dfe7357.png) using a recursive formula: ![](https://espresso.codeforces.com/78eecce31f344eb2317bd775efd28cffe6b24464.png). We can also precalculate ![](https://espresso.codeforces.com/928671037124ed697c1167b17adb99cffc135a20.png) for each *l* ≤ 200000, so in order to output ![](https://espresso.codeforces.com/f64315debb7a62c64e4467711ede27f5af8e09fd.png) after each query we should keep track of the values of the function *d*(*i*), the number of multiples of *i*. When receiving *c**i* flowers, we only need to update *d* for the divisors of *c**i* and add ![](https://espresso.codeforces.com/9d9d7b2ff5d128e19266906d3f27973058c9170a.png). If we precompute the list of divisors of every integer using a sieve or sqrt checking, each update requires *O*(*divisors*).
    233 
    234 Thus the complexity of this algorithm is ![](https://espresso.codeforces.com/7d7e317c3b81d2f099280a3a3a7d47ddf6b5bb25.png) or ![](https://espresso.codeforces.com/7d23bde938d1df17fc001b65f49c7f9c6e5dafaa.png) preprocessing, and *O*((*n* + *q*)·*max*(*divisors*)).
    235 
    236 **Code**
    237 
    238 ```
    239 #include <bits/stdc++.h>
    240 using namespace std;
    241 
    242 typedef long long ll;
    243 
    244 const ll MOD = 1000000007;
    245 const int MAXN = 200005;
    246 const int MAXA = 1000005;
    247 int N, K, Q, A[MAXN];
    248 int use[MAXA], phi[MAXA], cnt[MAXA];
    249 vector<int> divisors[MAXA];
    250 ll bin[MAXN], res;
    251 
    252 ll inv(ll a, ll p){
    253   if(a == 1) return 1;
    254   return (p - p / a) * inv(p % a, p) % p;
    255 }
    256 
    257 void read(){
    258   scanf("%d%d%d", &N, &K, &Q);
    259   for(int i = 0; i < N + Q; i++){
    260     scanf("%d", &A[i]);
    261     use[A[i]] = 1;
    262   }
    263 }
    264 
    265 void init(){
    266   iota(phi, phi + MAXA, 0);
    267   for(int i = 1; i < MAXA; i++){
    268     for(int j = i; j < MAXA; j += i){
    269       if(i != j) phi[j] -= phi[i];
    270       if(use[j]) divisors[j].push_back(i);
    271     }
    272   }
    273   bin[K - 1] = 1;
    274   for(int i = K; i < MAXN; i++){
    275     bin[i] = bin[i - 1] * i % MOD * inv(i - K + 1, MOD) % MOD;
    276   }
    277 }
    278 
    279 int main(){
    280   read();
    281   init();
    282   for(int i = 0; i < N + Q; i++){
    283     for(int d : divisors[A[i]]){
    284       res = (res + bin[cnt[d]] * phi[d]) % MOD;
    285       cnt[d] += 1;
    286     }
    287     if(i >= N){
    288       printf("%dn", res);
    289     }
    290   }
    291 }
    292 ```
    293 
    294 ## [645G - Armistice Area Apportionment](/contest/645/problem/G "CROC 2016 - Elimination Round")
    295 
    296 **Idea: [yummy](/profile/yummy "International Master yummy")**
    297 
    298 Thanks to [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage") and [Petr](/profile/Petr "Legendary Grandmaster Petr") for sharing a solution with me that is much more intuitive than the one I originally had in mind! It works as follows:
    299 
    300 First, let’s try to solve the smaller case where we only have two points. Let ![](https://espresso.codeforces.com/c7c068229f25f741e2c902b657ba04a42feb0752.png) be the line passing through *x**i* and *x**j*. We want to compute the difference of ![](https://espresso.codeforces.com/c7c068229f25f741e2c902b657ba04a42feb0752.png) relative to *P* and *Q*. Define *P*’ as the reflection of *P* over ![](https://espresso.codeforces.com/c7c068229f25f741e2c902b657ba04a42feb0752.png). By the triangle inequality, we have |*PX* - *QX*| = |*P*’*X* - *QX*| ≤ *P*’*Q*. Equality can be achieved when *X*, *P*’ and *Q* are collinear—that is, when *X* is the intersection of ![](https://espresso.codeforces.com/c7c068229f25f741e2c902b657ba04a42feb0752.png) and line *P*’*Q*. (If ![](https://espresso.codeforces.com/c7c068229f25f741e2c902b657ba04a42feb0752.png) and *P*’*Q* are parallel, we can imagine that they intersect at infinity.) Therefore, the difference of a line ![](https://espresso.codeforces.com/c7c068229f25f741e2c902b657ba04a42feb0752.png) relative to *P* and *Q* is the distance from *P*’ to *Q*.
    301 
    302 We can also think about *P*’ in a different way. Let *C**i* be the circle with center *x**i* that pases through *P*. Then *P*’ is the second intersection of the two circles *C**i* and *C**j*. Thus our problem of finding a line with minimum difference becomes equivalent to finding the intersection among {*C**i*} that lies closest to *Q*. This last part we can do with a binary search.
    303 
    304 Consider the problem of checking if two circles *C**i* and *C**j* intersect at a point within a distance *r* of *Q*. In other words, we wish to check if they intersect inside a circle *S* of radius *r* centered at *Q*. Let *A**i* and *A**j* be the arcs of *S* contained by *C**i* and *C**j*, respectively. Observe that *C**i* and *C**j* intersect inside the circle if and only if the two arcs overlap, but do not contain each other. Thus we can verify this condition for all pairs of points with a radial sweep line along the circle. Due to the binary search and the sorting necessary for the sweep line, this solution runs in ![](https://espresso.codeforces.com/329f3247e826224b3d6979bf4c71aaf08c8aa93e.png), where *P* is the precision required.
    305 
    306 One might also wonder if precision will be an issue with all the calculations that we’re doing. It turns out that it won’t be, since our binary search will always stabilize the problem and get us very close to the answer.
    307 
    308 Here’s my original solution using a projective transformation:
    309 
    310 We begin by binary searching on the the minimum possible difference. Thus we wish to solve the decision problem "Can a difference of *k* be achieved?" Consider the hyperbola |*PX* - *QX*| = *k*. Note that our answer is affirmative if and only if a pair of outposts defines a line that does not intersect the hyperbola.
    311 
    312 Our next step is a reduction to an equivalent decision problem on a circle through a projective transformation. We express this transformation as the composition of two simpler operations. The first is an affine map that takes the hyperbola |*PX* - *QX*| = *k* to the unit hyperbola. The second maps homogenous coordinates (*x*, *y*, *z*) to (*z*, *y*, *x*). Under the latter, the unit hyperbola *x*2 - *y*2 = *z*2 goes to the unit circle *x*2 + *y*2 = *z*2.
    313 
    314 Because projective transformations preserve collinearity, a line intersecting the hyperbola is equivalent to a line intersecting the circle. Thus we want to know if any pair of the outposts' images defines a line that does not intersect the circle. We now map the image of each outpost to the minor arc on the unit circle defined by its tangents. (We disregard any points lying inside the circle.) Observe that our condition is equivalent to the existence of two intersecting arcs, neither of which contains the other. Verifying that two such arcs exist can be done with a priority queue and a radial sweep line in ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png).
    315 
    316 The total complexity of our solution is therefore ![](https://espresso.codeforces.com/e17c7f516898285764ec01316a1a64b2bb98b32c.png), where *P* is the precision that we need. It turns out that the implementation of this algorithm is actually pretty neat:
    317 
    318 **Code**
    319 
    320 ```
    321 #include <bits/stdc++.h>
    322 using namespace std;
    323 
    324 typedef long double ld;
    325 
    326 const ld EPS = 1e-12;
    327 const ld PI = acos(-1);
    328 const int MAXN = 100005;
    329 int N;
    330 ld A, X[MAXN], Y[MAXN];
    331 
    332 bool check(ld m){
    333   ld u = m / 2;
    334   ld v = sqrt(A * A - u * u);
    335   vector<pair<ld,ld>> ev;
    336   for(int i = 0; i < N; i++){
    337     ld x = 1, y = Y[i] / v, alpha;
    338     if(X[i] != 0){
    339       x *= u / X[i], y *= u / X[i];
    340       ld r = sqrt(x * x + y * y);
    341       if(r < 1) continue;
    342       alpha = acos(1 / r);
    343     } else {
    344       alpha = PI / 2;
    345     }
    346     ld base = atan2(y, x) - alpha;
    347     if(base < 0) base += 2 * PI;
    348     ev.push_back({base, base + 2 * alpha});
    349   }
    350   priority_queue<ld, vector<ld>, greater<ld>> pq;
    351   sort(ev.begin(), ev.end());
    352   for(int i = 0; i < 2; i++){
    353     for(int j = 0; j < ev.size(); j++){
    354       while(pq.size() && pq.top() < ev[j].first) pq.pop();
    355       if(pq.size() && pq.top() < ev[j].second) return 1;
    356       pq.push(ev[j].second);
    357       ev[j].first += 2 * PI;
    358       ev[j].second += 2 * PI;
    359     }
    360   }
    361   return 0;
    362 }
    363 
    364 int main(){
    365   ios::sync_with_stdio(0);
    366   cin >> N >> A;
    367   for(int i = 0; i < N; i++){
    368     cin >> X[i] >> Y[i];
    369   }
    370   ld lo = 0, hi = 2 * A;
    371   while(hi - lo > EPS){
    372     ld mid = (lo + hi) / 2;
    373     (check(mid) ? hi : lo) = mid;
    374   }
    375   cout << fixed << setprecision(10);
    376   cout << (lo + hi) / 2 << 'n';
    377 }
    378 ```