Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
vector<int> s(4);
for (int& x : s) cin >> x;
if (min(s[0], s[1]) > max(s[2], s[3]) || max(s[0], s[1]) < min(s[2], s[3]))
cout << "NO\n";
else
cout << "YES\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 (int &x : a) cin >> x;
sort(a.begin(), a.end(), [](int x, int y) {
return x % 2 < y % 2;
});
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ans += __gcd(a[i], a[j] * 2) > 1;
}
}
cout << ans << endl;
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
vector<vector<int>> lst(2, vector<int>(2, -1));
long long ans = 0;
for (int i = 0; i < int(s.size()); ++i) {
int j = i - 1;
int p = i & 1;
if (s[i] != '1') j = min(j, max(lst[0][p ^ 1], lst[1][p]));
if (s[i] != '0') j = min(j, max(lst[0][p], lst[1][p ^ 1]));
ans += i - j;
if (s[i] != '?') lst[s[i] - '0'][p] = i;
}
cout << ans << '\n';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin >> k;
string s;
cin >> s;
reverse(s.begin(), s.end());
int n = 1 << k;
vector<int> cnt(2 * n, 1);
auto upd = [&](int i) {
return cnt[i] = (s[i] != '0' ? cnt[i * 2 + 1] : 0) + (s[i] != '1' ? cnt[i * 2 + 2] : 0);
};
for (int i = n - 2; i >= 0; i--) {
upd(i);
}
int q;
cin >> q;
while (q--) {
int p;
char c;
cin >> p >> c;
p = n - p - 1;
s[p] = c;
while (p) {
upd(p);
p = (p - 1) / 2;
}
cout << upd(0) << '\n';
}
}
```

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);
const int LOG = 20;
int q;
vector<int> a, c;
vector<int> p[LOG];
int main() {
cin >> q;
a.resize(q + 1);
c.resize(q + 1);
fore (lg, 0, LOG)
p[lg].resize(q + 1);
fore (lg, 0, LOG)
p[lg][0] = 0;
cin >> a[0] >> c[0];
fore (id, 1, q + 1) {
int tp; cin >> tp;
if (tp == 1) {
int pr; cin >> pr;
cin >> a[id] >> c[id];
p[0][id] = pr;
fore (lg, 1, LOG)
p[lg][id] = p[lg - 1][p[lg - 1][id]];
}
else {
int v, w;
cin >> v >> w;
int ansR = 0;
li ansS = 0;
while (w > 0 && a[v] > 0) {
int u = v;
for (int lg = LOG - 1; lg >= 0; lg--) {
if (a[p[lg][u]] > 0)
u = p[lg][u];
}
int mn = min(a[u], w);
a[u] -= mn;
w -= mn;
ansR += mn;
ansS += mn * 1ll * c[u];
}
cout << ansR << " " << ansS << endl;
}
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int LN = 20;
const int K = 12000;
int pw2[1 << LN];
vector<int> sorted_segments(const string& s)
{
int n = int(s.size()) - 1;
vector<int> res(n);
for(int i = 0; i < n; i++)
if(s[i] <= s[i + 1])
res[i] = 0;
else
res[i] = 1;
return res;
}
vector<int> prefix_sum(const vector<int>& s)
{
int n = s.size();
vector<int> p(n + 1);
for(int i = 0; i < n; i++)
p[i + 1] = p[i] + s[i];
return p;
}
int naiveLCP(const string& s, const string& t)
{
int ans = 0;
int n = s.size();
int m = t.size();
while(ans < n && ans < m && s[ans] == t[ans])
ans++;
return ans;
}
vector<vector<int>> build_table(const vector<int>& a)
{
int n = a.size();
vector<vector<int>> table(LN, vector<int>(n));
for(int i = 0; i < n; i++)
table[0][i] = a[i];
for(int i = 1; i < LN; i++)
for(int j = 0; j < n; j++)
if(j + (1 << (i - 1)) < n)
table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
else
table[i][j] = table[i - 1][j];
return table;
}
struct LCP
{
vector<int> idx;
vector<vector<int>> table;
int query_inner(int x, int y)
{
if(x > y) swap(x, y);
int len = y - x;
int d = pw2[len];
return min(table[d][x], table[d][y - (1 << d)]);
}
int query(int x, int y)
{
return query_inner(idx[x], idx[y]);
}
LCP() {};
LCP(vector<string> s)
{
int n = s.size();
vector<pair<string, int>> t;
for(int i = 0; i < n; i++)
{
t.push_back(make_pair(s[i], i));
}
sort(t.begin(), t.end());
idx.resize(n);
for(int i = 0; i < n; i++)
{
idx[t[i].second] = i;
}
vector<int> LCPs;
for(int i = 0; i < n - 1; i++)
LCPs.push_back(naiveLCP(t[i].first, t[i + 1].first));
table = build_table(LCPs);
};
};
const int T = int(2e7);
map<char, int> nxt[T];
int cur = 1;
int root = 0;
int cnt[T];
void clear_trie()
{
root = cur++;
}
int go(int x, char c)
{
if(!nxt[x].count(c))
nxt[x][c] = cur++;
return nxt[x][c];
}
void add(int v, const string& s, int l, int r, int n, bool sw, const vector<int>& ps)
{
if(sw && l + r < n - 1 && ps[n - r - 1] == ps[l])
{
cnt[v]++;
}
if(sw)
{
if(l + r < n - 1)
add(go(v, s[n - r - 1]), s, l, r + 1, n, sw, ps);
}
else
{
add(go(v, '$'), s, l, r, n, true, ps);
if(l < n - 1)
add(go(v, s[l]), s, l + 1, r, n, sw, ps);
}
}
int calc(int v, const string& s, int l, int r, int n, bool sw, const vector<vector<int>>& good)
{
int ans = 0;
if(sw && l + r < n - 1 && good[l][r])
{
ans = cnt[v];
}
if(sw)
{
if(l + r < n)
ans += calc(go(v, s[n - r - 1]), s, l, r + 1, n, sw, good);
}
else
{
ans += calc(go(v, '$'), s, l, r, n, true, good);
if(l < n)
ans += calc(go(v, s[l]), s, l + 1, r, n, sw, good);
}
return ans;
}
long long solve_short(vector<string> s, int n)
{
long long ans = 0;
clear_trie();
sort(s.begin(), s.end());
for(int i = 0; i < n; i++)
{
string cur = s[i];
int len = cur.size();
vector<vector<int>> good(len + 1, vector<int>(len + 1));
for(int l = 0; l < len; l++)
{
set<char> q;
for(int r = l; r < len; r++)
{
q.insert(cur[r]);
if(cur[l] != *q.begin() && cur[r] != *q.rbegin())
{
good[l][len - r - 1] = 1;
}
}
}
vector<int> p = prefix_sum(sorted_segments(cur));
add(root, cur, 0, 0, len, false, p);
ans += calc(root, cur, 0, 0, len, false, good);
}
ans = n * 1ll * (n - 1) - ans;
return ans;
}
long long solve_long(vector<string> s, int n)
{
int len = s[0].size();
sort(s.begin(), s.end());
vector<string> t = s;
for(int i = 0; i < n; i++)
reverse(t[i].begin(), t[i].end());
LCP ls(s);
LCP lt(t);
long long ans = 0;
for(int i = 0; i < n; i++)
{
vector<int> aux = prefix_sum(sorted_segments(s[i]));
for(int j = i + 1; j < n; j++)
{
int lf = ls.query(i, j);
int rg = lt.query(i, j);
if(aux[len - rg - 1] - aux[lf] == 0)
ans++;
else
ans += 2;
}
}
return ans;
}
long long solve_class(vector<string> s, int n)
{
if(n <= K)
return solve_long(s, n);
else
return solve_short(s, n);
}
vector<int> get_class(string s)
{
vector<int> c(26);
for(auto x : s) c[x - 'a']++;
return c;
}
int main()
{
pw2[1] = 0;
for(int i = 2; i < (1 << LN); i++)
pw2[i] = pw2[i >> 1] + 1;
int n;
cin >> n;
vector<string> s(n);
for(int i = 0; i < n; i++)
cin >> s[i];
long long ans = 0;
map<vector<int>, vector<string>> classes;
for(int i = 0; i < n; i++)
classes[get_class(s[i])].push_back(s[i]);
int cnt = 0;
for(auto x : classes)
{
ans += solve_class(x.second, x.second.size());
ans += cnt * 1337ll * x.second.size();
cnt += x.second.size();
}
cout << ans << endl;
}
```

