Разбор Codeforces Round #555 (Div. 3)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

Разбор

Решение

def f(x):
	x += 1
	while(x % 10 == 0):
		x //= 10
	return x

a = set()
n = int(input())

while(not(n in a)):
	a.add(n)
	n = f(n)

print(len(a))

1157B - Длинное число

Идея: BledDest

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

int f[10];
string s;

int main()
{
	int n;
	cin >> n;
	cin >> s;
	for(int i = 1; i <= 9; i++)
		cin >> f[i];
	vector<int> diff;
	for(int i = 0; i < n; i++)
		diff.push_back(f[s[i] - '0'] - (s[i] - '0'));
	for(int i = 0; i < n; i++)
		if(diff[i] > 0)
		{
			while(i < n && diff[i] >= 0)
			{
				s[i] = char(f[s[i] - '0'] + '0');
				i++;
			}
			break;
		}
	cout << s << endl;
}

1157C1 - Возрастающая подпоследовательность (упрощенная версия)

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	string res;
	int l = 0, r = n - 1;
	int lst = 0;
	while (l <= r) {
		vector<pair<int, char>> cur;
		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
		sort(cur.begin(), cur.end());
		if (int(cur.size()) == 2) {
			cur.pop_back();
		}
		if (int(cur.size()) == 1) {
			if (cur[0].second == 'L') {
				res += 'L';
				lst = a[l];
				++l;
			} else {
				res += 'R';
				lst = a[r];
				--r;
			}
		} else {
			break;
		}
	}
	
	cout << res.size() << endl << res << endl;
	
	return 0;
}

1157C2 - Возрастающая подпоследовательность (усложнённая версия)

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	string res;
	int l = 0, r = n - 1;
	int lst = 0;
	while (l <= r) {
		vector<pair<int, char>> cur;
		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
		sort(cur.begin(), cur.end());
		if (int(cur.size()) == 2 && cur[0].first != cur[1].first) {
			cur.pop_back();
		}
		if (int(cur.size()) == 1) {
			if (cur[0].second == 'L') {
				res += 'L';
				lst = a[l];
				++l;
			} else {
				res += 'R';
				lst = a[r];
				--r;
			}
		} else if (int(cur.size()) == 2) {
			int cl = 1, cr = 1;
			while (l + cl <= r && a[l + cl] > a[l + cl - 1]) ++cl;
			while (r - cr >= l && a[r - cr] > a[r - cr + 1]) ++cr;
			if (cl > cr) {
				res += string(cl, 'L');
			} else {
				res += string(cr, 'R');
			}
			break;
		} else {
			break;
		}
	}
	
	cout << res.size() << endl << res << endl;
	
	return 0;
}

1157D - N задач за K дней

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	if (n < k * 1ll * (k + 1) / 2) {
		cout << "NO" << endl;
		return 0;
	}
	
	int nn = n - k * (k + 1) / 2;
	vector<int> a(k);
	for (int i = 0; i < k; ++i) {
		a[i] = i + 1 + (nn / k) + (i >= k - nn % k);
	}
	
	if (nn != k - 1) {
		cout << "YES" << endl;
		for (int i = 0; i < k; ++i) cout << a[i] << " ";
		cout << endl;
	} else {
		if (k > 3) {
			--a[1];
			++a[k - 1];
		}
		if (k == 2 || k == 3) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
			for (int i = 0; i < k; ++i) cout << a[i] << " ";
			cout << endl;
		}
	}
	
	return 0;
}

1157E - Минимальный массив

Идея: vovuh

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	multiset<int> b;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		b.insert(x);
	}
	
	for (int i = 0; i < n; ++i) {
		auto it = b.lower_bound(n - a[i]);
		if (it == b.end()) it = b.begin();
		cout << (a[i] + *it) % n << " ";
		b.erase(it);
	}
	cout << endl;
	
	return 0;
}

