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;
if (n % 2 == 1) {
cout << "NO" << '\n';
continue;
}
cout << "YES" << '\n';
for (int i = 0; i < n / 2; ++i)
for (int j = 0; j < 2; ++j)
cout << "AB"[i & 1];
cout << '\n';
}
}
```

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 (auto& x : a) cin >> x;
vector<int> b({a[n - 1]});
for (int i = n - 2; i >= 0; --i) {
if (a[i] > b.back()) {
b.push_back(a[i] % 10);
b.push_back(a[i] / 10);
} else {
b.push_back(a[i]);
}
}
cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n';
}
}
```

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<char> ok1(n / 2), ok2(n / 2);
for (int i = 0; i < 2; ++i) {
string s;
cin >> s;
for (int j = 0; j < n; ++j) if ((i + j) & 1) {
ok1[(i + j) / 2] |= (s[j] == '>');
ok2[(j - i + 1) / 2] |= (s[j] == '>');
}
}
bool ans = true;
for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i];
cout << (ans ? "YES" : "NO") << '\n';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
for _ in range(int(input())):
s = input()
n = len(s)
ans = 0
for d in range(1, n // 2 + 1):
cnt = 0
for i in range(n - d):
cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?'
if i - d >= 0:
cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?'
if i - d >= -1 and cnt == d:
ans = 2 * d
print(ans)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n), c(n);
for(int i = 0; i < n; i++)
{
a[i] = i + 1;
c[i] = i / k + 1;
}
int q = *max_element(c.begin(), c.end());
for(int i = 1; i <= q; i++)
{
int l = find(c.begin(), c.end(), i) - c.begin();
int r = c.rend() - find(c.rbegin(), c.rend(), i);
int m = (l + r) / 2;
reverse(a.begin() + l, a.begin() + m);
reverse(a.begin() + m, a.begin() + r);
}
for(int i = 0; i < n; i++)
cout << a[i] << " \n"[i == n - 1];
cout << q << "\n";
for(int i = 0; i < n; i++)
cout << c[i] << " \n"[i == n - 1];
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
```

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 mul(int x, int y) {
return x * 1LL * y % MOD;
}
int binpow(int x, int y) {
int z = 1;
while (y) {
if (y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<int> suma(n + 1), sumb(n + 1);
for (int i = 0; i < n; ++i) {
suma[i + 1] = suma[i] + a[i];
sumb[i + 1] = sumb[i] + b[i];
}
int m = sumb[n];
vector<int> f(m + 1), invf(m + 1);
f[0] = 1;
for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i);
invf[m] = binpow(f[m], MOD - 2);
for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i);
vector<int> sumc(m + 2);
for (int i = 0; i <= m; ++i)
sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i])));
int pw2 = binpow(binpow(2, MOD - 2), m);
while (q--) {
int l, r;
cin >> l >> r;
--l;
int k = 2 * (suma[r] - suma[l]) - suma[n];
int cur = sumb[r] - sumb[l];
int mx = max(0, min(k + cur, m + 1));
int cnt = sumc[mx];
cout << mul(cnt, pw2) << ' ';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
int n, c;
int g[21][21];
const int INF = int(1e9);
int primMST(int vertex_cover_mask)
{
vector<int> d(n, INF);
vector<bool> used(n, false);
d[0] = 0;
int ans = 0;
for(int i = 0; i < n; i++)
{
int idx = -1;
for(int j = 0; j < n; j++)
{
if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx]))
idx = j;
}
if(idx == -1) return INF;
used[idx] = true;
ans += d[idx];
for(int k = 0; k < n; k++)
{
if(used[k])
continue;
if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0)
continue;
d[k] = min(d[k], g[idx][k]);
}
}
return ans;
}
int main()
{
cin >> n >> c;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> g[i][j];
if(g[i][j] == 0) g[i][j] = INF;
}
}
int ans = INF;
for(int mask = 0; mask < (1 << n); mask++)
{
int cur = primMST(mask);
if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask));
}
cout << ans << endl;
}
```

In problem B why do we need to iterate through array from right to left and not from left to right?

Counterexample:

1

3

12 46 20

If we will iterate from left to right we will get:

1) 12 < 46. Don't change the array

2) 46 > 20. Split 46 by 4 and 6

And we got:

12 4 6 20. Which is not a non-growth sorted array.