The round was really educational. thanks!

Solution to problem c was much simpler . Just use basic DP . Here's my solution ->

Can you explain the logic behind this Solution?

Without DP Time Complexity — O(N) Space Complexity — O(1)

int main() {

}

Auxiliary Space, not Space Complexity.

difference ?

Google.

Logic Please

Somehow I understood this task "the number of beautiful substrings of the string s" as follows: For string 0101, the beautiful substrings are: 0 1 01 10 010 101 0101 i.e. 7 substrings

It turns out that the solution expects 10 for this example: 0 1 0 1 01 10 01 010 101 0101 i.e. 10 substrings (with duplicates at different indexes)

Can you explain the logic behind this solution?

i was having same logic ,but dont know how to implement , really nice implementation.

nice! very short and simple solution

That's some gg stuff

simple and beautiful code!

I am trying to solve the problem C with dp ,but unable to solve. Can you explain how you came up with the solution. What is the logic for dp relation?

The logic for dp is such

If character at ith index is '0' you can't do anything but take transition from previous index's '1' that is dp[i-1][1] where dp[i][j] stores the number of valid substrings if the ith index ends with j (0 or 1).

Similarly the same has to be done if the ith index is '1'

Now if the ith index is '?' you would want the the alternating string ending at '?' to be as huge as possible therefore u pick dp[i — 1][0] or dp[i — 1][1] depending which is bigger.