1157F - Максимальный сбалансированный круг

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(200 * 1000 + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());
	
	int l = 0, r = 0;
	int ans = cnt[a[0]];
	for (int i = 0; i < int(a.size()); ++i) {
		int j = i + 1;
		int sum = cnt[a[i]];
		while (a[j] - a[j - 1] == 1 && cnt[a[j]] > 1) {
			sum += cnt[a[j]];
			++j;
		}
		int cr = j - 1;
		if (j < n && a[j] - a[j - 1] == 1) {
			sum += cnt[a[j]];
			cr = j;
		}
		if (ans < sum) {
			ans = sum;
			l = i;
			r = cr;
		}
		i = j - 1;
	}
	
	cout << ans << endl;
	for (int c = 0; c < cnt[a[l]]; ++c) cout << a[l] << " ";
	for (int i = l + 1; i < r; ++i) {
		for (int c = 0; c < cnt[a[i]] - 1; ++c) cout << a[i] << " ";
	}
	for (int c = 0; l != r && c < cnt[a[r]]; ++c) cout << a[r] << " ";
	for (int i = r - 1; i > l; --i) cout << a[i] << " ";
	cout << endl;
	
	return 0;
}

1157G - Обращение строк и столбцов

Идея: vovuh

Это комментарий по поводу квадратичного решения. Спасибо за упоминание этого факта, STommydx!

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int n, m;

void invRow(vector<vector<int>> &a, int idx) {
	for (int pos = 0; pos < m; ++pos) {
		a[idx][pos] ^= 1;
	}
}

void invCol(vector<vector<int>> &a, int idx) {
	for (int pos = 0; pos < n; ++pos) {
		a[pos][idx] ^= 1;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	
	for (int cnt0 = 0; cnt0 <= m; ++cnt0) {
		string r(n, '0');
		string c(m, '0');
		vector<vector<int>> b = a;
		for (int j = 0; j < m; ++j) {
			if ((j < cnt0 && b[0][j] == 1) || (j >= cnt0 && b[0][j] == 0)) {
				invCol(b, j);
				c[j] = '1';
			}
		}
		bool ok = true;
		if (cnt0 < m) {
			for (int i = 1; i < n; ++i) {
				int sum = accumulate(b[i].begin(), b[i].end(), 0);
				if (sum != 0 && sum != m) {
					ok = false;
				} else if (sum == 0) {
					invRow(b, i);
					r[i] = '1';
				}
			}
		} else {
			int idx = -1;
			for (int i = 1; i < n; ++i) {
				int sum = accumulate(b[i].begin(), b[i].end(), 0);
				if (sum != 0 && sum != m) {
					if (idx != -1) ok = false;
					else idx = i;
				}
			}
			if (idx == -1) {
				for (int i = 1; i < n; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == 0) {
						invRow(b, i);
						r[i] = '1';
					}
				}
			} else {
				for (int i = 1; i < idx; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == m) {
						invRow(b, i);
						r[i] = '1';
					}
				}
				if (b[idx][0] == 1) {
					invRow(b, idx);
					r[idx] = '1';
				}
				for (int j = 1; j < m; ++j) {
					if (b[idx][j] < b[idx][j - 1]) {
						ok = false;
					}
				}
				for (int i = idx + 1; i < n; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == 0) {
						invRow(b, i);
						r[i] = '1';
					}
				}
			}
		}
		if (ok) {
			cout << "YES" << endl << r << endl << c << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;
	
	return 0;
}

Комментарии (29)

Показать архивные | Написать комментарий?

Devil

6 лет назад, # |

The editorial for Problem G looks like a little the editorial of Problem F

→ Ответить

vovuh

6 лет назад, # ^ |

Thank you for mentioning, I just forgot to fix this place :)

It_Wasnt_Me

it was a greedy contest :D Good round by the way

sodafago

My solution problem D after contest(sad): 1)Find minimum first element with binary search 2) let's get maximum suffix, when we can add 1 for all numbers on segment, do it, while exist this is segment 3) end O(nLogn), and write easy

https://codeforces.me/contest/1157/submission/53393728

i_love_my_mom

В этот раз, однако, див3 был сложноватый

index_

ну разве что С2 была сложноватой для С

RNR

