codeforces-scrape

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

550.md (7570B)


      1 Source: https://codeforces.com/blog/entry/18329
      2 
      3 ## [550A - Two Substrings](/contest/550/problem/A "Codeforces Round 306 (Div. 2)")
      4 
      5 There are many ways to solve this problem. Author solution does the following: check if substring "AB" goes before "BA", and then vice versa, if "BA" goes before "AB".
      6 
      7 You can do it in the following way: find the first occurence of "AB" then check all substrings of length two to the right of it to check if substring "BA" also exists. Then do it vice versa.
      8 
      9 Complexity of the solution is *O*(*n*), where *n* is the length of the given string.
     10 
     11 ## [550B - Preparing Olympiad](/contest/550/problem/B "Codeforces Round 306 (Div. 2)")
     12 
     13 Because of the low constraints, this problem can be solved by complete search over all problem sets (there are 2*n* of them).
     14 
     15 For every potential problem set (which can be conviniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most difficult and the easiest problems in linear time, iterating over the problems that we included in our current set/bitmask. If this problem set can be used, we increase the answer by one.
     16 
     17 Complexity of this solution is *O*(2*n*·*n*).
     18 
     19 ## [550C - Divisibility by Eight](/contest/550/problem/C "Codeforces Round 306 (Div. 2)")
     20 
     21 This problem can be solved with at least two different approaches.
     22 
     23 The first one is based on the "school" property of the divisibility by eight — number can be divided by eight if and only if its last three digits form a number that can be divided by eight. Thus, it is enough to test only numbers that can be obtained from the original one by crossing out and that contain at most three digits (so we check only all one-digit, two-digit and three-digit numbers). This can be done in *O*(*len*3) with three nested loops (here *len* is the length of the original number).
     24 
     25 Second approach uses dynamic programming. Let's calculate *dp*[*i*][*j*], 1 ≤ *i* ≤ *n*, 0 ≤ *j* < 8. The value of dp is true if we can cross out some digits from the prefix of length *i* such that the remaining number gives *j* modulo eight, and false otherwise.
     26 
     27 This dp can be calculated in the following way: let *a**i* be *i*th digit of the given number. Then *dp*[*i*][*a**i**mod*8] = *true* (just this number). For all 0 ≤ *j* < 8 such that *dp*[*i* - 1][*j*] = *true*, *dp*[*i*][(*j* * 10 + *a**i*)*mod*8] = *true* (we add current digit to some previous result), *dp*[*i*][*j*] = *true* (we cross out current digit).
     28 
     29 Answer is "YES" if *dp*[*i*][0] = *true* for some position *i*. For restoring the answer we need to keep additional array *prev*[*i*][*j*], which will say from where current value was calculated. Complexity of such solution is *O*(8·*len*) = *O*(*len*) (again *len* is the length of the original number).
     30 
     31 Code for DP solution:
     32 
     33 **Spoiler**
     34 
     35 ```
     36 #include <bits/stdc++.h>
     37  
     38 using namespace std;
     39  
     40 #define sz(x) (int) x.size()
     41 #define all(a) a.begin(), a.end()
     42 #define prev sadasdjksgjkasjdklaj
     43  
     44 const int MAXN = 105;
     45  
     46 string s;
     47 int n;
     48 bool dp[MAXN][8];
     49 int prev[MAXN][8];
     50  
     51 int main() {
     52  
     53     getline(cin, s);
     54     n = sz(s);
     55  
     56     memset(prev, -1, sizeof(prev));
     57  
     58     dp[0][(s[0] - '0') % 8] = true;
     59  
     60     for (int i = 1; i < n; i++) {
     61         dp[i][(s[i] - '0') % 8] = true;
     62  
     63         for (int j = 0; j < 8; j++) {
     64             if (dp[i - 1][j]) {
     65                 dp[i][(j * 10 + s[i] - '0') % 8] = true;
     66                 prev[i][(j * 10 + s[i] - '0') % 8] = j;
     67  
     68                 dp[i][j] = true;
     69                 prev[i][j] = j;
     70             }
     71         }
     72     }
     73  
     74     for (int i = 0; i < n; i++) {
     75         if (dp[i][0]) {
     76             string ans = "";
     77             int curI = i, curJ = 0;
     78  
     79             while (true) {
     80                 if (prev[curI][curJ] == -1 || prev[curI][curJ] != curJ) {
     81                     ans.append(1, s[curI]);
     82                 }
     83  
     84                 if (prev[curI][curJ] == -1) break;
     85  
     86                 curJ = prev[curI][curJ];
     87                 curI--;
     88             }
     89  
     90             puts("YES");
     91             reverse(all(ans));
     92             cout << ans << endl;
     93             return 0;
     94         }
     95     }
     96  
     97     puts("NO");
     98  
     99     return 0;
    100 }
    101 ```
    102 
    103 ## [550D - Regular Bridge](/contest/550/problem/D "Codeforces Round 306 (Div. 2)")
    104 
    105 Let's prove that there is no solution for even *k*.
    106 
    107 Suppose our graph contains some bridges, *k* = 2*s* (even), all degrees are *k*. Then there always exists strongly connected component that is connected to other part of the graph with exactly one bridge.
    108 
    109 Consider this component. Let's remove bridge that connects it to the remaining graph. Then it has one vertex with degree *k* - 1 = 2*s* - 1 and some vertices with degrees *k* = 2*s*. But then the graph consisting of this component will contain only one vertex with odd degree, which is impossible by Handshaking Lemma.
    110 
    111 Let's construct the answer for odd *k*. Let *k* = 2*s* - 1.
    112 
    113 For *k* = 1 graph consisting of two nodes connected by edge works.
    114 
    115 For *k* ≥ 3 let's construct graph with 2*k* + 4 nodes. Let it consist of two strongly connected components connected by bridge. Enumerate nodes of first component from 1 to *k* + 2, second component will be the same as the first one.
    116 
    117 Let vertex 1 be connected to the second component by bridge. Also connect it with *k* - 1 edges to vertices 2, 3, ..., *k*. Connect vertices 2, 3, ..., *k* to each other (add all possible edges between them), and then remove edges between every neighbouring pair, for example edges 2 - 3, 4 - 5, ..., (*k* - 1) - *k*.
    118 
    119 Then we connect vertices 2, 3, ..., *k* with vertices *k* + 1 and *k* + 2. And finally add an edge between nodes *k* + 1 and *k* + 2.
    120 
    121 Build the second component in the similar manner, and add a bridge between components. Constructed graph has one bridge, all degrees of *k* and consists of *O*(*k*) nodes and *O*(*k*2) edges.
    122 
    123 Complexity of the solution — *O*(*k*2).
    124 
    125 ## [550E - Brackets in Implications](/contest/550/problem/E "Codeforces Round 306 (Div. 2)")
    126 
    127 Let input consists of ![](https://espresso.codeforces.com/80095dcd87e10e1179bb37b912c210fa334d214c.png), *a**i* is 0 or 1 for all *i*.
    128 
    129 Let's show that there is no solution in only two cases:
    130 
    131 1) *a**n* = 1.
    132 
    133 ![](https://espresso.codeforces.com/b405779007d14be982d3a17dc0b46531d1fec735.png), for all *x*, and no parentheses can change last 1 to 0.
    134 
    135 2) Input has the form ![](https://espresso.codeforces.com/2f028ff603c9781bb3479d4d517df830db22fb21.png) or its suffix with at least two arguments.
    136 
    137 This can be proven by induction. For input ![](https://espresso.codeforces.com/8b64b6532c8c8e1095f1992c08bcd00eecaabf95.png) there is no solution, for longer inputs any attempt to put parentheses will decrease the number of 1s in the beginning by one, or will introduce 1 in the last position (which will lead to case one).
    138 
    139 Let's construct solution for all other cases.
    140 
    141 1) For input 0 we don't need to do anything.
    142 
    143 2) For input of the form ![](https://espresso.codeforces.com/e527b1a1db69043f38ad7a1511e4e268e411cc0d.png) we don't need any parentheses, the value of this expression is always
    144 
    145 3) Expression in the form ![](https://espresso.codeforces.com/92c9ad62ed6b76a25f87b66d3dce97686b8ab177.png) (where second missed part consists of ones only). Then ![](https://espresso.codeforces.com/c235ef6be544c0f18527428645b42783e7db6d6b.png).
    146 
    147 Complexity of the solution is *O*(*n*).