That's what I call simpler :)

Why is this downvoted so much? the solution is much simpler than the official one.

Awesome approach

why so many negative upvotes ../

why so many down votes! It's such a good soln.

I accidentally solved a harder version of problem E where you're given not a path from $$$v_i$$$ to the root in the second query type but ANY vertical path. I think it might be fun for you to solve if you're interested.

UPD: Oh yeah, btw, I can modify this solution a little bit so that it works not only for vertical but for arbitrary paths.

Can u provide the link to the referred problem?

There's no such problem. I was just solving problem E from this contest and forgot that the path goes from the root.

I think SecondThread also did something similar by bashing it with LCT with path aggregates: https://codeforces.com/contest/1535/submission/118434117

He explains it in https://youtu.be/1x4mkj1kE1E?t=7051

Omg. LCT. No, my submission 118419626 is just a little bit harder than the one from the editorial. Yeah, I also thought about LCA but it's too much for problem E I guess.

I Loved problem D, the first time I got a chance to use Segment tree in a CF contest and the editorial also good. Thanks to the team behind the contest.

You already commented the same before ¯_(ツ)_/¯

Both posts are regarding the same contest and the same problem so I think it's fair to post the same comment.

Thanks for such an interesting contest! I really enjoyed the problems, especially B and C. Actually, I think problem A was a little bit too easy in comparison with the last contest. I hope the next contest will be more and more exciting! :)

I have a solution to problem F in $$$O (n * m * log n)$$$ (where $$$m$$$ is the length of the string). Similarly to the author's, we split strings into equivalence classes. We only need to quickly calculate the number of pairs of strings with a distance equal to 1. Divide each string into the minimum number of blocks so that the characters in each block are sorted. Note that for the string $$$s[i]$$$ this partition is unique and is specified only by those positions $$$j$$$, where $$$s[i][j] < s[i][j - 1]$$$. Suppose we have two strings $$$s1 < s2$$$. Note that we can sort in $$$s2$$$ only a segment nested in some block in $$$s1$$$. Then, in fact, we can expand this segment to the size of the block. That is, for each block $$$[l, r]$$$ in $$$s1$$$, we need to find the number of such $$$s2$$$ so that if we sort the segment $$$[l, r]$$$ in $$$s2$$$, then $$$s2$$$ becomes equal to $$$s1$$$. Note that in this case $$$s1[:l-1]$$$ = $$$s2[:l-1]$$$ and $$$s1[r + 1:]$$$ = $$$s2[r + 1:]$$$. Let's iterate over $$$l$$$ for the equivalence class and split into new equivalence classes by prefixes of length $$$l$$$. Now, note that if some block $$$[l, r]$$$ of string $$$s[i]$$$ begins in $$$l$$$, then we need to find out the number of such $$$s[j] > s[i]$$$ in the new equivalence class $$$s[i]$$$ that the length of the common suffix $$$s[i]$$$ and $$$s[j]$$$ $$$> = m - r$$$. This is easily done by simply sorting all the reversed strings and doing a binsearch using a sparse table on the lcp array. Further, going through the strings in descending order, add 1 to their position in the new array, for beginning of the block find out the amount on the segment using any convenient data structure.

