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

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

Идея: 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, x, y;
	string s;
	cin >> n >> x >> y >> s;
	
	int ans = 0;
	for (int i = n - x; i < n; ++i) {
		if (i == n - y - 1) ans += s[i] != '1';
		else ans += s[i] != '0';
	}
	
	cout << ans << endl;
	
	return 0;
}

1165B - Polycarp Training

Идея: 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];
	}
	sort(a.begin(), a.end());
	
	int pos = 1;
	for (int i = 0; i < n; ++i) {
		if (a[i] >= pos) ++pos;
	}
	
	cout << pos - 1 << endl;
	
	return 0;
}

1165C - Good String

Идея: BledDest

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

string s;
int n;
string res;

int main()
{
	cin >> n >> s;
	for(int i = 0; i < n; i++)
	{
		if(res.size() % 2 == 0 || res.back() != s[i])
			res.push_back(s[i]);
	}
	if(res.size() % 2 == 1) res.pop_back();
	cout << n - int(res.size()) << endl << res << endl;
	return 0;
}

1165D - Almost All Divisors

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {

		int n;
		cin >> n;
		vector<long long> d(n);
		for (int i = 0; i < n; ++i) {
			cin >> d[i];
		}
		sort(d.begin(), d.end());
		long long x = d[0] * d[n - 1];
		
		vector<long long> dd;
		for (int i = 2; i * 1ll * i <= x; ++i) {
			if (x % i == 0) {
				dd.push_back(i);
				if (i != x / i) {
					dd.push_back(x / i);
				}
			}
		}
		sort(dd.begin(), dd.end());
		
		if (dd == d) {
			cout << x << endl;
		} else {
			cout << -1 << endl;
		}
	}
	
	return 0;
}

1165E - Two Arrays and Sum of Functions

Идея: vovuh

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	
	sort(b.begin(), b.end());
	vector<pair<long long, int>> val(n);
	for (int i = 0; i < n; ++i) {
		val[i].first = (i + 1) * 1ll * (n - i) * a[i];
		val[i].second = i;
	}
	sort(val.rbegin(), val.rend());
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = (ans + (val[i].first % MOD * 1ll * b[i]) % MOD) % MOD;
	}
	cout << ans << endl;
	
	return 0;
}

1165F1 - Microtransactions (easy version)

Идея: BledDest

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> k;
vector<pair<int, int>> q(1001);

bool can(int day) {
	vector<int> lst(n, -1);
	for (int i = 0; i < m; ++i) {
		if (q[i].first <= day) {
			lst[q[i].second] = max(lst[q[i].second], q[i].first);
		}
	}
	vector<vector<int>> off(1001);
	for (int i = 0; i < n; ++i) {
		if (lst[i] != -1) {
			off[lst[i]].push_back(i);
		}
	}
	vector<int> need = k;
	int cur_money = 0;
	for (int i = 0; i <= day; ++i) {
		++cur_money;
		if (i > 1000) continue;
		for (auto it : off[i]) {
			if (cur_money >= need[it]) {
				cur_money -= need[it];
				need[it] = 0;
			} else {
				need[it] -= cur_money;
				cur_money = 0;
				break;
			}
		}
	}
	return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	k = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> k[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> q[i].first >> q[i].second;
		--q[i].first;
		--q[i].second;
	}
	
	for (int l = 0; l <= 2000; ++l) {
		if (can(l)) {
			cout << l + 1 << endl;
			return 0;
		}
	}
	
	assert(false);
	
	return 0;
}

1165F2 - Microtransactions (hard version)

Идея: BledDest

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> k;
vector<pair<int, int>> q(200001);

bool can(int day) {
	vector<int> lst(n, -1);
	for (int i = 0; i < m; ++i) {
		if (q[i].first <= day) {
			lst[q[i].second] = max(lst[q[i].second], q[i].first);
		}
	}
	vector<vector<int>> off(200001);
	for (int i = 0; i < n; ++i) {
		if (lst[i] != -1) {
			off[lst[i]].push_back(i);
		}
	}
	vector<int> need = k;
	int cur_money = 0;
	for (int i = 0; i <= day; ++i) {
		++cur_money;
		if (i > 200000) continue;
		for (auto it : off[i]) {
			if (cur_money >= need[it]) {
				cur_money -= need[it];
				need[it] = 0;
			} else {
				need[it] -= cur_money;
				cur_money = 0;
				break;
			}
		}
	}
	return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	k = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> k[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> q[i].first >> q[i].second;
		--q[i].first;
		--q[i].second;
	}
	
	int l = 0, r = 400000;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (can(mid)) r = mid;
		else l = mid;
	}
	
	for (int i = l; i <= r; ++i) {
		if (can(i)) {
			cout << i + 1 << endl;
			return 0;
		}
	}
	
	assert(false);
	
	return 0;
}

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

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

rupav

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

-6

Still can't understand problem E. Why we take in reverse order array b ?

→ Ответить

burt_macklin_