If we will iterate from right to left we will get:

1) 46 > 20. Split 46 by 4 and 6

2) 12 > 4. Split 12 by 1 and 2

And we got:

1 2 4 6 20. Which is a non-growth sorted array.

Summary, iterating from left to right will give us the wrong answer. This is because the right element can split and become smaller than the left element, but we have already checked that the left element is larger than the right element and will not go back to check it again.

thx

Nice Explanation , Thanks

Suppose initially $$$a_{i-1} \le a_i$$$; but after considering $$$a_i$$$ with $$$a_{i+1}$$$, we find out that we have to split $$$a_i$$$. This might break the condition $$$a_{i-1} \le a_i$$$, so if we iterate from left to right, we sometimes have to backtrack to fix the conditions we've broken

thx

You can go from left to right also. My logic while going from left to right: https://mirror.codeforces.com/contest/1948/submission/251609551

^read lastDigit as lastNumber

I solved the problem by iterating from left to right with following logic: you want current element (CUR which can also be last digit if we divided the number in previous step) to be as small as possible because that can only help for next numbers, so you have two cases: 1) if you CAN divide current element i into it's digits with equality holding: CUR <= dig1 <= dig2 you do so, because then CUR = dig2 which is smallest possible. If you can't, if CUR <= a[i] then CUR = a[i]. If both do not hold, return NO. This works because at any moment, last element you have in your new array will be smallest possible which can only help for both of previously mentioned checks.

I write a simple brute force for Problem :B. But it is failing of hidden case.I am not able guess what it lacks. Can you please help. https://ideone.com/g5da0S

