This was our first time setting a Div.4 contest. We sincerely hope you enjoyed the problems!

##### 1985A - Создание слов

Problem Credits: cry

Analysis: cry

**Solution**

To swap the first character of the strings, you can use the built-in method std::swap in C++, or for each string, separate the first character from the rest of the string and concatenate it with the other string.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while(t--){
string a, b; cin >> a >> b;
swap(a[0], b[0]);
cout << a << " " << b << endl;
}
}
```

##### 1985B - Максимальная сумма кратных чисел

Problem Credits: cry

Analysis: cry

**Solution**

To maximize the number of multiples of $$$x$$$ less than $$$n$$$, it optimal to choose a small $$$x$$$, in this case, $$$2$$$. The only exception is $$$n = 3$$$, where it is optimal to choose $$$3$$$ instead, since both $$$2$$$ and $$$3$$$ have only one multiple less than $$$3$$$.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while(t--){
int n; cin >> n;
cout << (n == 3 ? 3 : 2) << endl;
}
}
```

##### 1985C - Хорошие префиксы

Problem Credits: sum

Analysis: cry

**Solution**

The only element that can be the sum of all other elements is the maximum element, since all elements are positive. Therefore, for each prefix $$$i$$$ from $$$1$$$ to $$$n$$$, check if $$$sum(a_1, a_2, ..., a_i) - max(a_1, a_2, ..., a_i) = max(a_1, a_2, ..., a_i)$$$. The sum and max of prefixes can be tracked with variables outside the loop.

**Code (C++)**

```
#include <iostream>
using namespace std;
int main(){
int t; cin >> t;
while(t--){
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++)
cin >> a[i];
long long sum = 0;
int mx = 0, ans = 0;;
for(int i = 0; i < n; i++){
sum += a[i];
mx = max(mx, a[i]);
if(sum - mx == mx)
ans++;
}
cout << ans << endl;
}
}
```

##### 1985D - Манхэттенский круг

Problem Credits: cry

Analysis: cry

**Solution**

Note that the manhattan circle is always in a diamond shape, symmetric from the center. Let's take notice of some special characteristics that can help us. One way is to find the top and bottom points of the circle. Note that these points will have columns at the center of the circle, so here we can acquire the value of $$$k$$$. To find $$$h$$$, since the circle is symmetric, it is just the middle of the rows of the top and bottom points.

Note that we never needed to find the value of $$$r$$$.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
int t; cin >> t;
while(t--){
int n, m; cin >> n >> m;
vector<vector<char>> g(n, vector<char>(m));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> g[i][j];
}
}
pair<int, int> top = {INF, INF}, bottom = {-INF, -INF};
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(g[i][j] == '#'){
top = min(top, {i, j});
bottom = max(bottom, {i, j});
}
}
}
assert(top.second == bottom.second);
cout << (top.first + bottom.first) / 2 + 1 << " " << top.second + 1 << endl;
}
}
```

##### 1985E - Секретный ящик

Problem Credits: cry

Analysis: cry

**Solution**

Since the side lengths of $$$S$$$ has to multiply to $$$k$$$, all three side lengths of $$$S$$$ has to be divisors of $$$k$$$. Let's denote the side lengths of $$$S$$$ along the $$$x$$$, $$$y$$$, and $$$z$$$ axes as $$$a$$$, $$$b$$$, and $$$c$$$ respectively. For $$$S$$$ to fit in $$$B$$$ , $$$a \leq x$$$, $$$b \leq y$$$, and $$$c \leq z$$$ must hold. Because of the low constraints, we can afford to loop through all possible values of $$$a$$$ and $$$b$$$, and deduce that $$$c=\frac{k}{a \cdot b}$$$ (make sure $$$c \leq z$$$ and $$$c$$$ is an integer). To get the amount of ways we can place $$$S$$$, we can just multiply the amount of shifting space along each axes, and that just comes down to $$$(x−a+1) \cdot (y−b+1) \cdot (z−c+1)$$$. The answer is the maximum among all possible values of $$$a$$$, $$$b$$$, and $$$c$$$ .

The time complexity is $$$\mathcal{O}(n^2)$$$ where $$$n$$$ is at most $$$2000$$$.

**Code (C++)**

```
#include <iostream>
using namespace std;
using ll = long long;
int main(){
int t; cin >> t;
while(t--){
ll x, y, z, k; cin >> x >> y >> z >> k;
ll ans = 0;
for(int a = 1; a <= x; a++){
for(int b = 1; b <= y; b++){
if(k % (a * b)) continue;
ll c = k / (a * b);
if(c > z) continue;
ll ways = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1);
ans = max(ans, ways);
}
}
cout << ans << "\n";
}
}
```

##### 1985F - Финальный босс

Problem Credits: cry, sum

Analysis: cry, sum

**About Hacks**

Unfortunately, there was a lot of hacks on this problem, and we're sorry for it. Since our intended solution is not binary search, we didn't really take overflow using binary search seriously. I (cry) prepared this problem and I only took into account about overflow with big cooldown, but I forgot overflow can happen on attacks as well. I apologize and we will do better next time!

**Solution**

Since the sum of $$$h$$$ is bounded by $$$2 \cdot 10^5$$$, and each attack deals at least $$$1$$$ damage. If we assume every turn we can make at least one attack, the sum of turns to kill the boss in every test case is bounded by $$$2 \cdot 10^5$$$. This means that we can afford to simulate each turn where we make at least one attack.

But what if we cannot make an attack on this turn? Since the cooldown for each attack can be big, we cannot increment turns one by one. We must jump to the next turn we can make an attack. This can be done by retrieving the first element of a sorted set, where the set stores pairs {$$$t$$$, $$$i$$$} which means {next available turn you can use this attack, index of this attack} for all $$$i$$$. Here, we can set the current turn to $$$t$$$ and use all attacks in the set with first element in the pair equal to $$$t$$$. Remember to insert the pair to {$$$c_i + t$$$, $$$i$$$} back into the set after processing the attacks.

The time complexity is $$$\mathcal{O}(h \log n)$$$.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while(t--){
int h, n; cin >> h >> n;
vector<int> a(n), c(n);
for(int& i: a) cin >> i;
for(int& i: c) cin >> i;
set<pair<long long, int>> S;
for(int i = 0; i < n; i++){
S.insert({1, i});
}
long long last_turn = 1;
while(h > 0){
auto [turn, i] = *S.begin();
S.erase(S.begin());
last_turn = turn;
h -= a[i];
S.insert({turn + c[i], i});
}
cout << last_turn << "\n";
}
}
// comment "tomato" if you see this comment
```