I was hoping that editorial will give a proof for greedy strategy in problem C. :(

kkbb

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

But it's trivial

I don't know. The one I know is very very complex and I am not even sure if it is correct. Could you please tell yours?

Consider the left-most pair that violates the condition. To fix this, we either remove one character from the pair, or one character to the left of the pair. Notice that whichever we do, the effect on the characters to the right of the pair is the same. So, we can always just remove one character from the pair.

Kya_Hi_Farak_Padhta_Hai

Hello can you please tell that in E question if first i were to multiply min a[i] with its corresponding max b[i] and then apply modulo function how would i do it? Like i want to do first: c[i] = a[i] * b[i] and then c[i]*(n-i)*(i+1) . What is the correct approach of doing modulo?

_orcus

Is there any way to prove why a greedy solution works in problem C?

https://codeforces.com/blog/entry/67041?#comment-511546

dr_matjo

Здравствуйте, не могли бы вы мне объяснить откуда взялась формула i*(n-i+1) ? Если не трудно, можно вывести?

Задача E

vovuh

Это количество отрезков, покрывающих $$$i$$$-й элемент. Оно берется из того, что возможных левых границ у нас $$$i$$$ ($$$1, 2, \dots, i$$$), а правых границ — $$$n - i + 1$$$ ($$$i, i + 1, \dots, n$$$). Так как способы выбрать эти границы независимы, то мы можем перемножить эти величины, чтобы получить количество отрезков.

irlbeck2

In Problem E, how do we derive the formula for the number of times $$$a_i*b_i$$$ will appear in the final answer?

__v0id

← Rev. 3 →

This is the number of l and r such that a_i and b_i are going to contribute to f(l, r). There are i possible left borders (1,2,...,i),and n-i+1 right borders (i,i+1,...,n). We can choose those borders independently, so the number of ways of doing this is i*(n-i+1) according to the product rule.

vrooooom

I have a question on F1. So far what I understand is that you buy the microtransactions on the last day of their sales, unless you can buy out all of the items on the current day. However I am confused since the last day of the sale might be far away, and it would be more optimal to use the current sale.

For instance, if you have only have 1 item, and 7 microtransactions for it, with sales on day 5 and 10, this algorithm will not do anything until day 10, where it will buy all of the microtransactions that it needs to, and finish off on day 10.

However, you could just spend 5 bourles on day 5, and then buy two transactions on day 9, to finish off the purchases on day 9, which occurs before day 10.

Obviously either my understanding of the problem or tutorial is flawed and I would greatly appreciate it if someone could explain my mistake to me.

sankalp_

Binary search succeeds for day = 10, so we search over the range 1 to 9 and finally arrive at 9 to be the minimum day I think.

Pj18

In F the question doesn't ask us to keep the money spent minimum, so why don't we buy all type on the first day?

verymuch4470

you need to have enough money

FITHOUk17

← Rev. 2 →

In problem E, I still don't understand why the value (ai * bi) occur i * (n — i + 1) times in the answer!

Can someone explain it to me :'( ?

iabhishek15

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

your answer = https://codeforces.com/blog/entry/67041?#comment-512045

Sam_Jn

Problem D(w.r.t. tutorial): why is it necessary to check that x is the correct answer?

sky_full_of_stars

11 месяцев назад, # ^ |

It's necessary because if x is the correct answer, then almost all divisors of x should be listed.

Example : For [2,10] , x = 20. But this value of x is not valid, because almost all divisors of x is [2,4,5,10] != [2,10]

eng_hardik

Getting TLE on test case 10 in problem E ... My solution is in JAVA ... Anybody please help me out

suhail25

It's bec of the Arrays.sort (dual pivot quicksort algorithm which has n^2 in worst case scenario), so must use mergesort or collection library. It happened with me too :( here you can see.

Thanks

ZxCv

In problem E, why are we taking the extra term i*(n-i-1)?

_trojan_horse

Because it is a double summation.When you'll simplify it,you'll get that term.

Think like: The no. of sequences(l,r) of which (ai*bi) is a part .

'l' can be chosen in 'i' no. of ways whereas 'r' can be chosen in 'n-i+1' no. of ways (all possible combinations are valid).So each term will have contribution i*(n-i+1).

2022OVO

I still don't understand why the solution of D use vector<pair<long long, int>> val(n).What's the use of val[i].second here?

pr3pony

F can be solved in $$$O(n + m \log m)$$$ using BST or segment tree 54494060 . The time complexity is independent of the range of $$$d_j, k_i, sum(k)$$$ if they can be stored in 64 bits integers.

I came up with the solution because I didn't see the sentence "sum of all $$$k_i$$$ is not less than $$$1$$$ and not greater than $$$2\cdot10^5$$$" at first.

Errichto

I explained problem E in detail in my Youtube video, enjoy. https://www.youtube.com/watch?v=ThjkHw6vxv8

aman_naughty

for d why can't the answer be the lcm of given divisors??

MinhNguyen546

20 месяцев назад, # ^ |

Of course we can. But there is a special case when X = p * p, then divisors array = {p}, in this case just take lcm = p^2.

kaneki_007

Can anyone help me with problem e bcoz i am not understanding after the first summation of a[i]*b[i] i.e. summation(f(l,r))? how did we get val[i]=a[i]*i*(n-1-i)?

aad3shk

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

Hello, i have a question for Problem D: In test case #6: 13 802 5 401 4010 62 2 12431 62155 310 10 31 2005 24862 the expected answer is : -1, when the correct answer should be 124310, could someone explain what am i missing ? Thanks

Imperial_Lord

The answer -1 is correct. If the value for n is odd, it means that the number can be represented as d[n/2]*d[n/2], where d is its divisors array. Thus we need to add the d[n/2] element again in the array, and then sort it. In this case, the added element will be 401, which can't be true, because 401*401 is not equal to 2*62155. So the result is -1

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