codeforces-scrape

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

991.md (15182B)


      1 Source: https://codeforces.com/blog/entry/60181
      2 
      3 [991A - If at first you don't succeed...](/contest/991/problem/A "Codeforces Round 491 (Div. 2)")
      4 
      5 **Editorial**
      6 
      7 There are 4 groups of students — those who visited only the first restaurant, who visited only the second, who visited both places and who stayed at home. One of the easiest ways to detect all the incorrect situations is to calculate number of students in each group. For the first group it is *A* - *C*, for the second: *B* - *C*, for the third: *C* and for the fourth: *N* - *A* - *B* + *C*. Now we must just to check that there are non-negative numbers in the first three groups and the positive number for the last group. If such conditions are met the answer is the number of students in the fourth group.
      8 
      9 ```
     10 	int n1 = a - c;
     11 	int n2 = b - c;
     12 	int n3 = c;
     13 	int n4 = n - n1 - n2 - n3;
     14 
     15 	if (n1 >= 0 && n2 >= 0 && n3 >= 0 && n4 > 0)
     16 		cout << n4;
     17 	else
     18 		cout << -1;
     19 ```
     20 
     21 In general you are recommended to view [inclusion–exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle).
     22 
     23 Moreover the limitations allow to go over all possible numbers of students for each group (except for the third) in *O*(*N*3) and to check whether such numbers produce a correct solution. If no correct numbers found, just print  - 1:
     24 
     25 ```
     26 	int n3 = c;
     27 	for (int n1 = 0; n1 <= n; n1++)
     28 		for (int n2 = 0; n2 <= n; n2++)
     29 			for (int n4 = 1; n4 <= n; n4++)
     30 				if (n1 + n3 == a && n2 + n3 == b && n1 + n2 + n3 + n4 == n) {
     31 					cout << n4;
     32 					return 0;
     33 				}
     34 	cout << -1;
     35 ```
     36 
     37 [Solution1](https://pastebin.com/Zy6F6Zhz)
     38 
     39 [Solution2](https://pastebin.com/YB289ebH)
     40 
     41 [991B - Getting an A](/contest/991/problem/B "Codeforces Round 491 (Div. 2)")
     42 
     43 **Editorial**
     44 
     45 It is necessary to use the greedy approach: of course Vasya should redo the lowest grades firstly. So we have to sort the values in the ascending order and begin to replace the values by 5 until we get the desired result. In order to check whether the current state is suitable we may calculate the mean value after each iteration (*O*(*N*2) complexity in total), or just update sum of the grades and calculate the arithmetic mean in *O*(1) with *O*(*N*) total complexity (excluding sorting). For example:
     46 
     47 ```
     48 bool check(int sum, int n) {
     49 	// integer representation of sum / n >= 4.5
     50 	return sum * 10 >= n * 45;
     51 }
     52 
     53 int main() {
     54 	... // read integers to vector v and calculate sum
     55 	sort(v.begin(), v.end());
     56 	int ans = 0;
     57 	while (!check(sum, n)) {
     58 		sum += 5 - v[ans];
     59 		ans++;
     60 	}
     61 	cout << ans;
     62 }
     63 ```
     64 
     65 Of course, both approaches easily fit TL.
     66 
     67 Finally, it is recommended to avoid floating-point operations while calculating the mean value.
     68 
     69 [Solution](https://pastebin.com/cwYqVdLC)
     70 
     71 [991C - Candies](/contest/991/problem/C "Codeforces Round 491 (Div. 2)")
     72 
     73 **Editorial**
     74 
     75 It is easy to check that if for some value *k* the necessary condition is met (Vasya eats at least half of the candies), then it is met for each integer greater *k*.
     76 
     77 **Proof**
     78 
     79 Let's consider the number of candies remaining at the evening of each day for some selected *k*1 — let *a**i* candies remain at day *i*. If Vasya will use another number *k*2 > *k*1 we will have less candies in the first day: *b*1 < *a*1. So Petya will eat no more candies than in the first case (for *k*1), but in the next day the number of candies will be not greater than in the first case (if *n*1 > *n*2 then *n*1 - *n*1 / 10 ≥ *n*2 - *n*2 / 10). The same way, including that *k*2 > *k*1 at the evening of the second day we get *b*2 < *a*2 and so on. In general, for each *i* we have *b**i* < *a**i*, so Petya will eat not more candies than in the first case in total. It means that Vasya will eat not less candies than in the first case.
     80 
     81 So this problem can be solved using the binary search (answer) approach. In order to check whether selected *k* is applicable it necessary just to implement the process described in the problem statement.
     82 
     83 ```
     84 bool check(long long k, long long n) {
     85 	long long sum = 0;
     86 	long long cur = n;
     87 	while (cur > 0) {
     88 		long long o = min(cur, k);
     89 		sum += o;
     90 		cur -= o;
     91 		cur -= cur / 10;
     92 	}
     93 	return sum * 2 >= n;
     94 }
     95 ```
     96 
     97 Since Petya eats 10% of candies, its amount decreases **exponentially**, so there will be only few days before all the candies will be eaten. In the worst case it is necessary 378 days. Formally the complexity of the solution is *O*(*log*(*n*)2).
     98 
     99 Like in the previous problem it is recommended to avoid floating operations and to use only integer types.
    100 
    101 [Solution](https://pastebin.com/cYNpvWrQ)
    102 
    103 [991D - Bishwock](/contest/991/problem/D "Codeforces Round 491 (Div. 2)")
    104 
    105 **Editorial**
    106 
    107 In this problem we may use the greedy approach. Let's go through columns from left to right. If we are currently considering column *i* and we may place a figure occupying only cells at columns *i* and *i* + 1, we have to place this figure. Really if the optimal solution doesn't contain a bishwock at column *i* then column *i* + 1 may be occupied by at most one bishwock. So we can remove this figure and place it at columns *i* and *i* + 1, the result will be at least the same.
    108 
    109 A bit harder question is — how exactly we should place the figure if all 4 cells of columns *i* and *i* + 1 are empty (in other cases there will be only one way to place a bishwock)? Of course, we should occupy both cells of column *i*. Moreover it does not matter which cell we will occupy at column *i* + 1 in this case. The cells of *i* + 1 may be used only for placing a bishwock in columns *i* + 1,*i* + 2. If column *i* + 2 has at most one empty cell we are unable to place such figure and the remaining empty cells of column *i* + 1 are useless at all. If both cells of column *i* + 2 are empty we may place a bishwock regardless of the position of the remaining empty cell at column *i* + 1.
    110 
    111 It means that we don't have to place the figures actually — we have to calculate and update number of empty cells in columns. According to the described algorithm we may write such code:
    112 
    113 ```
    114 	... // read strings s[0] and s[1]
    115 	int ans = 0;
    116 	int previous = 0;
    117 	for (int i = 0; i < n; i++) {
    118 		int current = (s[0][i] == '0') + (s[1][i] == '0');
    119 		if (current == 0)
    120 			previous = 0;
    121 		if (current == 1) {
    122 			if (previous == 2) {
    123 				ans++;
    124 				previous = 0;
    125 			}
    126 			else
    127 				previous = 1;
    128 		}
    129 		if (current == 2) {
    130 			if (previous > 0) {
    131 				ans++;
    132 				if (previous == 2)
    133 					previous = 1;
    134 				else
    135 					previous = 0;
    136 			}
    137 			else
    138 				previous = 2;
    139 		}
    140 	}
    141 ```
    142 
    143 Moreover this implementation can be simplified to just two cases:
    144 
    145 ```
    146 	int ans = 0;
    147 	int empty = 0;
    148 	for (int i = 0; i < n; i++) {
    149 		int current = (s[0][i] == '0') + (s[1][i] == '0');
    150 		empty += current;
    151 		if (empty >= 3) {
    152 			empty -= 3;
    153 			ans++;
    154 		}
    155 		else
    156 			empty = current;
    157 	}
    158 ```
    159 
    160 Formally such algorithm may be considered as the dynamic programming. Of course it is not necessary to have a deep understanding of DP to write such implementation and solve the problem.
    161 
    162 This problem also can be solved by more ''obvious'' DP approach (for example we may consider index of current column and state of the cells of the previous column as a state of DP). In this case the implementation will be a bit more complicated but it won't be necessary to prove described solution.
    163 
    164 [Solution1](https://pastebin.com/4L3kwNWZ)
    165 
    166 [Solution2](https://pastebin.com/4dnyBusL)
    167 
    168 [991E - Bus Number](/contest/991/problem/E "Codeforces Round 491 (Div. 2)")
    169 
    170 **Editorial**
    171 
    172 According to the statement, digits of original bus number form a subset of digits of the number seen by Vasya. It is possible to iterate through all the subsets in 2*k* operations (where *k* is length of *n*). For each subset we need to check whether it is correct (contains all necessary digits) and transform it to ''normal'' state (sort the digits for example), in order to avoid conflicts with another subsets which differ only at the digits order. We have to keep only unique subsets.
    173 
    174 ```
    175 	long long ans = 0;
    176 	for (int i = 1; i <= (1 << k); i++) {
    177 		string c;
    178 		for (int j = 0; j < k; j++)
    179 			if (i & (1 << j))
    180 				c += n[j];
    181 		ans += getans(c);
    182 	}
    183 ```
    184 
    185 Now for each subset of digits we have to calculate amount of corresponding correct bus numbers. It can be calculated in *O*(*k*) operations using permutations of multisets formula (see ''Permutations of multisets'' at the article about [permutations](https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets) and [multinomial coefficients](https://en.wikipedia.org/wiki/Multinomial_theorem))
    186 
    187 *C* = *k*! / (*c*0! * *c*1! * ... * *c*9!),
    188 
    189 where *k* — total number of digits in the subset and *c**i* — number of digits *i*:
    190 
    191 ```
    192 long long fact[20];
    193 int c[10];
    194 
    195 void split(string s, int *c) {
    196 	for (int i = 0; i < 10; i++)
    197 		c[i] = 0;
    198 	for (char ch : s)
    199 		c[ch - 48]++;
    200 }
    201 
    202 long long getCount() {
    203 	long long ans = fact[accumulate(c, c + 10, 0)];
    204 	for (int i = 0; i < 10; i++)
    205 		ans /= fact[c[i]];
    206 	return ans;
    207 }
    208 ```
    209 
    210 Now, we have to subtract amount of bus numbers with leading zeroes from the result for this subset if it contains digit 0. This can be done in the very same way: if we place digit 0 at the first position of the number, we have to decrease *k* by 1 and decrease *c*0 by 1; the formula described above will calculate amount of ways to place remaining digits of the subset and this number should be subtract from the answer:
    211 
    212 ```
    213 long long getans(string s) {
    214 	split(s, c);
    215 
    216 	// check whether the string contains all digits
    217 	for (int i = 0; i < 10; i++)
    218 		if (c0[i] && !c[i])
    219 			return 0;
    220 
    221 	// check whether we already processed such string
    222 	sort(s.begin(), s.end());
    223 	if (was.count(s))
    224 		return 0;
    225 	was.insert(s);
    226 
    227 	long long ans = getCount();
    228 	if (c[0] > 0) {
    229 		c[0]--;
    230 		ans -= getCount();
    231 	}
    232 	return ans;
    233 }
    234 ```
    235 
    236 In total, even with such rough evaluation of complexity and naive implementation we get *O*(2*k* * *k*) operations, where *k* ≤ 19 — amount of digits in *n*. It is easy to check that the answer doesn't exceed 1018 so the standard 64-bit integer type will be enough.
    237 
    238 [Solution](https://pastebin.com/CY5V5dDz)
    239 
    240 [991F - Concise and clear](/contest/991/problem/F "Codeforces Round 491 (Div. 2)")
    241 
    242 **Editorial**
    243 
    244 All the problem numbers (except for 1010, which is given in the samples) contain at most 10 digits. It means that we have to use at most 9 digits if we want to find a shorter representation. Notice that the length of sum of two integers is not greater than sum of the lengths of these integers, so in the optimal representation at most one term is a number while other terms are expressions containing `*` and/or `^`. Each expression (not a number) contains at least 3 symbols, so the optimal representation can contain at most 3 terms. The maximal integer that can be represented in such manner is `9^9+9^9+9`, but it contains only 9 digits while expressions with 3 terms always contain at least 9 symbols. So we proved that there always exists an optimal representation which is a sum of at most two terms.
    245 
    246 So there exist only 3 types of representation of the original number:
    247 
    248 1. `n = a^b`
    249 2. `n = x+y`
    250 3. `n = x*y`
    251 
    252 where *x* and *y* — some expressions (in the first case *a* and *b* are numbers), which doesn't contain `+`. Moreover in all the cases such expressions should contain at most 7 digits.
    253 
    254 Let's find for each *x* ≤ *n* a shortest valid representation *m*[*x*], containing at most 7 symbols (if it exists and contains less digits than simple number *x*), and for each length *d* — set of integers *s*[*d*] which can be represented by an expression of length *d*. The standard containers (std::map and std::set в C++) are suitable for that:
    255 
    256 ```
    257 map<long long, string> m;
    258 set<long long> s[10];
    259 
    260 string get(long long x) {
    261 	if (m.count(x))
    262 		return m[x];
    263 	return toString(x);
    264 }
    265 
    266 void relax(long long x, string str) {
    267 	// obviously not optimal
    268 	if (x > n || str.length() >= getlen(x))
    269 		return;
    270 
    271 	// already have better
    272 	if (m.count(x) && m[x].length() <= str.length())
    273 		return;
    274 
    275 	s[m[x].length()].erase(x);
    276 	m[x] = str;
    277 	s[str.length()].insert(x);
    278 }
    279 ```
    280 
    281 Firstly let's add all expressions `a^b`, there are about `sqrt(n)` such expressions.
    282 
    283 ```
    284 void generatePowers() {
    285 	for (long long x = 2; x * x <= n; x++) {
    286 		long long c = x * x;
    287 		int p = 2;
    288 		while (c <= n) {
    289 			string tmp = toString(x) + "^" + toString(p);
    290 			relax(c, tmp);
    291 			c *= x;
    292 			p++;
    293 		}
    294 	}
    295 }
    296 ```
    297 
    298 Now lets consider the expressions containing several multipliers. The same way (as for addition) in such representation at most one multiplier is a number. Including that the expression can contain at most 7 digits we have only 2 possible ways:
    299 
    300 1. `x = a^b*c^d`
    301 2. `x = a^b*c`
    302 
    303 where *a*, *b*, *c* and *d* are some numbers. Lets iterate through *i* — the length of the representation of the first multiplier and go over all values stored in *s*[*i*]. The second multiplier can have length at most *d* = 7 - *i* - 1 and the total number of ways to choose two multipliers will be small enough. The second multiplier should be selected from containers *s*[*j*] for length at most *d* (in the first case), or we should iterate from 1 to 10*d* (in the second case). After that we will have about *k* = 150000 numbers in *m* in total:
    304 
    305 ```
    306 void generatePowerAndPower(int maxlen) {
    307 	for (int i = 1; i <= maxlen; i++)
    308 		for (int j = i; i + j + 1 <= maxlen; j++)
    309 			for (auto x : s[i])
    310 				for (auto y : s[j])
    311 					relax(x * y, get(x) + "*" + get(y));
    312 }
    313 
    314 void generateSimpleAndPower(int maxlen) {
    315 	for (int i = 1; i + 2 <= maxlen; i++)
    316 		for (long long x = 1; x < p10[maxlen - 1 - i]; x++)
    317 			for (long long y : s[i])
    318 				relax(x * y, toString(x) + "*" + get(y));
    319 }
    320 
    321 void precalc() {
    322 	generatePowers();
    323 	generatePowerAndPower(7);
    324 	generateSimpleAndPower(7);
    325 }
    326 ```
    327 
    328 Now lets go back to the representation of the original number. For the first case — `a^b` — we have already stored such values in *m*. For the cases `x+y` and `x*y` we may assume that the length of expression of *x* is not greater than 4. Now lets iterate through *x* among found representations of length up to 4, and among integers from 1 to 104. For each such *x* and for each of 2 cases we determine value of *y* uniquely, and the optimal representation of *y* is already stored in *m* or it is just a number. So, for each such *x* we can find optimal answer for *n* by at most two addressing to *m* i.e. in *log*(*k*) operations.
    329 
    330 ```
    331 string ans;
    332 void relaxAns(string s) {
    333 	if (ans.length() > s.length())
    334 		ans = s;
    335 }
    336 
    337 void check2() {
    338 	for (int i = 1; i * 2 + 1 < ans.length(); i++) {
    339 		for (long long x = 1; x <= p10[i]; x++) {
    340 			relaxAns(get(n - x) + "+" + get(x));
    341 			if (n % x == 0)
    342 				relaxAns(get(n / x) + "*" + get(x));
    343 		}
    344 		for (auto x : s[i]) {
    345 			relaxAns(get(n - x) + "+" + get(x));
    346 			if (n % x == 0)
    347 				relaxAns(get(n / x) + "*" + get(x));
    348 		}
    349 	}
    350 }
    351 
    352 int main() {
    353 	... // read n, calculate powers of 10
    354 	precalc();
    355 	ans = get(n);
    356 	check2();
    357 	cout << ans;
    358 }
    359 ```
    360 
    361 Finally, the total algorithm complexity is *O*((*sqrt*(*n*) + *k* + 104) * *log*(*k*)).
    362 
    363 [Solution](https://pastebin.com/77nTfkWQ)