Идея: vovuh
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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 - Два массива и сумма функций
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#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 - Микротранзакции (упрощенная версия)
Идея: BledDest
Разбор
Tutorial is loading...
Решение
#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 - Микротранзакции (усложненная версия)
Идея: BledDest
Разбор
Tutorial is loading...
Решение
#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;
}
Still can't understand problem E. Why we take in reverse order array b ?
I was hoping that editorial will give a proof for greedy strategy in problem C. :(
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.
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?
Is there any way to prove why a greedy solution works in problem C?
https://mirror.codeforces.com/blog/entry/67041?#comment-511546
Здравствуйте, не могли бы вы мне объяснить откуда взялась формула i*(n-i+1) ? Если не трудно, можно вывести?
Задача E
Это количество отрезков, покрывающих $$$i$$$-й элемент. Оно берется из того, что возможных левых границ у нас $$$i$$$ ($$$1, 2, \dots, i$$$), а правых границ — $$$n - i + 1$$$ ($$$i, i + 1, \dots, n$$$). Так как способы выбрать эти границы независимы, то мы можем перемножить эти величины, чтобы получить количество отрезков.
In Problem E, how do we derive the formula for the number of times $$$a_i*b_i$$$ will appear in the final answer?
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.
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.
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.
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?
you need to have enough money
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 :'( ?
your answer = https://mirror.codeforces.com/blog/entry/67041?#comment-512045
Problem D(w.r.t. tutorial): why is it necessary to check that x is the correct answer?
Getting TLE on test case 10 in problem E ... My solution is in JAVA ... Anybody please help me out
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
In problem E, why are we taking the extra term i*(n-i-1)?
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).
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?
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.
I explained problem E in detail in my Youtube video, enjoy. https://www.youtube.com/watch?v=ThjkHw6vxv8
for d why can't the answer be the lcm of given divisors??
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.
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)?
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
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 thed[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, because401*401 is not equal to 2*62155. So the result is -1