1157D — N Problems During K Days can be solved simply by putting $$$1,2,\dots,k$$$ initially and then trying to put $$$(n-(k*(k+1)/2))/k$$$ elements in each, and then from reverse order adding as many elements in each position as possible, without considering special cases separately.

You can go through my submission for clear understanding.

AmericanViper9022

Anyone help me in finding the cause of TLE in Problem D in my solution.

rotavirus

← Rev. 2 →

"erase" for vector works in linear time of size of the whole vector

vjvjain0

This problem also has a solution like D:

https://www.codechef.com/SNCK1B19/problems/MAXPRODU

prac64

Does anyone have a solution for problem E which does not involve STL structures, specifically without using multiset,set,map or multimap ?

islammohsen

You can use segment trees.

check this solution 53473452

sultan_01

5 лет назад, # ^ |

I did it using DSU 78261765 Incase if you need a explanation reply to this comment or DM me.

Naman_Bhalla

Problem D: "Then if nn != k — 1 or k = 1 then this answer is correct."

Any explanation for this ?

deque

For problem 1157c1, what if the input is

7 7 4 5 6 3 2 1

The solution code out puts 5 RRRRL But if I discard 7 and take the subsequence [4 5 6 3 2 1],it's possible to get a strictly increasing subsequence of size 6, right?

fengquyoumo

When is the next div3?

Mohit_Thorat

What's wrong with my solution for problem B? https://codeforces.me/contest/1157/submission/53566680 I am getting wrong answer on test case 7

heyBossCanIGetAnACPlease

Try for
5
43111
9 2 3 5 1 1 1 1 1
Answer should be : 53999, get it?

GaryZ005

I solved D in a different way. Mine

VLADO

I'm kind of late, but problem D can be easily (more or less) solved by binary searching the first element, and then binary searching every other element as well, from left to right, so that the minimum possible sum is <= n and the maximum possible sum is >= n. My submission

For the D problem, I just initialized array to 1,2,...,K then added (S — (K * (K + 1)) / 2) / N to every element in the array, and then just distributed (S — (K * (K + 1)) / 2) % N from the behind appropriately. Just wondering why there were so less submissions for this problem?

_Shubho_

How to solve problem Minimum Array using segment trees??

Rockett

← Rev. 5 →

I solved with segment tree, so I will try to explain my solution:

First we need to sort B array, to be able to find some index j for each $$$A_i$$$ such that $$$A_i + B_l \lt n$$$ for all $$$l \lt j$$$, and $$$A_i + B_r \ge n$$$ for all $$$r \ge j$$$. We'll have only one index j for each $$$A_i$$$, because $$$max(A) + max(B) < 2n$$$.

After that we can divide B array in two parts and find the best among these greedly, using segment tree here to get minimum, and then updating the used element to not be taken more than once.

Submission

AdnanShamsi

4 года назад, # |

can anyone tell me mathematical proof of E i just wanted to know why finding greater element is optimal than finding lesser value element if n-a[i] is not found

vdmedragon

4 года назад, # ^ |

It is because for any $$$k\geq n-a[i]$$$ and any $$$0\leq b < n-a[i]$$$, you will have $$$(a[i]+k) \mod n \leq a[i] + (n-1) \mod n < a[i] \leq a[i]+b < n$$$.

hsrb

3 года назад, # |

In problem E first I used a sorted vector to store the elements of array b and used lower_bound+erase operations to find the appropriate element for the current a[i]. But it gave TLE on test 16. But when I used multiset instead of vector it passed all the tests. Can anyone explain why vector solution gave TLE?

rahul_rax

3 года назад, # ^ |

This is because erase function in vector works in linear time(n), but in set or multiset, the data is already sorted so it works in constant time.o(1).

Got it. Thanks bro.

canonica1

23 месяца назад, # |

i think i have better solution for D. We can search maximum value of c that sum of array(c, c + 1, c + 2 .... c + k) <= n; then we can run through this array from the end and greedily add 1 while the problem condition is being met. since we have to add a maximum of k units, we will be able to do this.

Блог пользователя vovuh