Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while (t--){
long long x1, x2;
int p1, p2;
cin >> x1 >> p1 >> x2 >> p2;
int mn = min(p1, p2);
p1 -= mn;
p2 -= mn;
if (p1 >= 7)
cout << ">" << endl;
else if (p2 >= 7)
cout << "<" << endl;
else{
for (int i = 0; i < p1; ++i) x1 *= 10;
for (int i = 0; i < p2; ++i) x2 *= 10;
if (x1 < x2)
cout << "<" << endl;
else if (x1 > x2)
cout << ">" << endl;
else
cout << "=" << endl;
}
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int mn = *min_element(a.begin(), a.end());
for (int i = 0, k = 0; k < n / 2; ++i) if (a[i] != mn) {
cout << a[i] << ' ' << mn << '\n';
k += 1;
}
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
int t;
cin >> t;
while (t--) {
int n;
li h;
cin >> n >> h;
vector<li> a(n);
for (li &x : a) cin >> x;
li l = 1, r = 1e18;
while (l <= r) {
li m = (l + r) / 2;
li sum = m;
for (int i = 0; i < n - 1; ++i)
sum += min(m, a[i + 1] - a[i]);
if (sum < h) l = m + 1;
else r = m - 1;
}
cout << r + 1 << '\n';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
return x;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
vector<int> dp1(n + 2), dp2(n + 2);
dp1[0] = 1;
while (n--) {
int x;
scanf("%d", &x);
dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]);
dp1[x + 1] = add(dp1[x + 1], dp1[x]);
if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]);
if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]);
dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]);
}
int ans = 0;
for (int x : dp1) ans = add(ans, x);
for (int x : dp2) ans = add(ans, x);
printf("%d\n", add(ans, MOD - 1));
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct cell{
int x, y;
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int main() {
int t;
cin >> t;
while (t--){
int n, m;
cin >> n >> m;
vector<string> s(n);
int lx = -1, ly = -1;
forn(i, n){
cin >> s[i];
forn(j, m) if (s[i][j] == 'L'){
lx = i;
ly = j;
}
}
auto in = [&](int x, int y){
return 0 <= x && x < n && 0 <= y && y < m;
};
vector<vector<int>> d(n, vector<int>(m, 0));
forn(x, n) forn(y, m) if (s[x][y] == '.'){
forn(i, 4){
int nx = x + dx[i];
int ny = y + dy[i];
d[x][y] += in(nx, ny) && s[nx][ny] != '#';
}
}
queue<cell> q;
vector<vector<char>> used(n, vector<char>(m, 0));
q.push({lx, ly});
used[lx][ly] = true;
while (!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
forn(i, 4){
int nx = x + dx[i];
int ny = y + dy[i];
if (!in(nx, ny) || s[nx][ny] == '#' || used[nx][ny]) continue;
--d[nx][ny];
if (d[nx][ny] <= 1){
used[nx][ny] = true;
q.push({nx, ny});
}
}
}
forn(i, n){
forn(j, m) if (s[i][j] == '.' && used[i][j])
s[i][j] = '+';
cout << s[i] << "\n";
}
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define sz(a) int((a).size())
const int MOD = 998244353;
struct Mint
{
int val;
bool operator==(const Mint& other)
{
return val == other.val;
}
Mint operator+(const Mint& other)
{
int res = val + other.val;
while(res >= MOD) res -= MOD;
while(res < 0) res += MOD;
return Mint(res);
}
Mint operator-(const Mint& other)
{
int res = val - other.val;
while(res >= MOD) res -= MOD;
while(res < 0) res += MOD;
return Mint(res);
}
Mint operator*(const Mint& other)
{
return Mint((val * 1ll * other.val) % MOD);
}
Mint pow(int y)
{
Mint z(1);
Mint x(val);
while(y > 0)
{
if(y % 2 == 1) z = z * x;
x = x * x;
y /= 2;
}
return z;
}
Mint operator/(const Mint& other)
{
return Mint(val) * Mint(other.val).pow(MOD - 2);
}
Mint() {
val = 0;
};
Mint(int x)
{
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
val = x;
};
};
ostream& operator<<(ostream& out, const Mint& x)
{
return out << x.val;
}
const int g = 3;
const int LOGN = 19;
vector<Mint> w[LOGN];
vector<int> rv[LOGN];
void prepare() {
Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
forn(st, LOGN - 1) {
w[st].assign(1 << st, 1);
Mint bw = wb.pow(1 << (LOGN - st - 1));
Mint cw = 1;
forn(k, 1 << st) {
w[st][k] = cw;
cw = cw * bw;
}
}
forn(st, LOGN) {
rv[st].assign(1 << st, 0);
if (st == 0) {
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
forn(k, 1 << st)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
void ntt(vector<Mint> &a, bool inv) {
int n = sz(a);
int ln = __builtin_ctz(n);
forn(i, n) {
int ni = rv[ln][i];
if (i < ni) swap(a[i], a[ni]);
}
forn(st, ln) {
int len = 1 << st;
for (int k = 0; k < n; k += (len << 1)) {
fore(pos, k, k + len){
Mint l = a[pos];
Mint r = a[pos + len] * w[st][pos - k];
a[pos] = l + r;
a[pos + len] = l - r;
}
}
}
if (inv) {
Mint rn = Mint(n).pow(MOD - 2);
forn(i, n) a[i] = a[i] * rn;
reverse(a.begin() + 1, a.end());
}
}
vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
a.resize(cnt);
b.resize(cnt);
ntt(a, false);
ntt(b, false);
vector<Mint> c(cnt);
forn(i, cnt) c[i] = a[i] * b[i];
ntt(c, true);
return c;
}
vector<Mint> norm(vector<Mint> a)
{
while(a.size() > 1 && a.back() == Mint(0))
a.pop_back();
return a;
}
const int N = 250043;
vector<int> G[N];
int d[N];
Mint fact[N * 2];
Mint rev[N * 2];
void dfs(int x, int p)
{
if(p != x) d[p]++;
for(auto y : G[x]) if(y != p) dfs(y, x);
}
Mint C(int n, int k)
{
return fact[n] * rev[k] * rev[n - k];
}
int main()
{
prepare();
fact[0] = Mint(1);
for(int i = 1; i < N * 2; i++) fact[i] = fact[i - 1] * i;
for(int i = 0; i < N * 2; i++) rev[i] = Mint(1) / fact[i];
int n;
scanf("%d", &n);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(0, 0);
vector<vector<Mint>> cur;
for(int i = 0; i < n; i++)
if(d[i] > 0)
cur.push_back(vector<Mint>({Mint(1), Mint(d[i])}));
while(cur.size() > 1)
{
vector<vector<Mint>> ncur;
for(int i = 0; i + 1 < cur.size(); i += 2)
ncur.push_back(norm(mul(cur[i], cur[i + 1])));
if(cur.size() % 2 == 1) ncur.push_back(cur.back());
cur = ncur;
}
Mint ans = 0;
for(int i = 0; i < cur[0].size(); i++)
{
if(i % 2 == 0) ans = ans + cur[0][i] * fact[n - i];
else ans = ans - cur[0][i] * fact[n - i];
}
cout << ans << endl;
}
```

In my opinion , E might be a little easier than D , so I recommend swapping D and E .

Neat and Clean explanations especially on F. Thank you!

This was a great contest, learned about FFT technique from problem F which seems quite useful

great problems! great editorial! I learnt a lot.

i wrote this dp solution for problem DSpoilerProblem F can be solved in $$$O(n\log n)$$$ time:

SpoilerConsider maintaining the product for those vertex such that $$$d_i \ge k$$$ and loop $$$k$$$ from $$$n$$$ to $$$1$$$. Each time we only need to multiply $$$(1+kx)^{\sharp_k}$$$, where $$$\sharp_i$$$ denotes the number of vertices such that $$$d_i = k$$$. The complexity can be bounded by

There is also an much more complex algorithm that solve F in $$$O(n)$$$:

SpoilerWe define linear functional $$$L: x^n \mapsto n!$$$, our goal is to evaluate $$$\displaystyle L\left(\prod_{i=1}^n (x-d_i)\right)$$$. Let $$$\sharp_k = \sharp i \mid d_i = k$$$, let $$$\displaystyle P(x)= \prod_{k < B} (x-k)^{\sharp_k}$$$ and $$$\displaystyle Q(x) = \prod_{k\ge B} (x-k)^{\sharp_k}$$$.

Since $$$\displaystyle L(PQ) = \sum_{i\le n/B} L(x^iP) \cdot [x^i]Q$$$. Noticed that $$$\displaystyle \sum_{i=1}^n d_i = n-1$$$, evaluation of $$$Q$$$ has an upper bound $$$O\left(\frac{n\log^2 n}{B}\right)$$$. (This estimation might be improved)

Since $$$P$$$ has an P-recurrence with order $$$B$$$, we can evaluate $$$L(P)$$$ in $$$\tilde O(\sqrt n \operatorname{poly} B)$$$ by the fast algorithm for P-recursive sequence. Then we show that $$$L(x^i P)$$$ has an recurrence respect to $$$i$$$.

Noticed that $$$L(P) = P(0) + L(P')$$$ for all $$$P$$$, we have the recurrence of $$$L(x^iP)$$$

and we have the recurrence

For each $$$i$$$ the recurrence takes $$$O(B)$$$ arithmetic operations. Since we only need to evaluate for $$$i\le n/B$$$, the complexity of evaluating the recurrence is $$$\displaystyle O\left(\frac n B \cdot B\right) = O(n)$$$. The evaluation of $$$i=0$$$ costs $$$\tilde O(\sqrt n \operatorname{poly} B)$$$.

The total complexity is $$$O\left(n + \sqrt n \operatorname{poly}(B) \log n + \frac{n\log^2 n}{B}\right)$$$. Taking $$$B=\Theta(\log^2n)$$$ we have the time complexity $$$O(n)$$$.

Umnik: "Idk how Elegia's mind works"

Those interested in how um_nik's mind works can read how to solve it in $$$O(N log N)$$$ in simpler notations here

Captain EI txdy txdy txdy

I've never heard of this before, could you link to a tutorial / paper or something?

The brief idea is to evaluate $$$\mathbf M(x+1)\mathbf M(x+2)\cdots \mathbf M(x+\sqrt n)$$$ for $$$x=\sqrt n, 2\sqrt n, \dots, \sqrt n \cdot \sqrt n$$$ where $$$\mathbf M(x)$$$ is a matrix with polynomial entries. Min-25 gives an algorithm that achieves the smallest log factor currently. Though his original blog was not available for some reason, there is a detailed description of this algorithm in the editorial of CF Round #700 div1. E.

I read that editorial, but unfortunately don't see how it is connected to this problem.

Oh, also, what's the P-recursive equation for $$$P$$$?

Since $$$\displaystyle \log P = \sum_{k<B} \sharp_k \log (x-k)$$$, we take derivation on both sides, then we obtain

By extracting the coefficients on both sides you obtained a P-recursive equation of $$$[x^i]P$$$ immediately. Consider $$$f_i$$$ is P-recursive, then $$$g_i = i! \cdot f_i$$$ is also P-recursive (You can obtain the equation by simply replacing $$$f_i$$$ with $$$g_i/i!$$$ and then multiplying $$$i!$$$ on both sides of the equation). So its sum can be evaluated through the algorithm.

There are more tricky ways to deal with the recurrence to reduce the $$$\operatorname{poly} B$$$ factor, but I omitted the details here since it's not the bottleneck of the entire problem :)

it would be very interesting to see the code for the $$$O(n)$$$ solution

damn those are some very elegant solutions

I don't understand why the runtime is $$$O(n \log^2 n)$$$ in problem F.

We can write the divide and conquer runtime as $$$T(n) = 2 * T(n / 2) + O(n \log n)$$$. This is case 3 in the master theorem of divide and conquer which yields $$$T(n) = \theta(n \log n)$$$, no?

Do you have an implementation? This sounds cool.

I didn't solve this problem, I'm simply reading the solution from the editorial and wondering why their implementation is $$$O(n \log^2 n)$$$ instead of $$$O(n \log n)$$$.

I think my mistake is probably that the 3rd case of the master theorem doesn't apply here, and the master theorem cannot be used. To use the master theorem case 3 there must exist a constant $$$\epsilon > 0$$$ such that $$$n \log n = \theta(n^{1 + \epsilon})$$$, and it might not exist.

Because the $$$f(n) = \Theta(n \log(n)) = \Theta(n^{c_{crit}} log(n)^1)$$$, this recurrence actually falls in case 2 of the master theorem (if you hold on the order of cases in wikipedia). This solves to a running time of

.

I was referring to the cases from CLRS (page 94) and the case 2 is more specific there, and it doesn't fall into it.

Indeed if I look at Wikipedia the case 2 is more generic and it does apply in this case, thanks!

Video Editorial of A,B,C

E is the easiest problem.

In problem D,Why the ans should become ans — 1?

We initialize $$$dp1_{0,0}$$$ with a $$$1$$$, which represents an empty subsequence (which has MEX equal to $$$0$$$). At the end we accumulate the answers and count it in. Since we are asked to count only non-empty subsequences, we should subtract it.

Thank you,I got it.

I cant understand why the number of colorings that meet $$$k$$$ choosen violations is $$$(n-k)!$$$ in problem

F, can someone explain it in more details please?I can give an intuitive idea behind that. For every violated constraint, a node of the tree is already defined by its parent (it's just their parent's number minus one). So basically out of the $$$ n $$$ nodes, we can focus on the $$$ n - k $$$ nodes which aren't tied to their parents and think about the

relative order between them.Let's build a sequence of these untied nodes in which the first node has the highest value $$$ n $$$, the second the next highest value and so on.

Of course you can choose any of them to have the highest value $$$ n $$$, then choose any other node to have the next highest value (which depends on the previous node as it might have induced the value $$$ n - 1 $$$ to one of its children and maybe more values to its descendants) and so on. The thing is you can choose any of the untied nodes to go next in this sequence. Therefore you can have any possible relative order between them, so the number of colorings is $$$ (n - k)! $$$

Thank you, it was very helpful !

I feel like F should have a "divide and conquer" tag based on what's written in the editorial, is it really so?

UPD: Thanks for adding the tag, hope it will help people in their practice later ^_^Can someone help me in E, 137783013 it keeps getting TLE but it's just a BFS.

Try replacing your endl by "\n"

endl is slower. It also flushes the output

Thanks a lot! In a million years I wouldn't have thought of that

It's a very bad thing!!!

How could one handle this at the contest time? Please explain anyone, who had handled such things.

Is it a reason for a problem left unsolved?

Those who have solved this problem by putting just "\n" instead of endl, please tell me, how did you figure out that at the contest time?

BledDest awoo

One thing I can't understand in the tutorial for D: The tutorial says that [0,0,1,1,1,2,3,3] is a MEX-correct sequence. However, this violates the definition of MEX-correctness. For example, let i = 7. Now MEX(0,0,1,1,1,2,3) = 4. |0 — 4| = 4, |1 — 4| = 3, and |2 — 4| = 2. These are all violations of MEX-correctness as described in the question. May you elaborate on how the above sequence is MEX-correct?

i think you should just solve problem A first..

Please read the second announcement. You got a wrong understanding of MEX-correct sequence.

The sequence (x1, x2, x3, .., xi) is mex-correct if :- | xi — mex(x1, x2, x3, ..., xi) | <= 1 ; where xi is the last element in sequence. Hence for sequence (0,0,1,1,1,2,3) => mex(0,0,1,1,1,2,3) = 4 and xi=3 (last_element_in_sequence). Here, | xi — mex| = |3-4| = 1 and 1 <=1. Hence it is correct

https://atcoder.jp/contests/abc213/tasks/abc213_h The above problem from atcoder have the solution where one has to apply DNC FFT stuff. While The Problem F seems like a polynomial multiplication where one prefers to multiply shorter polynomial first. We can do it along the similar line of merge-sort or simply use priority queue and multiply shorter polynomials each time. 137796885. How is it DNC FFT? (Or what is DNC FFT exactly?)

I couldn't understand the editorial this much but can I solve E like this?? we implement a bfs or dfs from lab and just change to + the cells of grid which we can control and we can reach them with a path from the lab that we can control?? we can control means that the cell has two paths or less.

You can start a BFS from the lab. Mark lab as + for generalization sake. During bfs, do the following: 1. If a cell you are looking at has at most one neighbour cell which is not blocked and not with plus, then mark that cell as +. 2. If a cell is marked + now, push all of its neighbour cells to the queue unless the neighbour cell was visited from this particular cell. In other words, keep visited not just for some cell, but for a parent-child relationship. If cell a already pushed cell b to a queue, then don't let a to push b again, but some other cell c can still push b. 3. Go to the next queue element. Pretty sure there is no way to solve this problem using DFS.

There is a dfs solution, check my submission: 137662230. Consider the lab is the root, we follow the four "hallways". At any square we find it connects to more than 1 '.', stop there.

thanks I understood:)

Thanks to div2, I became a pupil

Thank you for the contest!!

Can anyone please tell me what's wrong in my submission for E?

I am getting TLE on : 137850453 Also this is the exact same solution which got passed in about 200 ms : 137675491

Dont use

`std::endl`

, use`"\n"`

instead.Flushing

`std::cout`

is very slow, especially when you need to do it 1000000 times.see this: 137852168 and 137853185

In problem E (Crazy Robot) I am getting wrong answer over test case 8

My solution:- https://codeforces.com/contest/1613/submission/137885700

If anyone can help me out

Thanks in advance

AC: https://codeforces.com/contest/1613/submission/137914304

Your mistake is using

`stack<char> qx; stack<char> qy;`

. it should be`stack<int>`

to not overflow as a char overflows quickly.As a tip, this is how I debugged your code. Use

`assert()`

and insert it at different points of your code to see where things went wrong. I`assert()`

ed that your values were valid just before pushing it onto the stack, as well as`assert()`

ing the values at the start of the function. It was okay before pushing it onto the stack, but not when you used it in the function. So I can deduce that something must have went wrong when you passed it into the function, and that's how I found out.Thanks bro

i should have joined the tournament

[deleted]

No, $$$1 \leq x_2 \leq 10^6 $$$. Your input $$$1000000000000$$$ is too large.

thanks for explanation, i mistakenly read that as 10^16 .

An alternative solution for C without using binary search.

Let $$$d_1, d_2, ... d_{n-1}$$$ be the differences $$$a_{i+1}-a_{i}$$$ sorted in non-descending order. Now it is easy to calculate the damage to the dragon as a function of $$$k$$$ if we observe that for $$$k = d_{i}$$$ it is equal to $$$\sum_1^{i} d_i + (n - i) \cdot k$$$, and for other values it is linear with the slope 1.

https://codeforces.com/contest/1613/submission/137715371

This solution would have an advantage if there were multiple queries for different values of $$$k$$$, since it would be $$$O(1)$$$ per query if we precalculate prefix sums.

Thanks for the great editorial for D!

Thanks for the problems and editorial.

Can anyone provide some problems similar to problems D and E?

Binary search tagged problems for D

Any ideas why my solution D timed out on test 10? Seems like I have done everything the right way.

https://codeforces.com/contest/1613/submission/137705963

I can't get why are we printing "r + 1" answer in question C and not simply "r".

Hey, this has simply got to do with the way the binary search was written. From the code, you can see (thanks to the if else) that the variable r will be the greatest value for which the sum will be < h. You can understand this as: if the sum >= h, then r = r-1. So r will be lowered until it reaches the optimal solution-1. There is actually another way to write this binary search. In my solution, I wanted "lo" to be the smallest value such that the sum would be >= h. Link to my solution: https://codeforces.com/contest/1613/submission/138581286 I hope this is clearer to you now! Do not hesitate to reply if it is not clear enough :)

Can anyone please help me , Why am I getting memory limit exceeded on 8th test case in problem E ? https://codeforces.com/contest/1613/submission/138290812

Never mind It got resolved after passing multidimensional vectors by reference which helped me removing some unnecessary global containers.

In 1613D — MEX Sequences, for the 1st test case, why [0,2,1] is not in the answer? MEX([0,2,1]) = 3 0 — 3 = -3 <= 1 2 — 3 = -1 <= 1 1 — 3 = -2 <= 1

So the correct answer should include: [0], [1], [0,1], [0,2], [0,2,1]

Thanks for any hint. If I understand it correctly, in the last test case:

0 1 2 3

The answer should include:

[0], [1], [0,1], [0,2], [0,1,2], [0,1,3], [0,1,2,3]

Please correct me if I am wrong.

Thanks heaps :D

[0 2 1] is not correct

in ith step we get mex from (x1, x2.... xi)

i = 0; we have (0) now mex is 1. so |0-1| = 1 <= 1.. right. i = 1; we have (0, 2). now mex is 1. so |2 — 1| = 1 <= 1.. right. i = 2; we have (0, 2, 1). now mex is 3. so |1 — 3| = 2 > 1... wrong;

Thanks, Wolowitz! I didn't notice it was inside a math absolute value, LOL. Shame on me~