**Bonus**

Try to solve this if $$$1 \le h \le 10^9$$$.

**Solution**

We can do this by binary searching for the answer. For some time $$$t$$$, we know that we can perform an attack of cooldown $$$c$$$ exactly $$$\lfloor \frac{t - 1}{c} \rfloor + 1$$$ times. The total damage we will do in time $$$t$$$ will be:

So we binary search for the first $$$t$$$ such that the total damage we do in time $$$t$$$ is greater than or equal to $$$h$$$. This runs in $$$\mathcal{O(n \log {(h \cdot \max c_i)})}$$$. Be careful of long long overflow!

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll h, n;
cin >> h >> n;
vector<ll> A(n), C(n);
for (ll &i : A)
cin >> i;
for (ll &i : C)
cin >> i;
auto chk = [&](ll t){
ll dmg = 0;
for (int i = 0; i < n and dmg < h; i++){
ll cnt = (t - 1) / C[i] + 1;
if (cnt >= h)
return true;
dmg += cnt * A[i];
}
return dmg >= h;
};
ll L = 1, H = 1e12;
while (L < H){
ll M = (L + H) / 2;
chk(M) ? H = M : L = M + 1;
}
cout << L << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
```

##### 1985G - D-Функция

Problem Credits: cry

Analysis: cry

**Solution**

To satisfy $$$D(k \cdot n) = k \cdot D(n)$$$, each digit $$$d$$$ in $$$n$$$ must become $$$k \cdot d$$$ after multiplying $$$n$$$ by $$$k$$$. In other words, none of $$$n$$$'s digits can carry over to the next digit upon multiplication. From this, we can deduce that each digit in $$$n$$$ must be less than or equal to $$$\lfloor \frac{9}{k} \rfloor$$$. Only thing left is to count all such numbers in the range of $$$10^l$$$ inclusive and $$$10^r$$$ exclusive.

Every number below $$${10}^r$$$ has $$$r$$$ or less digits. For numbers with less than $$$r$$$ digits, let's pad the beginning with zeroes until it becomes a $$$r$$$ digit number (for example, if $$$r = 5$$$, then $$$69$$$ becomes $$$00069$$$). This allows us to consider numbers with less than $$$r$$$ digits the same way as numbers with exactly $$$r$$$ digits. For each digit, we have $$$\lfloor \frac{9}{k} \rfloor + 1$$$ choices (including zero), and there are $$$r$$$ digits, so the total number of numbers that satisfies the constraint below $$${10}^r$$$ is $$$(\lfloor \frac{9}{k} \rfloor + 1)^r$$$.

To get the count of numbers in range, it suffices to subtract all valid numbers less than $$$10^l$$$. Therefore, the answer is $$$(\lfloor \frac{9}{k} \rfloor + 1)^r - (\lfloor \frac{9}{k} \rfloor + 1)^l$$$. To exponentiate fast, we can use modular exponentiation.

**Code (Python)**

```
MOD = int(1e9+7)
t = int(input())
for _ in range(t):
l, r, k = map(int, input().split())
print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD)
```

##### 1985H1 - Максимизация наибольшей компоненты (простая версия)

Problem Credits: sum

Analysis: sum

**Solution**

Let's first solve the problem if we can only select and fill **rows**. Columns can be handled in the exact same way.

For each row $$$r$$$, we need to find the size of the component formed by filling row $$$r$$$ (i.e. the size of the component **containing** row $$$r$$$ if we set all cells in row $$$r$$$ to be $$$\texttt{#}$$$).

The size of the component **containing** row $$$r$$$ if we set all cells in row $$$r$$$ to be $$$\texttt{#}$$$ will be the **sum** of:

- The number of $$$\texttt{.}$$$ in row $$$r$$$ since these cells will be set to $$$\texttt{#}$$$. Let $$$F_r$$$ denote this value for some row $$$r$$$.
- The sum of sizes of components containing a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ (i.e. components that are touching row $$$r$$$). This is since these components will be part of the component containing row $$$r$$$. Let $$$R_r$$$ denote this value for some row $$$r$$$.

The challenge is computing the second term quickly. For some component, let $$$s$$$ be the size of the component and let $$$r_{min}$$$ and $$$r_{max}$$$ denote the minimum and maximum row of a cell in the component. This means that the component will contain cells with rows $$$r_{min},r_{min+1},...,r_{max}$$$. Note that we can find these values with a dfs. Since the component will contribute $$$s$$$ to rows in $$$[r_{min}-1,r_{min},\ldots r_{max}+1]$$$, we add $$$s$$$ to $$$R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$$$. This can be done naively or with prefix sums.

We find the maximum $$$F_r+R_r$$$ and then handle columns in the same way. This solution runs in $$$\mathcal{O}(nm)$$$ time.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC;
vector<vector<bool>> vis; vector<vector<char>> A;
void dfs(int i, int j){
if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
return;
vis[i][j] = true;
sz++;
minR = min(minR, i);
maxR = max(maxR, i);
minC = min(minC, j);
maxC = max(maxC, j);
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
}
void solve(){
cin >> n >> m;
R.assign(n + 5, 0);
C.assign(m + 5, 0);
freeR.assign(n + 5, 0);
freeC.assign(m + 5, 0);
vis.assign(n + 5, vector<bool>(m + 5, false));
A.assign(n + 5, vector<char>(m + 5, ' '));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> A[i][j];
if (A[i][j] == '.'){
freeR[i]++;
freeC[j]++;
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (vis[i][j] or A[i][j] == '.')
continue;
// Reset
sz = 0;
minR = 1e9;
maxR = -1e9;
minC = 1e9;
maxC = -1e9;
dfs(i, j);
// Expand by 1 since adjacent cells also connect
minR = max(minR - 1, 1);
maxR = min(maxR + 1, n);
minC = max(minC - 1, 1);
maxC = min(maxC + 1, m);
// Update prefix sums
R[minR] += sz;
R[maxR + 1] -= sz;
C[minC] += sz;
C[maxC + 1] -= sz;
}
}
ans = 0;
for (int i = 1; i <= n; i++){
R[i] += R[i - 1];
ans = max(ans, freeR[i] + R[i]);
}
for (int i = 1; i <= m; i++){
C[i] += C[i - 1];
ans = max(ans, freeC[i] + C[i]);
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
```