My submission — 118431979.

P.S. If you don't understand something, ask questions. Sometimes even I don't understand myself.

"Let's iterate over l for the equivalence class and split into new equivalence classes by prefixes of length l"

How do you split into new equivalence classes ?

Strings $$$s1$$$ and $$$s2$$$ in the same new class, if the length of their common prefix is at least $$$l$$$ and their multisets of characters are the same. Therefore, when incrementing $$$l$$$ by 1, you only need to create subclasses using the character at position $$$l + 1$$$ (numbering from 1).

Can you explain about

`vector<vector<int>> to(m, vector<int> (sz))`

in your code?$$$to[j][i]$$$ — the number of the equivalence class of $$$s[i]$$$, if $$$l$$$ (which I described earlier) is equal to $$$j$$$. It is not hard to see that the equivalence classes form segments in the sorted array of strings.

I wonder what this initiation means. Isn't this -2 out of bound?

lol really. You are right, this is out of bound. :) I was lucky that there was no RE.

I think I found an easier solution to problem B (I am not saying it is faster — just easier). There's simply no need to move the even numbers to the beginning, just check for each pair (i < j) if

`__gcd(a[i], 2 * a[j]) > 1`

or`__gcd(a[j], 2 * a[i] > 1`

.Here is my submission: 118428074.

editorial for c is more complicated to understand then the solution itself

simple (not) solution for C, no Dp, just string compression and index checking and then straight up calculating, also if an array of len n is beautiful then all its substrings will be beautiful, and an array of len n will have n*(n+1) substrings, I have used this concept.solutionYour solution is so complex to understand -_-

Can someone please explain the solution to B in python ?

Bro just think about this, put all positive number in the beginning , so for each positive number you’ll have n-i (where i is it’s one based index ) pairs , then put all odd numbers in sorted order and manually calculate the pairs using two for loops, simple as that. Try to prove why this is the best ordering yourself ;)

Main idea behind this code is that when we calling gcd(a,2*b) then case when "a" is odd we get large number of solution as gcd()<=1 which we don't want. So we want STOP this type of case gcd(odd,2*b). so that is why if we make array like this even,even, odd... in which all odd elements are at last. We get our solution. Order of element doesn't matter.

Note: For learning purpose after you code refer solution of this profile he use such elegant code in python. You definite like his work...

Happy coding.

my submission = https://codeforces.com/contest/1535/submission/118565398

pls help me. I can't find the reason of runtime error

try to rewrite your cmp function like this Link

this is a common RTE mistake you can search on CF,some blogs has been written about this

thank you

MikeMirzayanov, I just got a message that my solution Kal-El/118413234 for 1535C coincides with low_profile/118412998,K0000/118413793, shakeitbaby/118414205, O_BhosDiwale_ChaCha/118414232, madarakaguya1234/118414304, XENOX_GRIX/118417732, codeforcesalt11/118418351, yash_agarl_/118423400

I think this is either coincidence(I used a simple 2 pointer approach for it) or the people mentioned above are indulging in cheating. I have never indulged in leaking my solution or copying someone else code (you can have a look at my profile to confirm it), and looking at the timestamps it is clear that I did not copy paste someone else code.

If u look at template of my other submissions on Codeforces it is similar to my submission for 1535C but for the people mentioned above their code style is not same as their submission for 1535C. I do not know how they got access to my code or was it just a mere coincidence.

I sincerely participated in the contest and it is a humble request to you to not skip my submissions for the contest.

Can anyone tell why my solution for problem B giving TLE

ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a % b); }

int main(){

return 0;

}

Store

`v.size()`

in some variable and then pass it into loops.Thanks but then how did it passed the pretest-1

