Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int n;
cin >> n;
forn(i, n) {
string s;
cin >> s;
if (set<char>(s.begin(), s.end()).size() == s.length()
&& *max_element(s.begin(), s.end()) == char(*min_element(s.begin(), s.end()) + (s.length() - 1)))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
```

1144B - Parity Alternated Deletions

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
int sum = 0;
vector<int> even, odd;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
sum += x;
if (x & 1) odd.push_back(x);
else even.push_back(x);
}
sort(odd.rbegin(), odd.rend());
sort(even.rbegin(), even.rend());
int k = min(odd.size(), even.size());
int rem = sum;
rem -= accumulate(odd.begin(), odd.begin() + k, 0);
rem -= accumulate(even.begin(), even.begin() + k, 0);
if (int(odd.size()) > k) {
rem -= odd[k];
}
if (int(even.size()) > k) {
rem -= even[k];
}
cout << rem << endl;
return 0;
}
```

1144C - Two Shuffled Sequences

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> cnt(200 * 1000 + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
if (cnt[x] > 2) {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl << count(cnt.begin(), cnt.end(), 2) << endl;
for (int i = 0; i <= 200 * 1000; ++i) {
if (cnt[i] == 2) {
cout << i << " ";
--cnt[i];
}
}
cout << endl << count(cnt.begin(), cnt.end(), 1) << endl;
for (int i = 200 * 1000; i >= 0; --i) {
if (cnt[i] == 1) {
cout << i << " ";
--cnt[i];
}
}
cout << endl;
assert(count(cnt.begin(), cnt.end(), 0) == 200 * 1000 + 1);
return 0;
}
```

Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n), cnt(200 * 1000 + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
++cnt[a[i]];
}
int val = max_element(cnt.begin(), cnt.end()) - cnt.begin();
int pos = find(a.begin(), a.end(), val) - a.begin();
cout << n - cnt[val] << endl;
int siz = 0;
for (int i = pos - 1; i >= 0; --i) {
cout << 1 + (a[i] > a[i + 1]) << " " << i + 1 << " " << i + 2 << " " << endl;
a[i] = a[i + 1];
++siz;
}
for (int i = 0; i < n - 1; ++i) {
if (a[i + 1] != val) {
assert(a[i] == val);
cout << 1 + (a[i + 1] > a[i]) << " " << i + 2 << " " << i + 1 << " " << endl;
a[i + 1] = a[i];
++siz;
}
}
assert(siz == n - cnt[val]);
return 0;
}
```

Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
vector<int> get(const string &s) {
vector<int> res(s.size() + 1);
for (int i = 0; i < int(s.size()); ++i) {
res[i + 1] = s[i] - 'a';
}
return res;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int k;
string s, t;
cin >> k >> s >> t;
vector<int> a = get(s), b = get(t);
for (int i = k; i >= 0; --i) {
a[i] += b[i];
if (i) {
a[i - 1] += a[i] / 26;
a[i] %= 26;
}
}
for (int i = 0; i <= k; ++i) {
int rem = a[i] % 2;
a[i] /= 2;
if (i + 1 <= k) {
a[i + 1] += rem * 26;
} else {
assert(rem == 0);
}
}
for (int i = 1; i <= k; ++i) {
cout << char('a' + a[i]);
}
cout << endl;
return 0;
}
```

1144F - Graph Without Long Directed Paths

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 11;
int n, m;
vector<int> g[N];
vector<pair<int, int>> e;
bool bipartite;
vector<int> color;
void dfs(int v, int c) {
color[v] = c;
for (auto to : g[v]) {
if (color[to] == -1) {
dfs(to, c ^ 1);
} else {
if (color[to] == color[v]) {
bipartite = false;
}
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
e.push_back(make_pair(x, y));
}
bipartite = true;
color = vector<int>(n, -1);
dfs(0, 0);
if (!bipartite) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = 0; i < m; ++i) {
cout << (color[e[i].first] < color[e[i].second]);
}
cout << endl;
return 0;
}
```

There is different solution for the problem, it is pretty interesting! Thanks, Roundgod!

Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<int>> dp(n, vector<int>({-INF, INF}));
vector<vector<int>> p(n, vector<int>(2, -1));
dp[0][0] = INF;
dp[0][1] = -INF;
for (int i = 1; i < n; ++i) {
{
if (a[i] > a[i - 1] && dp[i][0] < dp[i - 1][0]) {
dp[i][0] = dp[i - 1][0];
p[i][0] = 0;
}
if (a[i] < dp[i - 1][0] && dp[i][1] > a[i - 1]) {
dp[i][1] = a[i - 1];
p[i][1] = 0;
}
}
{
if (a[i] < a[i - 1] && dp[i][1] > dp[i - 1][1]) {
dp[i][1] = dp[i - 1][1];
p[i][1] = 1;
}
if (a[i] > dp[i - 1][1] && dp[i][0] < a[i - 1]) {
dp[i][0] = a[i - 1];
p[i][0] = 1;
}
}
}
int pos = -1;
if (dp[n - 1][0] != -INF) {
pos = 0;
}
if (dp[n - 1][1] != INF) {
pos = 1;
}
if (pos == -1) {
cout << "NO" << endl;
return 0;
}
vector<int> inInc(n);
for (int i = n - 1; i >= 0; --i) {
if (pos == 0) {
inInc[i] = 1;
}
pos = p[i][pos];
}
cout << "YES" << endl;
for (int i = 0; i < n; ++i) {
cout << !inInc[i] << " ";
}
cout << endl;
return 0;
}
```

thank you

G Tutorial is not available?

Fixed now, sorry

Thanks For Fast Editorials <3

In Problem

G, I'm getting WA on test 12. Please help me out. 52149636Why is problem D tagged as dfs and similar?

Bfs solution

Interesting idea on E, very cool problem!

Solving E problem using Python gave TLE, don't know why. I stored the Number as int(base 26). Shouldn't it work?

Nobody can see your submitted solutions. You're probably getting TLE because the operations you are doing on the numbers are too slow.

No problem, I think I got the Reason why it is giving TLE.

I don't understand E's editorial,can anyone please explain?What are we doing? I thought of seeing the string as base 26,so we can convert it into decimal and take the mean. For example: az = 26^0*25 + 26^1*0 = 25, bf = 26^0*5 + 26^1*1 = 31 now taking the mean we get 28,converting into base 26 we get 12 (26^0*2+26^1*1 = 28),which is bc. But for large string lengths we may have to do 26^100000,so I thought it is not feasible. What are we doing in this editorial?

You misunderstood the meaning.We can represent the string to a number, with base 26. And then we can figure out that if string s is lexicographically smaller than t, the "number" which s represents is smaller than t's "number". So what we need to calculate is a "number" which is the median of [s's number, t's number]. We can Easily calculate it by writing "BigIntegar", to storing big number and doing operations. Here's my Code Link: Here

Thanks a lot for replying,in author's code,I understand the string is stored as int with base 26,but what are the 2 operations done? Is he adding the 2 vectors?

2 vectors represents 2 BigInt(base 26). so, now he add the BigInt and then divide it by 2. (Same as we did addition and division with paper and pencil in childhood :) )

Then print the vector as characters.

This is a real Div.3 :)

Another solution to G by considering whether the max.element in the array is in the decreasing or increasing subsequence:52159992

anyone please help. In problem F, why my code give me Runtime Error on test 15?.

My Submission: 52160039

You are reading n edges instead of m?

a lots of thanks man. i span 2-3 hours with this problem ..

Runtime error in F: can someone help me debug: https://codeforces.com/contest/1144/submission/52208937

maybe it's the for-loop for finding the largest degree

you iterate it for i = [0, m), while vector "graph" has the size of n. RTE when m > n.

Thanks! That was it.

for E:someone plzz explain how division by 2 is done in 26 base

for (int i = 0; i <= k; ++i)

{

}

If the digit in the pos[i] is not divisible by 2, you can just pass a one to the next digit, a 1 from $$$1*26^i$$$ is equivalent to 26 in $$$26^\left( i-1 \right)$$$, if it is divisible by 2 then you just need to divide it by 2

problem ID:1144F

problem F is also done by BFS

problem F code(happy coding)

Can I solve E using big integer?

You will end up with TLE if you try to actually find the values in base 26. Instead try to understand how you can divide the representation in base 26 by 2. In such a case you will not need BigInteger.

for problem g is this correct approach? let say i have two array X(increasing),Y(decreasing) and A is Merge(X,Y). Find the longest increasing sequence of A this sequence will contain X and atmost one element of Y and after removing that element from Y Y will still remain decreasing.

Why is this solution for E giving TLE? https://codeforces.com/contest/1144/submission/52223063

You are doing ans = ans + (char)(median[i] + 'a'); This takes more time as compared to ans+=(char)(median[i] + 'a'); I am not sure of its reason. But i too have faced similar issues before.

Can someone explain why this removes TLE?

Problem E is very badly explained.

there is a another way to solve problem G

first we found the LIS of the array and then there is a fact : if we can split the given sequence a into one increasing sequence and one decreasing sequence then at most one of the elements of the LIS could not appear in x ( x is the increasing sequence ) otherwise in the y ( the decreasing sequence ) we have two numbers A , B which a[A] < a[B] and A < B and its impossible so if we fix which index i is not gonna appear in x we can solve the problem

In problem E, why is it only allowed to do a[i] %= 26 when i > 0?

For this test case, for example:

6

nijfvj

tvqhwp

The sum in the base 26 is: 33 3 25 13 17 24

Why is it allowed to have this "33" in the first position?

In my program，its allow a[i] % 26 in i = 0

but if u do that, you need to deal with leading zeros，it's a little bit more trouble, but it doesn't really matter.

For example

33 3 25 13 17 24 -> 1 7 3 25 13 17 24

then u div 2

0 16 14 25 19 21 25

now,u need cheak the zero,if u dont do that ,the answer will be an extra a

Thanks for these tutorials. But I do not know how to solve the problem G with Greedy. So maybe I need help. QAQ.

Help me! I dont understand print problem F in tutorial: cout << (color[e[i].first] < color[e[i].second]); ???????????? please

when you split vertices in to two part . you want obtain direct of edges such that every edge in part one direct to the second pare or you can direct all edges from second part to the first part . and we know that every edges has two end point such that one of them from first and one of them from second (because its bipartite) so if color[first endpoint] < color[second endpoint] that means color[first endpoint] = 0 so that condition return 1 and otherwise return 0

^_^ yeah, thanks U somuch

In editorial 'G',what is the meaning of 'maximum possible minimal'?

minimal element from the sequence is a const value , this const value be maximum as possible means .

Somebody please tell me why this submission 52323233 works but this submission 52321524 does not ??

The only difference in both the codes is that in accepted one, I've accepted the input as strings while in wrong answer I've accepted them in character arrays

Who can help me for my submission on F: My submission for F I can pass when n=2e5 and m=2e5,but it will TLE on test 12(it's n=1e5 and m=2e5) and when it TLE,it run 10000~20000 edges. I think my code is an solution O(mlog(m)) Thank you!

For Problem E

First each letter in string is converted to corresponding number, ie a = 0 , b = 1 , c= 2....(This is base 26 representation) and is stored in two vectors a and b.

After that to add these vectors we can't do it normaly because it is in base-26 and not in base-10(decimal).

So refer this video for addition of numbers which are not of base-10(decimal) -> https://www.youtube.com/watch?v=O-CwMsS0eNw

So when addition of two digits becomes more than 26 we add 1(carry) to next digit and mod 26 with current digit(equivalent to number — 26).

The division part is explained by Sam in another comment.