##### 1985H2 - Максимизация наибольшей компоненты (сложная версия)

Problem Credits: sum

Analysis: sum

**Solution**

For each row $$$r$$$ and column $$$c$$$, we need to find the size of the component formed by filling both row $$$r$$$ and column $$$c$$$ (i.e. the size of the component **containing** row $$$r$$$ and column $$$c$$$ if we set all cells in both row $$$r$$$ and column $$$c$$$ to be $$$\texttt{#}$$$).

Extending the reasoning in H1, for some row $$$r$$$ and column $$$c$$$, consider the sum of:

- The number of $$$\texttt{.}$$$ in row $$$r$$$ or column $$$c$$$ since these cells will be set to $$$\texttt{#}$$$. Let $$$F_{r,c}$$$ denote this value for some row $$$r$$$ and column $$$c$$$.
- The sum of sizes of components containing a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ (i.e. components that are touching row $$$r$$$). This is since these components will be part of the component containing row $$$r$$$ and column $$$c$$$. Let $$$R_r$$$ denote this value for some row $$$r$$$.
- The sum of sizes of components containing a cell in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$ (i.e. components that are touching column $$$c$$$). This is since these components will be part of the component containing row $$$r$$$ and column $$$c$$$. Let $$$C_c$$$ denote this value for some column $$$c$$$.

However, components that contain a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ as well as in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$ will be **overcounted** (since it will be counted in both terms $$$2$$$ and $$$3$$$) (you can think of it as components touching both row $$$r$$$ and column $$$c$$$). Thus, we need to subtract the sum of sizes of components that contain a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ as well as in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$. Let $$$B_{r,c}$$$ denote this for some row $$$r$$$ and column $$$c$$$.

Then the size of the component formed by filling both row $$$r$$$ and column $$$c$$$ will be $$$F_{r,c}+R_r+C_c-B_{r,c}$$$ and we want to find the maximum value of this.

Let's try to calculate these values efficiently. Consider some component.

- Let $$$s$$$ be its size.
- Let $$$r_{min}$$$ and $$$r_{max}$$$ denote the minimum and maximum row of a cell in the component. This means that the component contains cells with rows $$$r_{min},r_{min+1},...,r_{max}$$$.
- Let $$$c_{min}$$$ and $$$c_{max}$$$ denote the minimum and maximum column of a cell in the component. This means that the component contains cells with columns $$$c_{min},c_{min+1},...,c_{max}$$$.

All these values can be found with a dfs. We then do the following updates:

- Add $$$s$$$ to $$$R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$$$. This can be done naively or with prefix sums.
- Add $$$s$$$ to $$$C_{c_{min}-1},C_{c_{min}},\ldots,C_{c_{max}+1}$$$. This can be done naively or with prefix sums.
- Add $$$s$$$ to the subrectangle of $$$B$$$ with top left at ($$$r_{min}-1,c_{min}-1$$$) and bottom right at ($$$r_{max}+1,c_{max}+1$$$). This can be done with 2D prefix sums. (Note that doing this naively will pass because of low constant factor and the fact that we could not cut this solution without cutting slow correct solutions.)

We do this for each component. Also, calculating $$$F_{r,c}$$$ can be done by looking at the number of $$$\texttt{.}$$$ in row $$$r$$$, column $$$c$$$, and checking whether we overcounted a $$$\texttt{.}$$$ at ($$$r,c$$$). In all, this solution runs in $$$\mathcal{O}(nm)$$$ time.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC;
vector<vector<int>> RC; vector<vector<bool>> vis; vector<vector<char>> A;
void dfs(int i, int j){
if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
return;
vis[i][j] = true;
sz++;
minR = min(minR, i);
maxR = max(maxR, i);
minC = min(minC, j);
maxC = max(maxC, j);
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
}
void solve(){
cin >> n >> m;
R.assign(n + 5, 0);
C.assign(m + 5, 0);
freeR.assign(n + 5, 0);
freeC.assign(m + 5, 0);
RC.assign(n + 5, vector<int>(m + 5, 0));
vis.assign(n + 5, vector<bool>(m + 5, false));
A.assign(n + 5, vector<char>(m + 5, ' '));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> A[i][j];
if (A[i][j] == '.'){
freeR[i]++;
freeC[j]++;
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (vis[i][j] or A[i][j] == '.')
continue;
// Reset
sz = 0;
minR = 1e9;
maxR = -1e9;
minC = 1e9;
maxC = -1e9;
dfs(i, j);
// Expand by 1 since adjacent cells also connect
minR = max(minR - 1, 1);
maxR = min(maxR + 1, n);
minC = max(minC - 1, 1);
maxC = min(maxC + 1, m);
// Update prefix sums
R[minR] += sz;
R[maxR + 1] -= sz;
C[minC] += sz;
C[maxC + 1] -= sz;
RC[minR][minC] += sz;
RC[maxR + 1][minC] -= sz;
RC[minR][maxC + 1] -= sz;
RC[maxR + 1][maxC + 1] += sz;
}
}
for (int i = 1; i <= n; i++)
R[i] += R[i - 1];
for (int i = 1; i <= m; i++)
C[i] += C[i - 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
RC[i][j] += RC[i - 1][j] + RC[i][j - 1] - RC[i - 1][j - 1];
ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans = max(ans, (R[i] + C[j] - RC[i][j]) + (freeR[i] + freeC[j] - (A[i][j] == '.')));
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
```

tomato

tomato

tomato

tomato

tomato

tomato

tomatooooo

me too

tomato

`laal tamatar bade mazedar`

``ahaa tamatar bade mazedar``

tomato

tomato

tomato

tamatar bina chatni kaise bani.

tomato

tomatotomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomATO!?

tomato

Tomatotomato

tomato

tomato

tomato

even you are not able to crush that tomato.

tomato

what's mean? why so many "tomato"

i see now, abort F

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomato

tomatotomato

tomato

tomato

F : Boss Fight Detailed Video Tutorial Priority Queues and Maps

https://youtu.be/COkEV373zRo?feature=shared

got hacked on F :(

Me too :(

Me too too:(

Me too too too:(

me too too too two:)

me too too too too too:(

me too too too too too too

Me tooo

me too too too too too too too :(

me too, but got some consolation in reading that the author got "hacked" too. (" forgot overflow can happen on attacks as well")

Me too too too too too too too too :(

Tomato

Me too too too too too too too too too :(

tomato

tomato

plus

me too

Hopefully rating changes will come out soon!

hey i have given only two contest before will this be rated for me....

Yes!

my C's not gonna pass system testing :( and Thanks! for E,F,G , for E looping over sorted divisors of k is also an interesting solution ig

my binary search solution wasnt hacked because i checked for overflow :D way to go

+1 did the same

+0.9 for the same

how i didn't understand . how can i learn it

how to check overflow, please tell the constraints on left and right, and did you do l<=r or l < r, can you please explain

Thats not the overflow error. In binary search many including me put r as 1e12 ish.

The max value of attack will be — 1e5 * 1e5 * 1e12.(N, attack[i], mid) long long cant handle that. To solve it, at every iteration of n we have to check if the value is greater than health or not

Your comment literally says its because of overflow :D

He was asking about the constraints on binary search. L<r or l<=r won't lead to overflow. Maybe he meant it as 2 separate things.

oh sorry i misunderstood but yea whenever we multiply two very large integers its always recommended to check for whether its gonna overflow or not :D well you are definitely a specialist and way better than me so you know better ;D

Yea I actually forgot checking. Anyways rating doesn't matter when making mistakes and during discussions. Also I think you will reach pupil, Congo!

I have checked if monster health is between [2^r,2^(r+1) ) taking r from 0 ,1 ...so on to avoid overflow .

Youtube Link this video might help you.

Thank you

Thanks for the editorial. I learned a lot.

tomato

This was a good contest! Thank you

cryandsum!Was it a unrated contest??

No, after system testing ratings will be updated

Ok

When is the time of acceptance for a problem calculated? Is it at the time the problem is submitted and accepted, or at the time we see the acceptance?

Time will be calculated based on submission but the solution should be accepted

Sometimes, the verdict of our solution will be delayed because it will be in the queue. If your solution is accepted then the time of acceptance will be when you submitted it.

tomato! got hacked on F ;(

What is the difference between my binary search sol and those that got hacked? I wanna know more on why I got pass the hacking phase.

https://mirror.codeforces.com/contest/1985/submission/265355482

It's when someone uses a very high value for the upper limit of binary search (like 1e18). Then (turns/c[i])*a[i] could go very high, even above 64 bit long long. So to AC you could either use int128, or set a lower upper limit such as yours. Or use a lang like python :)

Oh, that's interesting! Thanks!

This rules out the test cases where all the attack values were $$${2 \cdot 10^5}$$$. So, the maximum sum of $$${a_i}$$$ should be less than $$${2 \cdot 10^5}$$$. The choice of r = $$${10^{11}}$$$ is judicious as $$${r \cdot \sum\limits_{k = 0}^na_k}$$$ fits in the range of

`LONG LONG INT`

.That makes more sense now :0

You're wrong, it's not because of the upper bound you take. I've also taken 1e11 as upper bound but got hacked. 265328896

If all attacks have damage 2e5 and cooldown is 1, sum can reach 2e5 x 2e5 x mid. if mid is >= 1e8, it overflows. Yours is correct because of the h -= a[i]. It prevents running binary search in such cases.

The correct way to deal with this is to use 128 bit integer or break out of the loop as soon as sum becomes >= h.

I will consider this as the official answer :v Thank you so much!

the value of r (or high) you have taken it to be 1e11 while i took 1e14 which caused overflow

265361398

Thank you, I got it!

tomato

Going to spend time

crying because the brute force approach did not come to mind for EAnyone who used DSU for H1,H2 explain your solution?

For H1 — You can use dsu to connect the components first and get the size of each component.Now for each row,check if . have any neighbor # which it can connect to,if it can then add that component size,finally add all . of this row to size aswell(as they will be converted to #).Do same for columns aswell and then finally return max value.

You can use dsu to join components of '#'. Notice that for any $$$(n * m)$$$ grid, we can represent $$$(i, j)$$$ as $$$(i*m + j)$$$. So initialize a disjoint set of $$$(n*m)$$$ components at first.

Then whenever you encounter a '#', you can run a flood fill via dfs / bfs and take $$$(i, j)$$$ = $$$(i*m + j)$$$ as the parent for all '#' you encounter.

Now you have size of all the connected components of '#'.

Now you can either '#' an entire row or column. I'm considering row here, same thing can be done for each column.

Notice when you '#' an entire row, You already have some '#' as parents, once you '#' the row, all these parents combine together.

One more thing, the parents from row above and row below will also be joined in this new component.

Hence the final answer would be $$$Count('.')$$$ + size of each parent you encounter.

To prevent taking a parent twice you can use the set.

Code:

SpoilerThanks, in a few hours ill study DSU then I'll sit and understand your solution soon. :D

I used the same approach but how will you extend this approach for H2 ?

neal did a very neat implementation using DSU.

Link: 265272303

i am using DSU but this code is giving TLE can you tell me why?

Your code have overflow because your arrays

`parent`

and`Size`

are too small when you want to iterate from 1, no 0 (but generally you want to have some reserve). Quick fix is setting`MAX_N=4e6`

,also you can change`i*m+j`

to i.e.`(i-1)*m+j-1`

. On the other hand, i suggest to cin whole string rather than char (this is faster)(but then you iterate from 0), and you have a lot of 'shadow declaration' — your

`i`

.I wonder why you don't have SF

thank for answer will try after contest. btw what is SF?

Segmentation fault, but like runtime error

I use DSU+DP to calculate four arrays: when the operation is at row=x, col=y, what's the total size we can get for the top-left/top-right/bot-left/bot-right w.r.t to (x, y).

I use set to track rather than unordered_set so the complexity is O(mnlog(n)): https://mirror.codeforces.com/contest/1985/submission/266763301

tomato

tomato

i need help in problem G :=> "D function" i am not able to understand the editorial so a simpler straight forward way would be really helpful

consider the digit to be xyz and when we multiply it by k individual digits will be multiplied by k so the new digit will be like (kx)(ky)(kz) to get what is asked in question we should notice that during multiplication if carry is genrated then our condition is never met . so (kx) should only lie between 0 and 9 , similarly other two.

thus for k>=10 ans is simply no. now let us take for k = 1 to 9 k = 1 --->> [0,9] k = 2 --->[0,4] because (2*5 = 10) thus we get num by 9/k + 1;

now consider this r_ _ _ l_ _ _ now from i = 0 to r ith digit can take num values but we need to eliminate those answers which are less than 10^l; so for i = 0 to l-1 ith can take all nums and for i = l to r-1 rest wil be 00; thus ans would be simply difference of both.

Ps: check my soln once for better understanding: 265443453

For problem F, if we take R as 1e12 it is being hacked

Consider 2e5 values equal 2e5 in array a, array c : 2e5 values equal 1 .. so, when multiplying (mid / c[i] * a[i]) 1e12 * 2e5 * 2e5 gives 1e22 which doesn't fit into 64bit :)

The editorial contains bonus problem solution which uses 1e12

I have used 1e13 lol, just break the loop as soon as sum becomes GTOE health. I mean if you're not breaking the loop, it will cause overflow .

My bad didn't see that return true part. Understood thanks

tomato :) btw a question. will the time complexity of priority queue solution be also $$$ O(hlogn) $$$ ?

tomato

Fast Editorial!

Tomato

this was my first contest on codeforces , managed to solve A and B , got TLE on C . should i register for upcoming div 2 contests or just wait for other div 3 or div 4 contest ? What should i do , suggestions ??

You should register for contest and try to solve a and b

but it feels like waste of time struggling with problems after A and B , should i prepare more first ? before contesting for div 2 contests

I think you should wait for DIV 3, because problem A div 2 +-= problem C div 4

you should register for div 2 and try to solve atleast a. from my first 5 contests, onlt 1 was div3, rest were div2s.

Ok , thankyou for your suggestion

You could do either, I personally waited till I hit expert atleast once before doing non-educational Div2.

this was my first contest, will this change my status from unrated to newbie?

tomato

tomato

what does it mean

check out code for problem F

ok got it

what does tomato mean?

The editorial solution for problem F has a comment in the code that says to comment "tomato" if you read that comment.

Is there anyone generous enough to debug my code?I tried to up-solve F. If I'm not wrong my solution takes O(

nlogn). Then why it's getting TLE on the second test case?Submission: 265448705

Edit: Solve it by replacing the vector(named coolingTime) with a map;

oh, yeah tomato

Tomato

I'm still eager to see a proof of why there are no such $$$n$$$ that satisfy $$$D(n \cdot k) = k \cdot D(n)$$$ in the case of possible carries in multiplication.

Same. I just guessed it

Yeah, guessed it is well, 'cause haven't managed to construct a formal proof of that fact in a reasonable amount of time during the contests. Wonder if such even exists. If yes, I am interested to see it too.

We can see that for a number with more than one digit, its $$$D$$$ will be smaller than itself(this is how number expression works!). For a number with exactly one digit, its $$$D$$$ is equal to itself.

Imagine we are multiplying a single digit $$$x$$$ by $$$k$$$, resulting in a carryover. We get a result $$$kx$$$ which has more than one digit. And we expect $$$D(kx)$$$ to be $$$kD(x)$$$, which is equal to $$$kx$$$ ($$$x=D(x)$$$). Thus, our $$$D$$$ has been smaller than the target. It’s impossible to compensate for this with another digit multiplication since $$$D(ky)$$$ won’t be greater than $$$ky$$$ for any $$$y$$$.

For each carry, D will be reduced by 9: the carry will add 1 to D instead of adding ten.

Yeah shitty editorial.

solved A B C D , first contest after so long , hoping to be 1000+ after the rating update.

I submitted the hacked solution for question F again and it got accepted then how is it possible that my solution got hacked, please help!! cry

test cases aren't yet updated!!

Ok

Problem G was ProjecteulerForces XD

tomato

![ ]()

In H1 why to subract R[maxR + 1] -= sz; and C[maxC + 1] -= sz; in solution.

Can anyone help explain why this equation is wrong only with large numbers in problem F using the binary search method?

The number of times we use the current attack is

`ceil(mid / (c[i] + 1))`

.(c[i] + 1) is the segment length in which we can perform only one attack.

Dividing gives us the number of segments we have, and any float will be ceiled. I don't understand why this is incorrect. Can anyone clarify?

It might overflow depending on your value of 'r'.

When will start System testing?

Is there a formal proof for B?

Let's consider any number greater than $$$n > 3$$$, then for $$$x=2$$$ we have $$$k = \lfloor n/2 \rfloor$$$ , hence $$$2 \cdot (1+2+ \dots k) = k \cdot (k+1)$$$, which is $$$n \cdot (n+2)/4$$$ for even $$$n$$$ and $$$(n^2-1)/4$$$ for odd $$$n$$$.

Consider any $$$x \ge 2$$$, then, $$$g(x) = \frac{(n+1) \cdot (n+1-x)}{2x} \le \frac{x \cdot k \cdot (k+1)}{2} \le \frac{n \cdot (n/x+1)}{2} = \frac{n \cdot (n+x)}{2x} = f(x)$$$. On evaluating, we get $$$f'(x) = \frac{-n^2}{2x^2}$$$ and $$$g'(x) = \frac{-(n+1)^2}{2x^2}$$$, hence a decreasing function. Thus, $$$f(x)$$$ or $$$g(x)$$$ should be maximum at $$$x=2$$$.

If the $$$f(x)$$$ and $$$g(x)$$$ logic is not convincing, you can think that $$$\lfloor n/x \rfloor$$$ will be always of the form $$$(n-\lambda)/x$$$ ,where $$$0 \le \lambda < x$$$ and it depends on $$$n$$$. [In fact, $$$\lambda = n \% x$$$] Thus the sum $$$h(x, \lambda) = \frac{(n - \lambda) \cdot (n- \lambda +x)}{2x}$$$, where $$$\lambda$$$ itself depends on $$$x$$$ and $$$n$$$. But, the for the extreme values of $$$\lambda$$$, the function $$$h(x)$$$ essentially takes the form $$$f(x)$$$ or $$$g(x)$$$, and it can be shown that it will work for any intermediate $$$\lambda$$$ as well.

PS: I am not sure why the above explanation doesn't work for $$$n=3$$$, could anyone point it out? Thanks!

Really intuitive and clear explanation, thanks a lot.

3(2) = 2

3(3) = 3 3>2

Yep I know that, but why is the proof failing? Cause the function is decreasing?

x(1+2+3+......+k) = k(x+kx)/2 — eq1 As x<=n and kx<=n => x+kx<=2n => (x+kx)/2<=n => eq1<=kn and if we consider n>=2 exept 3 we get the maximum value of eq1 when we have max k value thus k will be max for x = 2 as x>=2 given in problem and x = n/k thus for larges k we have to take smallest possible value of x thus 2 here and it will give the max answer for every n value. But for 3 we will have to take 3 as 2 < 3

got hacked F, ha.

cry for H2 on point 3. of the last paragraph, shouldn't it be subtract s on the subrectangle?

write proof for G, please

If I add two numbers and their digit carry over, then the digit sum of the new number will onviously decrease than the sum of the digit sum of the first two numbers. Same thing for k additions, if it is same after k additions, there should still be no carry. If there is no carry then each digit can be calculated for separately. More precicely each digit can range from 0 to 9/k. If a number is less than 10^l, then there are l digits to be filled so 9/k+1)^l. since we are asked in between, we can simply subtract the two values for r and l.

thanks)

Is it just me or the code for Problem E is wrong?

Having the same doubt...

my bad , it’s fixed now

For G, i solved this problem by Matrix Multiplication

SpoilerLet $$$cnt$$$ as the number less than or equal to $$$\frac{9}{k}$$$

We can determine the number of numbers that can be created by numbers less than or equal to $$$cnt$$$ with a length equal to a random $$$x$$$ is: $$$cnt$$$ $$$\cdot$$$ $$$(cnt + 1)^{x - 1}$$$

We define $$$F(k)$$$ = $$$cnt \cdot (cnt + 1)^k$$$ so the answer is $$$\sum\limits_{i = l + 1}^r(F(i))$$$ $$$module$$$ $$$1e9 + 7$$$ you can fast calculate this by the Matrix Multiplication

Here is the brute force solution: https://mirror.codeforces.com/contest/1985/submission/265340281

And here is my optimal solution: https://mirror.codeforces.com/contest/1985/submission/265348491

H2: We find some $$$O(n^3)$$$($$$O(nm\times \min(n,m))$$$) solutions like 265329368. Their solutions need to enumerate each cells in the smallest rectangle containing the connected blocks.

The data like

or

can let them have $$$O(n^3)$$$, but in fact they just need to run about $$$\frac{n^3}{12}$$$ times. We tried another construction, but it also failed. I think these solutions are wrong, hope the new construction can hack them.

Problem G was really good. Though I did not figure it out until I read the solution.

tomato

Tomato

I wonder why some participants solved the 'D' problem in a horrible way. Simply, push all the coordinates where the char is '#'. Then print the middle one.

Submission: 265290261

So how many testcases are there now in problem F?

236

crazy

tomato

how much time it takes for the ratings to be updated ???

after system testing gets completed.

What is system testing and how much time it takes??

refer this post contest FAQ's blog

Hm ok thanks sir

tomato

Meow

to be honest, i generated all n satisfy for all k from 2 to 11 and got the rules. got AC just by guessing the rules and i don't know how to prove the solution at all i was so regret that my solution for problem F got hacked because i forgot to check the overflow case

for this problem 1985E — Secret Box the code you provided gave 0 instead of 1030301 for the last test case. how come does it get accepted ? please answer. even my code was giving 0.that's why i didn't submit it yesterday.

Hi everyone,

I participated in this contest yesterday and I managed to solve 3 questions out of 9. Today when I look at the submissions, it says that I was only able to solve 2 out of 9. Can anyone tell me why is this happening?

Thanks.

System testing is going on. Wait until it reaches 100%.

Thanks, brother!!

tomato

tomatooooo

Wow, G solution was so easy... I almost came up with the idea that for each digit there are 9/k+1 digits, but I used 10/k+1, so couldn't figure out the answer(

Hey Guys, did anyone solve E. Secret Box in less than O(xy)?

Yes, it is solvable in O(k).

Here is the complete solution. Find all divisors of k and store them in a vector(let's call it div). The maximum size of this vector is sqrt(k) (let's call it size sz). Then you can brute force for x and y in this vector and calculate x = k/x/y. Now if these x,y,z satisfy given constraint then you got a valid dimension.

Overall complexity(O(sz*sz) where sz = sqrt(k)) => so O(k) Here is my O(n) submission: https://mirror.codeforces.com/contest/1985/submission/265647792

k <= 1e9?

Yes, it will still work because number of divisors for k <= 1e9 at max is 1344. So O(1344^2)

But O(root k) to find divisors actually takes more time then O(xy)

I used the same approach, and my runtime was more then that of O(xy)

https://mirror.codeforces.com/contest/1985/submission/265300819 Why my sol for C got TLE in testing?

Due to collision as u have used unordered map

Ok Thanks!

Same here

I too got a TLE.

But there shouldn't be any collision as I'm considering frequency.

Isn't it?

you can read the blog here about unordered_map (https://mirror.codeforces.com/blog/entry/50626)

Thanks bro

you can read the blog here about collision (https://mirror.codeforces.com/blog/entry/50626)

Thank u!

Tomato

Is there a solution about dsu roll back for H2, can you help me?

H1 can be solved using RollbackUnionFind

Submission: https://mirror.codeforces.com/contest/1985/submission/265404470

I also use rollback for h1, but i need it for H2. Do you have a solution?

I didn't even use rollback, simply doing it both directions works: https://mirror.codeforces.com/contest/1985/submission/265320343

The queuing time was too long. My solution for F got queued for 15mins, and gave wrong answer. I could have rectified it sooner :(

Hope codeforces fixes this :)

tomatoo

I have a friend who solved f using binary search and value of right 1e18 but it passes system tests.How?

share code

https://mirror.codeforces.com/contest/1985/submission/265374959

the guys is clever, i think it passes because he first performed the division then multiplication (in line 7 and 8), but i also got overflow because i multiplied both terms together and then divided, during multiplication of both then i might have got overflow.. any experts please reply after

in Line 5:

He used double to store the totalDamage,so there's no worry about overflow.

in Line 7:

the expression at right is at most 1e18 , also not overflow.

tomato

tomato

Its sad that being from India most of the cheaters and leaked solution are from my country although it does not affect my personal growth but it ruins the sportsmanship .. sad !!!

nothing sad, colleges focus on rubbish curriculum poor faculties, such high competetion for low paying jobs too.. then kuch to chahiye resume me bharne ke lie. not supporting cheating but most people start in their colleges , cp needs time and dedication blood sweat. but then students should have to do dev also, core also. seeing this they have nothing but to cheat and get rating tag (specialist/expert)..

just out of curiosity i am asking... in the E question is there any mathematical way to find the optimal sides of the smaller box directly(in constant time or even if in O(N) time) rather than using nested loop?

You can downgrade it from 3D to 2D, so if you can solve 2D version in constant time then you can solve 3D in linear time. In my opinion, the problem requires you to fix the shape first which I think may not be possible to have a solution faster than $$$O(min(min(x, y), \sqrt[]k))$$$.

tomato

265530894 This is my approach for problem F — Final Boss. I am fairly new to codeforces. I am not able to solve this error. Can anyone help why i am getting this diagnostics error?

Thanks

Diagnostics detected issues [cpp.clang++-c++20-diagnose]: p71.cpp:37:20: runtime error: signed integer overflow: 9195700509336791281 + 60645102003290034 cannot be represented in type 'long long' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:37:20 in

I am a C++ noob, but i think you need to use a bigger datatype for sum varriable.

Basically your sum variable is overflowing. try to figure out a way such that it doesn't overflow.

SpoilerCheck mid/c[i] every time before multiplying with a[i]. You can see my solution if needed.

265665651

still not working

Can you find out certain errors in my code?

I was able to solve it

Thanks

tomato

For problem E,

Can any one explain for $$$h \lt 10^9$$$, why the given time complexity holds true? Why in $$$log$$$ there is $$$h * max c_i$$$?

Thanks.

$$$h*maxc_i$$$ is one upper_bound of turns to kill the boss.

It's easy to prove. If you only use the attack that have max cooldown time of all attacks , assume that this attack only takes 1 damage , after $$$(h-1)*maxc_i+1$$$ turns the boss will die. This is the worst case, so you know that in $$$(h-1)*maxc_i+1$$$ turns the boss must die. For $$$(h-1)*maxc_i+1 < h*maxc_i$$$ ,in convinient we use $$$h*maxc_i$$$ for the upper_bound.

$$$log$$$ comes from binary_search approach.We use binary_search to find answer. You can find its time complexity proof on the Internet.

Got it 1xx55!

Thank you for the help! Appreciated.

G:(D-Function) Can someone explain, why do we add mod in this

`print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD)`

to the result of the difference?we know that

`pow(9 // k + 1, r, MOD)`

$$$\in [0,MOD-1]$$$ and`pow(9 // k + 1, l, MOD)`

$$$\in [0,MOD-1]$$$so it's possible that in some cases we have

`(pow(9 // k + 1, r, MOD) < pow(9 // k + 1, l, MOD)`

To avoid print a negative value , we add a MOD to the result.

Got it.

For problem G, how to prove the legal number n should be only that each digits of n multiple k have no influnance to the next digits.

using $$$D(x+y) = D(x) + D(y) - 9*carry$$$

To prove this formula , you can start with one digit , and it's correct. And you can expand this to all digits.

so we have $$$D(k*n) = k*D(n) - 9*carries$$$ .

What a prove！！！ Pretty good, thanks.

for problem H1 could someone tell me why my code get tle? Is there anything wrong with my dsu? code

there is a mistak in line 56, but it is still TLE after I correct it :(

tomato

Can someone explain why my submission 265271439 for problem C gives a TLE? It seems to be an O(n) approach. While I agree it's in Python, it would be helpful if someone pointed out what went wrong

From problem H2 what is wrong with the idea of taking maximum(first convert a row which gives maximum component size then convert a column which gives maximum component size, or reverse of previous).

I already implemented it and it fails at 5th sample case but I am not able to figure out why. I doubt its implementation mistake.

Does anyone get stack overflow in test 5 in Problem H2 in Java while implementing recursive dfs? In C++, it seems to be working (the author's solution uses recursive dfs). Any reason for this? Submission: 265565304

For problem F,

Can anyone help me to understand how $$$\lfloor{\frac{t - 1}{c}}\rfloor$$$ is derived?

Also, please let me know if it is a standard or generic way to calculate in such situations.

Thank you in advance.

This is a typical data structure problem. Here is my solution: https://mirror.codeforces.com/contest/1985/submission/265355672

Great explanation jay_1410!

Thank you so much! Appreciated!

TOMATO!!

For

H1I am using a map of pairs calledcompNumwhich basically marks each '**#**' with its component number. I have taken key pairs because I need to store coordinate of '**#**' and the value of this map is component number. And at the same time using anotherunordered map<int,int>cntI am counting the size of the current component number and using a visited matrix I am keeping track of whether the neighboring '**#**' is visited or not, standarddfsstuff. Then for each row I am placing '**#**' and counting answers as follows: FOr each rowri, if the cell contains '**#**' then using a map I am checking whether the component to which this cell belong to has already taken or not. ThecompNummap gives the component of this cell. And if it is not '**#**' then I increment the current answer by 1 because I place a new '**#**' in place of '**.**' and now I check four neighbors if any neighbor is '**#**' and its component is not taken then I add the size of the component to my current answer and proceed. Finally when I am done computing the value of the current answer for a row then I try to maximize my final ans with the current answer same stuff I do for columns. But I don't know why it is giving TLE. Any help will be appreciated. Thank you for spending time in understanding my approach.tomato

265582011 H1: I have used DSU for solving H1. It works for testcase1 but gives wrong answer for testcase2. could someone pls lemme know where I wen't wrong. I have been printing and debugging the last 6 hours. thx!

For H1 problem I have solved the problem but getting TLE on testcase 2. Any idea why it is giving TLE ? According to me the complexity is somewhat O(mn log(mn) ). Please correct me if I am wrong in assuming the complexity

## include <bits/stdc++.h>

using namespace std;

const int buf_size = 1e6+9;

bool vis[buf_size]; char grid[buf_size]; int grid_comp[buf_size]; int n,m;

void dfs(int i, int j, int comp) { // cout<<"dfs at index "<<i<<" "<<j<<"\n"; if(i<0 || j<0 || i>=n || j>=m) return;

}

int main() { // your code goes here int t; cin>>t; while(t--) {

}

good round, thx, i got green

tomato

tomato

I used binary search on F and got hacked since I defined r = 1e18. Then I changed to 1e13 and it worked, but I don't know exactly why it's working, since if all turns are 1 and a[i] = n (for n = 2*10^5), the possible maximum would be n * n * 1e13 (divided by 2), which it would be approximately 1e23 which doesn't fit on long long int, can anyone help?

You might be using a break statement while checking the binary search condition. If you use r = $$${10^{13}}$$$, $$${a_{i}}$$$ = $$${2 \cdot {10^{5}}}$$$ and $$${c_{i}}$$$ = $$${1}$$$. So as soon as the value is

`>= h`

you break out of the loop, and the value for the first iteration is $$${r \cdot a_{i}}$$$ which is around $$${10^{18}}$$$ that fits in the range of LONG LONG INT and you are able to successfully break out of the loop. Meanwhile if you use r = $$${10 ^{18}}$$$ then the value is around $$${10 ^{23}}$$$ for first iteration itself and it overflows before the break statement can come into action.I didn't use break on the for of the binary search, from what I calculated, this shouldn't be accepted, but I could be wrong https://mirror.codeforces.com/contest/1985/submission/265654152

Because of this initial pruning, you are able to ward off cases where all $$${a_i}$$$ are $$${2 \cdot {10 ^{5}}}$$$. So, $$${\sum\limits_{i = 0}^na_i < 2 \cdot {10 ^{5}}}$$$, is needed to go to binary search condition. You can easily check $$${r \cdot \sum\limits_{i = 0}^na_i}$$$ will not cause overflow for r = $$${10 ^ {13}}$$$ but for r = $$${10 ^ {14}}$$$ it will overflow.265655706

Ohh that's true, I didn't even notice it when I did it. r = 1e14 overflows because it might reach 1e19. Thanks a lot!! I will pay more attention now with overflow when doing binary search

i've posted my solution, please checkout the comment section... .you will get it

I tried solving H1. Why am I getting TLE on test case 3 ?? My solution is pretty much same as tutorial.

Someone Please check TIA!

Here is my code - 265512050

this is my BS solution for the "F"

tomato

how does max function works for pairs in c++ pair <int,int> a = {1,2} ; pair<int,int> b = {2,1}; max(a,b) ; ?

it will compare according to first... is first is same then according to second

Ok , thanks for the info

Can someone tell me whats wrong with this submission 265677247

How to prove the conclusion of question B?