Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
for i in range(int(input())):
x, y, k = map(int, input().split())
print(((y + 1) * k - 1 + x - 2) // (x - 1) + k)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n), c;
forn(i, n) cin >> a[i];
forn(i, n) cin >> b[i];
forn(i, n) if (!b[i])
c.push_back(a[i]);
sort(c.rbegin(), c.rend());
int j = 0;
forn(i, n) {
if (b[i]) cout << a[i] << ' ';
else cout << c[j++] << ' ';
}
cout << '\n';
}
int main() {
int T;
cin >> T;
while (T--) solve();
}
```

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
#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;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
int ans = 0;
ans += a[0] == 1;
for (int i = 1; i < n; ++i) {
if (a[i] == 0) {
continue;
}
int j = i;
while (j < n && a[j] == 1) {
++j;
}
ans += (j - i) / 3;
i = j - 1;
}
cout << ans << endl;
}
return 0;
}
```

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
int get(const set<int> &x, const multiset<int> &len) {
if (len.empty()) return 0;
return *x.rbegin() - *x.begin() - *len.rbegin();
}
void add(int p, set<int> &x, multiset<int> &len) {
x.insert(p);
auto it = x.find(p);
int prv = -1, nxt = -1;
if (it != x.begin()) {
--it;
len.insert(p - *it);
prv = *it;
++it;
}
++it;
if (it != x.end()) {
len.insert(*it - p);
nxt = *it;
}
if (prv != -1 && nxt != -1) {
len.erase(len.find(nxt - prv));
}
}
void rem(int p, set<int> &x, multiset<int> &len) {
auto it = x.find(p);
int prv = -1, nxt = -1;
if (it != x.begin()) {
--it;
len.erase(len.find(p - *it));
prv = *it;
++it;
}
++it;
if (it != x.end()) {
len.erase(len.find(*it - p));
nxt = *it;
}
x.erase(p);
if (prv != -1 && nxt != -1) {
len.insert(nxt - prv);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, q;
cin >> n >> q;
set<int> x;
multiset<int> len;
for (int i = 0; i < n; ++i) {
int p;
cin >> p;
add(p, x, len);
}
cout << get(x, len) << endl;
for (int i = 0; i < q; ++i) {
int t, p;
cin >> t >> p;
if (t == 0) {
rem(p, x, len);
} else {
add(p, x, len);
}
cout << get(x, len) << endl;
}
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 9;
const int MOD = 998244353;
int mul(int a, int b) {
return (a * 1LL * b) % MOD;
}
int bp(int a, int n) {
int res = 1;
for (; n > 0; n /= 2) {
if (n & 1) res = mul(res, a);
a = mul(a, a);
}
return res;
}
int inv(int a) {
int ia = bp(a, MOD - 2);
assert(mul(a, ia) == 1);
return ia;
}
int n, m;
int d[N];
long long sd[N];
long long sum (int l, int r) {
return (sd[r] - sd[l]) % MOD;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; ++i)
scanf("%d", d + i);
sort(d, d + n);
for (int i = 0; i < n; ++i)
sd[i + 1] = sd[i] + d[i];
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%d%d", &a, &b); // dur, def
int cnt = (d + n) - lower_bound(d, d + n, b);
int res = 0;
if (cnt >= a) {
res = mul( mul(cnt - a, inv(cnt)), sum(n - cnt, n) );
res += mul( mul(cnt - a + 1, inv(cnt + 1)), sum(0, n - cnt) );
res %= MOD;
}
printf("%d\n", res);
}
return 0;
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
int n, m;
li l, r;
inline bool read() {
if(!(cin >> n >> m))
return false;
cin >> l >> r;
return true;
}
const int N = int(2e5) + 555;
vector<int> divs[N];
inline void solve() {
fore(d, 1, N) {
for(int pos = d; pos < N; pos += d)
divs[pos].push_back(d);
}
li lf = m + 1, rg = m;
vector<int> cnt(m + 1, 0);
vector<int> id(m + 1, -1);
set<int> curDivs;
vector< vector<int> > ans(n + 1);
fore(x1, 1, n + 1) {
li newlf = (l + x1 - 1) / x1;
li newrg = r / x1;
assert(newrg - newlf + 1 >= 0);
while (lf > newlf) {
lf--;
for (int d : divs[lf]) {
if (cnt[d] == 0)
curDivs.insert(d);
cnt[d]++;
id[d] = (int)lf;
}
}
while (rg > newrg) {
for (int d : divs[rg]) {
cnt[d]--;
if (cnt[d] == 0)
curDivs.erase(d);
}
rg--;
}
for (int a : divs[x1]) {
auto it = curDivs.upper_bound(a);
if (it == curDivs.end())
continue;
int b = *it;
if (x1 / a * 1ll * b <= n) {
int y1 = id[b];
ans[x1] = {x1, y1, x1 / a * b, y1 / b * a};
}
}
}
fore(i, 1, n + 1) {
if (ans[i].empty())
cout << -1 << '\n';
else {
cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << '\n';
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution 1 (pikmike)**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 60;
typedef array<int, N> num;
num operator ^(const num &a, const num &b){
num c;
forn(i, N){
c[i] = a[i] + b[i];
if (c[i] >= 3) c[i] -= 3;
}
return c;
}
mt19937 rnd(42);
int main(){
int n;
scanf("%d", &n);
vector<int> a(n);
forn(i, n){
scanf("%d", &a[i]);
--a[i];
}
vector<num> nums(n);
forn(i, n) forn(j, N) nums[i][j] = rnd() % 3;
vector<vector<int>> pos(n);
vector<num> pr(1);
map<num, int> cnt;
cnt[pr[0]] = 1;
int cur = 0;
long long ans = 0;
forn(i, n){
pr.push_back(pr.back() ^ nums[a[i]]);
pos[a[i]].push_back(i);
if (pos[a[i]].size() >= 4){
while (cur <= pos[a[i]][int(pos[a[i]].size()) - 4]){
--cnt[pr[cur]];
++cur;
}
}
ans += cnt[pr.back()];
++cnt[pr.back()];
}
printf("%lld\n", ans);
}
```

**Solution 2 (pikmike)**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
typedef unsigned long long uli;
vector<int> a;
vector<pair<int, int>> t;
vector<int> ps;
pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b){
if (a.first != b.first)
return min(a, b);
return make_pair(a.first, a.second + b.second);
}
void push(int v){
if (v * 2 + 1 < int(ps.size())){
ps[v * 2] += ps[v];
ps[v * 2 + 1] += ps[v];
}
t[v].first += ps[v];
ps[v] = 0;
}
void build(int v, int l, int r){
if (l == r - 1){
t[v] = make_pair(0, 1);
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int l, int r, int L, int R, int val){
push(v);
if (L >= R)
return;
if (l == L && r == R){
ps[v] = val;
push(v);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, L, min(m, R), val);
upd(v * 2 + 1, m, r, max(m, L), R, val);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
int main(){
int n;
scanf("%d", &n);
a.resize(n);
forn(i, n){
scanf("%d", &a[i]);
--a[i];
}
t.resize(4 * n);
ps.resize(4 * n);
build(1, 0, n);
vector<vector<int>> pos(n, vector<int>(1, -1));
long long ans = 0;
forn(i, n){
int k = pos[a[i]].size();
if (k >= 1) upd(1, 0, n, pos[a[i]][k - 1] + 1, i + 1, 1);
if (k >= 3) upd(1, 0, n, pos[a[i]][k - 3] + 1, pos[a[i]][k - 2] + 1, -1);
if (k >= 4) upd(1, 0, n, pos[a[i]][k - 4] + 1, pos[a[i]][k - 3] + 1, 1);
pos[a[i]].push_back(i);
push(1);
if (t[1].first == 0) ans += t[1].second - (n - i - 1);
}
printf("%lld\n", ans);
}
```

Thanks for the editorial, the randomized solution to G is quite interesting.

really? Is it ?

I think there also should be tag

`graphs`

in the problem 1418C - Mortal Kombat Tower cause I solved it with Dijkstra's algorithm.could you please explain your solution a bit?

SpoilerThere are 4 cases:

Building GraphFor case 1 : Friend kills $$$i$$$'th boss for $$$a_i$$$ and then his next turn starts at position $$$i+2$$$ (cause $$$i+1$$$'th boss is already killed by 'us')

For case 2 : Friend kills $$$i$$$'th boss for $$$a_i$$$ and then his next turn starts at position $$$i+3$$$ (cause $$$i+1$$$'th and $$$i+2$$$'th bosses are killed by us)

For case 3 : Friend kills $$$i$$$'th and $$$i+1$$$'th bosses for $$$a_i+a_{i+1}$$$ and then his next turn starts at position $$$i+3$$$ (cause $$$i+2$$$'th boss is killed by us)

For case 4 : Friend kills $$$i$$$'th and $$$i+1$$$'th bosses for $$$a_i+a_{i+1}$$$ and then his next turn starts at position $$$i+4$$$ (cause $$$i+2$$$'th and $$$i+3$$$'th bosses are killed by us)

After building graph find the shortest path with Dijkstra. )

Thanks. Really nice solution.

You welcome. XD

I think you can model most dynamic programming problems like a graph problem. After all, dynamic programming states are nodes and transitions are directed edges. Together they create a DAG and in this problem you minimize the cost of the transitions.

Agree. This is not my first time solving a DP problem with graphs.

Or maybe dijkstra is a DP algorithm?

Not sure why you're getting downvoted. When running Dijkstra's on a graph, we can consider the graph as being implicitly ordered according to the eventual costs of the nodes, with edges going from low cost to high cost. This graph is acyclic, and the cost of a single node is computed in terms of the nodes which have an edge directed into it, which is literally just DP. The only thing that makes it different from a "normal" DP algorithm is that we compute the topological ordering of the nodes on the fly, rather than knowing it beforehand.

Maybe they don't get the idea (in a funny way), since we all know of Dijkstra as a algorithm to find shortest path in non-negative weight

graph.I think

`Dijkstra's`

is a Greedy AlgorithmI think it is not right that the model solution for D heavily relies on datastructures available in a relatively small subset of available languages, even though one of them is c++

Can someone explain the segment tree solution of G . what i didn't understand is that valid regions depend upon the choice of right border and also on the number under consideration for eg. for the array 1 2 3 3 2 5 4 4 2 3 4 3 if we fix the right border at last index and took the number 4 under consideration then the valid/invalid regions will look like 0 0 0 0 0 0 0 1 1 1 1 0 . But these regions will change if we change the right border or the number under consideration . so there are total n*n such arrays . How can we keep track of them all with segment tree . Do we require multiple segment tree or one will suffice .

One segment tree is enough. Consider which numbers change their segments when you proceed from some right border $$$r$$$ to $$$r+1$$$. Easy to see that it's only $$$a_{r+1}$$$. So we can actually clear the segments it contributed to and add the ones it contributes to now.

Thanks for explaining , just one query remaining. How do we update the regions when moving from r to r + 1, I mean a subarray can be bad not just because it doesn't has exactly 3 numbers of $$$a_{r + 1}$$$ but may be it doesn't have exactly three numbers of some other number . We can convert a good subarray to bad when moving from r to r + 1 , but how do we convert from bad to good. How do we know what numbers are making this a bad subarray .

You don't exactly store if the position is bad or good in the segtree. Each position only knows the number of bad segments it's covered by. For each bad segment $$$[l; r]$$$ you add 1 on positions $$$[l; r]$$$ in a segtree to maintain these values correct. And a position is good if the number of bad segments covering it is zero. Thus, adding a bad segment is adding 1 on a segment and removing a bad segment is subtracting 1 from a segment.

Got it . Thank you.

Such a clever and interesting approach for the problem E. I am interested to know if someone is able to solve it by going the usual way of (sum of damages for each perm / n! )

G and F should be swapped

Can someone give me links for more problems similar to G in which I can use string hashing but not of strings directly?

Hey pikmike can you tell me more about the thinking process of G. Like how did you arrive at the conclusion that we can use numbers in base 3?

Well, this xor hashing thingy is quite a common topic. I knew it because I encountered it multiple times. Initially the problem was to count the segments with 0 or 2 occurrences, so the usual xor worked perfectly.

Thus, for me the transition was only from bitwise to tritwise. BledDest suggested that idea and I found it pretty cool, props to him. Couldn't really come up with it myself.

Hey pikmike, In the post of Unofficial Editorial, I wonder whether problem D has an easier solution if we can only move one pile at a time.

I think the solution aniervs posts is right, but I wonder whether you have other clever solotuion?

The aniervs's solution was harder to interpret ( and I am still not able to understand it fully), but it would be great if an alternate solution of problem D is added to the editorial based on his idea just like you guys did for problem G(hashing and segment tree). It will help people like me in knowing different ways to tackle the problem. Also thanks for both unofficial editorial and this editorial... Learnt a lot!!

Idk if aniervs's solution is right, ternary search is quite hard to prove there. The function is surely convex but possibly not strictly convex which might break ternary search. Other than that I doubt it gets easier than such solution.

We (adedalic, if I am not mistaken) once set a similar problem about bringing some boxes to the same point, and we thought it was possible to solve it with ternary search. But, unfortunately, the function $$$f(x) = \text{minimum number of actions required to bring all items to position }x$$$ is not strictly convex because if there are two items in positions $$$x$$$ and $$$x + 1$$$, then $$$f(x) = f(x + 1)$$$, but it is not necessarily the local minimum. Though there might be some way to handle it.

Hi Pikmike and adedalic . The way we have pushed the divisors into the set for all the values from ceil(l/x1) + 1 to floor(r/x1) in the way mentioned in the editorial solution is not clear ? Like as i understand that why we can't directly pushed all the divisors of all the numbers in the range with simple for loop of divisors of all the valid numbers of the segments . And also in the method of the solution we are also not clearing the set for further iterations of x1 is very complex to comprehend . Thanks for reading the comment and I will be grateful if you will explain .

Can anyone help me identify what's wrong in my approach in C :

here's my submission : 92930622

res=min(ans(i-1,0)+a[i],ans(i-2,0)+a[i]+a[i-1]);Yes , thank you ! It was a stupid mistake

There is a mistake in the line:

if(i==0)** {** ** return a[i]; // since my friend's turn is the first one** ** }**so when you are calling ans(0,0) and ans(0,1) then you will get the same result as a[0] which shouldn't be. And really telling you only have to change only if(i==1) { if(j==0) return ans(i-1, 1); else return a[i] + ans(i-1,1); //as the first boss is only killed by the friend. }

And you can write more simpler version of it like these two : 1) https://codeforces.com/contest/1418/submission/92964444 2) https://codeforces.com/contest/1418/submission/92964444

Edit RequestpikmikeI think in problem E tutorial, you mistakenly replaced all $$$a_j$$$ for $$$b_j$$$ in every $$$max(K - a_j, 0)$$$ expression.

Thanks for the editorial . Greedy solution for C was really interesting.

@vovuh Can you explain me what is wrong with my solution although I am partitioning the two halves with respect to the mid-point and it is giving right answer for all the given test case. But it gives wrong answer on submission. Can you help me where I am wrong Please? my solution link : https://codeforces.com/contest/1418/submission/92877522[user:vovuh]`

@vovuh Can you explain me what is wrong with my solution although I am partitioning the two halves with respect to the mid-point and it is giving right answer for all the given test case. But it gives wrong answer on submission. Can you help me where I am wrong Please? my solution link : https://codeforces.com/contest/1418/submission/92877522

I've implemented the same code and it gives correct answer on my machine but it shows WA on Test Case 1. 92970290. I don't understand why this is happening.

NVM I found the error, I was inserting to the multiset a value which was not initialized. This is the final submission. 92971068

For G you would be better off using xor instead of sum. For each value generate two random integers x and y, and cyclically put x, y, x xor y in places with this value, the hash will be prefix xor.

**any one can help out why i am getting tle on

Problem Dand tc 52? i am using treemap and treeset **public class D {

// static Scanner sc = new Scanner(System.in); static StringBuilder out = new StringBuilder();

It's more simpler if you use higher and lower methods instead of ceiling and floor.

what is difference between both???

floor will return the greatest element less than or equal to that number while lower will return a strictly lower element. Similarly for ceiling and upper .

after using higher and lower still getting tle

Please.

i am getting runtime error in solution for problem c. can somebody help. https://codeforces.com/contest/1418/submission/92995605

Python has low recursion limit. Either do it iteratively or using another lang.

okk thanku.

In problem A, if I used the predefined ceil method(Java lang), it does not give the correct output. But If I did it in the other way, it is ok. Any idea?

Wrong submission

Accepted

https://codeforces.com/contest/1418/submission/93095427

Why my greedy approach is wrong for the problem C? Please give me a case that fail the solution. Thank you.

My Submission

Thanks in Adavanced..,

I had read the problem 1418B - Negative Prefixes for more than 40 min and after that I had read the solution but I wasn't able to understand these lines in block ,can any one help , I think it says we need to find array so that it prefix sum array should be like starting from negative elements and once the positive element came then there should be no negative elements(all elements after that are positive) like eg [−8,−14,−13,−9,−5,2,0] and as given in solution and k is 5 , and we need to reduce the k some and propose a solution ,but that was not the case

thanks in advance

Ok so this is what it means. Lets have this prefix sum array [-1,-4,-5,-6,7,8,9]. Here, k = 4. This is because k is the index of the "right most negative element".

Another example: prefix sum array = [1,-3,4,-5,-1,2,3] Here, k = 5. The "right most negative element" is -1, and so its index is 5. You can have positive in between the negatives, it doesn't matter. What the problem is asking is you want k to be as small as possible.

So you want to arrange the array such that its prefix sum array will have the smallest k, when compared to other arrangements.

I hope this helps!

Yeah , thanks bro..

A solution for F without any data structures, just simple math (although with many steps and cases):

For easier reading, let's rename $$$(x_1,y_1,x_2,y_2)$$$ to $$$x,a,b,c$$$, so we need to find three numbers $$$a,b,c$$$ such that $$$xa=bc \in [l,r]; a,c \in [1,m]; b \in [x+1,n]$$$. In fact, we can drop the constraint on $$$c$$$, it follows from the others.

So far, we have fixed a value of $$$x$$$. Now let's fix the greatest common divisor $$$g$$$ of $$$b,x$$$. There can only be a total of $$$n \log n$$$ such divisors across all values of $$$x$$$. The idea is to quickly find a solution given $$$g,x$$$ if it exists. We know that $$$b>x$$$ and since $$$g$$$ is their common divisor, we can write $$$b=x+yg$$$ for some $$$y>0$$$. The constraint on $$$b$$$ becomes $$$y\leq \frac{n-x}{g}$$$. Also, since $$$b$$$ divides $$$ax$$$, we have that $$$b/g$$$ divides $$$a(x/g)$$$ and so, since $$$b/g$$$ and $$$x/g$$$ are coprime, $$$b/g$$$ divides $$$a$$$, and so $$$a=(b/g)z=(x/g+y)z$$$ for some $$$z$$$.

Let's handle two cases:

1) $$$g > \sqrt{x}$$$. In this case there can be at most $$$x/g < \sqrt x$$$ different values of $$$y$$$ and we can try each. For a fixed $$$y$$$, we check whether $$$b$$$ fits the constraints and whether we can find $$$z$$$ such that $$$a$$$ also fits the constraints.

2) $$$g \leq \sqrt{x}$$$. We try each value of $$$z$$$ as long as $$$a$$$ is less than $$$m$$$. In fact, from $$$a=(x/g+y)z$$$ and $$$y>0$$$ we have $$$z \leq \frac{m}{x/g+1}$$$. After fixing $$$z$$$, we look for $$$y$$$ to fulfil the linear constraints given above (a couple of integer divisions and min/max).

Overall, the sum of small divisors (less than $$$\sqrt{x}$$$ for all numbers $$$x$$$ up to $$$n$$$ is asymptotically $$$O(n \sqrt n)$$$, and the sum of all values $$$\frac{1}{x/g+1}$$$ for all small divisors is asymptotically equal to $$$O(\sqrt n)$$$, so the overall complexity is $$$(n+m)\sqrt{n}$$$.