But why it does work? Any reason ?

[Refer to this](https://codeforces.com/blog/entry/44795#:~:text=size()%2D1%3B,alias%20for%20unsigned%20long%20int%20.)

Thanks but then how did it passed the pretest-1

Pretest-1 doesn't have a case where the number of odd numbers is zero.

`for(ll i=0;i<v.size()-1;i++){`

Since v.size() is unsigned that loop can run very long.

What data structure has the model solution used in the solve_short() function in the last problem? Is it Aho Corasick or something similar?

Can Anyone explain the dp solution for problem C in a little more detailed manner .

my submission = https://codeforces.com/contest/1535/submission/118565398

pls help me. I can't find the reason of runtime error

Hello guys. I have a little question. Does this python code equivalent to this C++ code?

Python:

C++:

Can somebody explain how sort function is written in the code of question B?

For

std::sort(first,last,comparatorFunction)this is the syntax of sort function for more you can refer to this Link.In editorial 3rd parameter in sort function is

lambda expressionwhich might confused you I guess. You can refer this Link.ok

If

`o`

is empty, then`o.size() - 1`

will evaluate to 2^64 − 1 since`size_t`

is unsigned.For Problem D: Can someone tell me why i am getting TLE in tc 11?

code : 118688525

Trying to implement something "smart" in F I accidentally got Accepted with "stupid" $$$O(n*n)$$$ (or even $$$O(n*n*m)$$$) solution. After removing all unnecessary trash it has only several lines of code: 118716718

In particular it uses the following code:

where $$$n$$$ — the size of a current equivalence class.

It seems C++ is too fast :) and, probably, the tests do not cover the worst case for this solution. Also please note, that all string are different, so the maximum size of an equivalence class is $$$200000/8 = 25000$$$.

Problem C: Are tutorial and solution the same?

In python 3.8 i used my own implementation for gcd (mod euler) and it got time limit exceeded using the math.gcd method it got accepted.

Have you used Euclid's algorithm?

yes

Can someone please explain this solution in brief? https://codeforces.com/contest/1535/submission/119788018

In problem 1535C - Нестабильная строка Can anyone explain is it necessary for a beautiful string to contain the character

`?`

? Also how does`0?10`

has 8 beautiful substrings ?0, ?, 1, 0, 0?, ?1, 10, ?10 are the 8 beautiful substrings in the first sample test case

And no, it is not necessary for a beautiful string to contain the '?' character. A better description of a beautiful string in my opinion would be closer to something like "The string is already unstable or can be made unstable through switching all '?' characters to '1's or '0's".

So This is how I approached 1535C - Нестабильная строка : So there are two kinds of unstable string ,

`101010...`

(let's call these type of string as`odd unstable string`

(because`1`

's are at odd positions ) ) and`010101....`

(let's call these type of string as`even unstable string`

). Now let's define`odd beautiful string`

as a string that can be converted to a`odd unstable string`

after replacing all the`?`

with`0`

or`1`

and similarly we define`even beautiful string`

. now, some (possibly all) substring of a given string is either a`odd beautiful string`

or a`even beautiful string`

. now let's consider a potential`odd beautiful string`

, we call those index as`bad index`

that break the`odd beautifulness`

of the string (i.e 0 at odd position and 1 at even position ) and the index that are not bad index are called`good index`

(i.e they conserve the`odd beautifulness`

property i.e 0 at even position and 1 at odd position ) .Notice that any substring of a beautiful substring is also a beautiful substring. now, we can see that our answer will be the sum of number of substring of strings formed from contiguous good index . Hence take all such substrings for both contiguous odd good index and contiguous even good index. in this process, some substring are getting counted twice namely, the substring consisting of only contiguous`?`

. Hence we eliminate all such substring.Code for more clarity.

Also sorry, if you found this explanation a little harder to understand.

for question B, i got TLE for https://codeforces.com/problemset/submission/1535/126669391 this submission but the same was done afterwards, it got accepted, https://codeforces.com/problemset/submission/1535/126670783 Can anyone explain the behavior of Codeforces here??

Why can't tutorial be in simple algorithmic form please? Tutorials explanation are very difficult to be converted to code.

Sir in Question 2 Array Reordering what is the expected time complexity