you are iterating from left to right , as explanied in above comment ( https://mirror.codeforces.com/blog/entry/127182#comment-1128987 ) iterate from right to left then it might results in correct answer.

In the place of tutorial of G ,it is showing tutorial of F.Update it please.

Fixed it, sorry.

is it possible to solve Div2-D in less than O(n^2)?

Can someone please explain in solution of problem C. What are ok1 and ok2 actually signifying? How are we taking the indices of ok1 and ok2.

I have been trying to understand for an hour, please help.

$$$ok1[i]$$$ and $$$ok2[i]$$$ refer to the second solution from the editorial. If $$$ok[i]$$$ is true, then the $$$i$$$-th diagonal pair of odd cells has at least one arrow to the right ($$$ok1$$$ and $$$ok2$$$ denote different diagonal directions).

You can instead check every diagonal pair by bruteforcing all pairs of adjacent odd cells.

but if n=4 and i,j=0,3.then (j-i+1)/2=2.ok2.size() is 2,so will cross the border?

I thought D was hashes, wasnt able to implement it well tho... The author's solution is kinda weird

Let me explain my solution of D -- I hope this might be easier to understand.

First, let's fix the length of a tandem, and call it $$$2d$$$ ($$$d$$$ is the length of each half of the tandem). For each $$$d$$$, we try to find a tandem repeat of length $$$2d$$$, and the answer to the problem is the length of the longest one we could find. Also let's define the length of $$$s$$$ as $$$n = |s|$$$.

A substring $$$s_l s_{l+1} \cdots s_{l + 2d - 1}$$$ is a tandem repeat if, for all indices $$$i \in \{ l, l+1, \ldots, l+d-1 \}$$$, $$$s_i = s_{i+d}$$$ is held. So, what matters here is the relationship between characters with distance $$$d$$$. With that in mind, let's define an array $$$\{ a_i \} \; (1 \le i \le n - d)$$$ as follows: $$$a_i = 1$$$ if $$$s_i = \text{'?'}$$$ or $$$s_{i+d} = \text{'?'}$$$ or $$$s_i = s_{i+d}$$$; $$$a_i = 0$$$ otherwise. Intuitively, $$$a_i$$$ is $$$1$$$ if $$$s_i$$$ and $$$s_{i+d}$$$ are equal or can be made equal. With this array $$$\{ a_i \}$$$, we can rephrase the condition that $$$s_l s_{l+1} \cdots s_{l + 2d - 1}$$$ can be a tandem repeat to: $$$a_l = a_{l+1} = \cdots = a_{l+d-1} = 1$$$ (selection of $$$\text{'?'}$$$s do not matter because each pair of letters in a tandem do not interfere with any other pairs). Thus, if there is a contiguous sequence of $$$1$$$s of length $$$d$$$ in $$$\{ a_i \}$$$, we have a tandem repeat of length $$$2d$$$; otherwise, there's no such tandem.

Building $$$\{ a_i \}$$$ and finding contiguous $$$1$$$s can be done in $$$O(n)$$$-time, so $$$O(n^2)$$$-time overall.

Thank for explaining

nice explanation

"Kruskal's algorithm with DSU might be a bit slower, but can also get accepted"

I don't thinks so :(

I think it's possible to optimize this, for example, by sorting all edges only once, not for every Kruskal run.

Didn't think of that, thanks you!

Problem D (Tandem Repeat) Video Editorial : (Audio : Hindi)

Link : ---Click Here (YOUTUBE)

Problem A, B Video Editorial : --Click Here

Here's a formulation of F as a probability problem (mostly because I am in a probability class right now :3).

Suppose we have $$$s$$$ silver coins in the bag, $$$g$$$ gold coins in the bag, $$$t_s$$$ total silver coins and $$$t_g$$$ total gold coins. The value of the silver coins in the bag is represented by the random variable $$$S\sim \mathrm{Binom}(s,\frac{1}{2})$$$. The value of the rest of the silver coins is represented by the random variable $$$S'\sim \mathrm{Binom}(t_s-s,\frac{1}{2})$$$.

We wish to compute

The difference between random variables isn't nice to compute, so we want to turn it into a sum. Notice that the random variable $$$S' ':= t_s-s-S'$$$ has the same $$$\mathrm{Binom}(t_s-s,\frac{1}{2})$$$ distribution as $$$S'$$$ (this only holds because our probabilities are $$$\frac{1}{2}$$$). Therefore,

But the sum of binomial random variables is itself a binomial random variable: $$$S+S' '\sim \mathrm{Binom}(t_s-s+s,\frac{1}{2}) = \mathrm{Binom}(t_s,\frac{1}{2})$$$, which gives us the formula

Here is my submission implementing this: 251836049.

This n^3 method passed systest. Can anyone hack it?

code

Video Editorial For Problems A,B,C,D,E,F.

Problem G is awesome. I cannot put forward Konig's theory because I didn't realize that a tree is a bipartite graph during the contest. Sad.

Can anyone please provide the solution of B using DP , I think we can use bit masking to solve this as the value of Dp[i] (whether performing operation on the i'th index will result in a sorted array or not ) depends on the pervious values too , so we can have a mask that denotes on which of the previous indexes we have performed the operation ,Thanks for the help .

code

Can you take a look into this code

I did BF using recursion to find all possibilities, but a test case is failing ?

Very fun problems, I like this contest!

In problem B i dont understand why when i Used a variable to iterate through the inputs of the array it and manipulate using the same algorithm it didnt work , however when i accepted all inputs in a vector , and started iterating and using my algorithm it worked out ? (check my accepted solution and the rejected one Using the Second Testing table) 252372121 252375040 Would be nice if someone can explain :/

problem D have weak test casesMy O(N^3) solution passes : O(N^3) submission

I have found an alternative solution to problem C only using if condition and do while loops -(https://mirror.codeforces.com/blog/entry/127853)

Hi, for Problem D, when I run my code locally with the provided testcases I get the correct answer. However, when I submit, I get a different output. Any ideas what's going on? link to submission

Hi, can anyone explain for me why the example answer of F — rare coins is that long line of integer?

I am not able to understand how the parity of coordinates sum will decide the category of a cell?

In problem F, why we use

`pw2 = binpow(binpow(2, MOD - 2), m)`

but not`pw2 = binpow(binpow(2, m), MOD - 2)`

? I really don't understand it, can anyone explain this for me?they calculate the same thing.

remember that binpow(x, MOD — 2) is finding the inverse of $$$x$$$, which is effectively $$$1/x$$$. So binpow(binpow(2, MOD — 2), m) means $$$(1/2)^m$$$. And binpow(binpow(2, m), MOD — 2) means $$$1/(2^m)$$$

$$$(2^x)^y = (2^y)^x = 2^{xy}$$$

Gotta say Tandem repeat taught me here.Good EDU problem

I have written dp solution for C problem....i am new in dp and only trying to solve any dp tagged prob with dp only so i tried not going towards other approach and finally was able to dpify the solution

LINK : https://mirror.codeforces.com/problemset/submission/1948/279865881