Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#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;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#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;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution**

```
#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;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#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

Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#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)

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution**

```
#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)

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution**

```
#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 ?

if we have two sorted sequence of numbers, let's say, $$$a_n$$$ and $$$b_n$$$ ($$$a_1 \leq a_2 \leq a_3 \leq ... \leq a_n$$$ and $$$ b_1 \leq b_2 \leq b_3 \leq ... \leq b_n $$$) then the minimum sum of their multiplication ($$$a_i * b_j$$$) is $$$ a_1*b_n + a_2*b_{n-1} + ... + a_n*b_1 $$$ (you take the largest value of $$$a_n$$$ and pair it with the lowest value of $$$b_n$$$ and vice versa) this is known as the rearrangement inequality. https://en.wikipedia.org/wiki/Rearrangement_inequality

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?

I can't understand problem C.Can any one explain this problem !

We have a string (lets name it s) which length is n. If we have any pair such that j = i + 1 and s[j] = s[i] and j is even ( j mod2 = 0), then delete these two letters from the s. And now we have a new string s. I hope yout got it

Thank u brother

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

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

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.

Thank u,I understand.

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.

54222326. Can't Understand, what is the problem in my solution in B?

If the Input is 1 5 5 then answer should be actually 3. But i think your sol'n will give 2 as answer.

Right! Thank you...

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 :'( ?

I got "Time limit exceeded on Test case 5" in the Remainder question. Can anybody some explanation.

Bro if u are using this step:"string h=h+s[i]" to push back a char s[i] in some string h then dont do it as it is inefficient try doing this as h.push_back(s[i]); I had this problem too though its punishment seems a bit too harsh

Holy cow. It does work. Thanks!!

for problem C i am following a 2 pointer approach.In beginning both pointer points to element 0 r=0 l=0 next if s[r]!=s[l] i add this mair to empty string h else r++

This is my code it times out for 5 th testcase since i am increasing" r "in every step it must be a O(n) solution and editorial too is O(n) dont know why it times out. `#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; string s; cin>>s; int l=0; int r=0; string h=""; while(r<n){ if(s[r]!=s[l]){ h=h+s[l]; h=h+s[r]; l=r+1;

} cout<<s.length()-h.length()<<endl; cout<<h<<endl;

} `

EDIT: Got it using "h=h+s[l]" this step is inefficient to do we should try doing this as h.push_back(s[l]); which is more efficient

looking at this editorial i am feeling like i could have easily done problem B,C,D but i don't know why i wasn't able to do them while the contest was running : (

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

Because you might have a case where you constructed the possible answer x from minimum and maximum but when you factorize the x you have some different values than the given array.

Eg-

A=[2,3,4,6,8]You will say

x=16but3will never be a factor of16. So we can't form an answer from that.could anyone explain F about its second example? why it is not 21? 21 = 3(on sale) + 2 * 9(not on sale)

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

Problems were wonderful .But problem A as first problem of div3 doesn't go . Problem D , There no need to be sorted only take minimum and maximum element by an array . My solution

https://github.com/joy-mollick/Codeforces-B-C-D-Problem-Solutions/blob/master/D%20-%20Almost%20All%20Divisors.cpp

In problem E val[i] should be a[i]*i*(n-i+1) but why is it multiplied by (i+1)*(n-i)?

You're approach would've been okay if the whole array was considered everytime. But that is not the case here. The problem statement wasn't able to make it clear but what we have to do here is, we have to minimize the sums of all the subarrays of the array. For this problem, you don't require to figure out how many subarrays the array will have. An array [1, 4, 3] has 6 subarrays. [1], [1,4], [1,4,3], [4], [4,3], [3]. For this problem we have to calculate how many times a particular index will be in a particular subarray. Take the array above for example. Here the element 4 occurs in a total of 4 subarrays. The element 3 in 3 subarrays and the element 1 in 3 subarrays. This is calculated using the formula [i * (n — i +1)] The approach here is very simple. Take one thing in mind here, we only have to change the order of the second array. The first array will be the same. And each element in the first array will occur [i * (n — i +1)] times. So first you multiply each element in the first array with [i * (n — i +1)]. Put these in a separate array and sort that in Ascending order. Then sort the second array in descending order. Now if you multiply each element of the two sorted arrays the final value will be minimum. Don't forget to mod the answer each time.

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?

Problem D solution, if i change the for iteration

for (int i = 2; i*1ll*i <= x; ++i){~~~}

for (int i = 2; i*i <= x; ++i){~~~}

erase "1ll" makes TLE in TC2 why does it happens? I think just overflow the range of expression in (int-long) does not make execution time longer, makes wrong answer but this in this case, makes TLE

Because you declared i as int and i*i can lead to overflow that gives negative result for (i*i) then it would never be greater than x. (i*i <= x) loop runs always that is why you have to put 1LL*i*i it will convert into long long Hope you get it.

oh!! i understand it thank you!

Regarding Problem C My code gives TLE . I've seen the editorial but I can't seem to find the problem in my code which leads to TLE. Here is the link to the code : https://ideone.com/fY10V4

Hey!! I checked your solution for quite some time and it looks O(n) . Even I am not sure where you're going wrong.

Can anyone please tell me where I'm going wrong for the problem F1?

https://codeforces.com/contest/1165/submission/54405888

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.

in problem d why set is causing problem?? can anyone check my code??

## define ll long long

int main() { ios_base :: sync_with_stdio (false); cin.tie (NULL); ll q; cin>>q; while(q--) { ll n; cin>>n; ll arr[n]; ll mn=INT_MAX; ll mx=INT_MIN; set se; for(int i=0;i<n;i++) { cin>>arr[i]; se.insert(arr[i]); mn=min(mn,arr[i]); mx=max(mx,arr[i]); } se.insert(1); ll fact=mn*mx; se.insert(fact); int pos=1; for(int i=1;i<=sqrt(fact);i++) { if(fact%i==0) { if(se.find(i)==se.end()) { pos=0; break; } if(se.find(fact/i)==se.end()) { pos=0; break; } }

}

https://codeforces.com/contest/1165/submission/54498967