Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
for _ in range(int(input())):
n = int(input())
s = input()
for i in range(n - 1):
if s[i] != s[i + 1]:
print(i + 1, i + 2)
break
else:
print(-1, -1)
```

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 t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
vector<int> id;
for (int i = 0; i < n; ++i) if (s[i] == '2')
id.push_back(i);
int k = id.size();
if (k == 1 || k == 2) {
cout << "NO\n";
continue;
}
vector<string> t(n, string(n, '='));
for (int i = 0; i < n; ++i) t[i][i] = 'X';
for (int i = 0; i < k; ++i) {
int x = id[i], y = id[(i + 1) % k];
t[x][y] = '+';
t[y][x] = '-';
}
cout << "YES\n";
for (int i = 0; i < n; ++i) cout << t[i] << '\n';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int mx = *max_element(a.begin(), a.end());
int cmx = count(a.begin(), a.end(), mx);
int k = count(a.begin(), a.end(), mx - 1);
int ans = 1, sub = 1;
for (long long i = 1; i <= n; ++i) {
ans = ans * i % MOD;
if (i != k + 1) sub = sub * i % MOD;
}
if (cmx == 1) ans = (ans - sub + MOD) % MOD;
cout << ans << '\n';
}
}
```

Idea: BledDest

**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 all(a) (a).begin(), (a).end()
#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) {
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, k;
vector<int> x, y;
vector<pt> ps;
inline bool read() {
if(!(cin >> n >> m >> k))
return false;
x.resize(n);
fore (i, 0, n)
cin >> x[i];
y.resize(m);
fore (i, 0, m)
cin >> y[i];
ps.resize(k);
fore (i, 0, k)
cin >> ps[i].x >> ps[i].y;
return true;
}
inline void solve() {
li ans = 0;
fore (_i, 0, 2) {
vector<int> cntY(m, 0);
sort(all(ps));
vector<pt> bord(k);
int u = 0;
while (u < k) {
int v = u;
while (v < k && ps[v].x == ps[u].x)
v++;
fore (i, u, v) {
int r = int(lower_bound(all(y), ps[i].y) - y.begin());
int l = r;
if (y[l] > ps[i].y)
l--;
assert(y[l] <= ps[i].y && ps[i].y <= y[r]);
bord[i] = {l, r};
}
fore (i, u, v) if (bord[i].x < bord[i].y)
ans += cntY[bord[i].x];
fore (i, u, v) if (bord[i].x < bord[i].y)
cntY[bord[i].x]++;
u = v;
}
fore (i, 0, k)
swap(ps[i].x, ps[i].y);
swap(x, y);
swap(n, m);
}
cout << ans << endl;
}
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);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) 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;
}
vector<int> evaluate(int n, int choice_mask)
{
int cur_place = n / 2 + 1;
int cur_bit = n - 2;
vector<int> p(n);
vector<int> c(n);
for(int i = 0; i < n; i++)
c[i] = i;
while(c.size() != 1)
{
vector<int> nc;
for(int i = 0; i < c.size(); i += 2)
{
if(choice_mask & (1 << cur_bit))
{
p[c[i]] = cur_place;
nc.push_back(c[i + 1]);
}
else
{
p[c[i + 1]] = cur_place;
nc.push_back(c[i]);
}
cur_bit--;
}
c = nc;
cur_place /= 2;
cur_place++;
}
p[c[0]] = 1;
return p;
}
vector<int> adjust(int n, vector<int> p, bool winning)
{
for(int i = 0; i < n; i++)
{
if(p[i] == 1)
{
if(!winning) p[i]++;
}
else
p[i] = p[i] * 2 - 1;
}
return p;
}
int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0)
{
if(partial)
p = adjust(n, p, winning);
int res = 0;
for(int i = 0; i < n; i++)
res = add(res, mul(add(i + 1, shift), binpow(A, p[i])));
return res;
}
int main()
{
int k, A, h;
cin >> k >> A >> h;
if(k <= 4)
{
for(int i = 0; i < (1 << ((1 << k) - 1)); i++)
{
vector<int> p = evaluate(1 << k, i);
if(get_hash(1 << k, p, A) == h)
{
for(auto x : p) cout << x << " ";
cout << endl;
return 0;
}
}
}
else
{
int mask_left = -1;
int mask_right = -1;
bool left_win = false;
for(int c = 0; c < 2; c++)
{
map<int, int> left_map;
for(int i = 0; i < (1 << 16); i++)
{
vector<int> p = evaluate(16, i);
int left_hash = get_hash(16, p, A, true, c == 0, 0);
left_map[left_hash] = i;
}
for(int i = 0; i < (1 << 16); i++)
{
vector<int> p = evaluate(16, i);
int right_hash = get_hash(16, p, A, true, c == 1, 16);
int left_hash = add(h, MOD - right_hash);
if(left_map.count(left_hash))
{
mask_left = left_map[left_hash];
mask_right = i;
left_win = (c == 0);
}
}
}
if(mask_left != -1)
{
vector<int> ans_left = evaluate(16, mask_left);
vector<int> ans_right = evaluate(16, mask_right);
ans_left = adjust(16, ans_left, left_win);
ans_right = adjust(16, ans_right, !left_win);
for(auto x : ans_left)
cout << x << " ";
for(auto x : ans_right)
cout << x << " ";
return 0;
}
}
cout << -1 << endl;
return 0;
}
```

1569F - Palindromic Hamiltonian Path

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;
vector<vector<char>> g;
map<long long, bool> dp;
void brute(int n, vector<int> &p){
int x = find(p.begin(), p.end(), -1) - p.begin();
if (x == int(p.size())){
vector<vector<char>> dp2(1 << n, vector<char>(n));
vector<int> pos1(n), pos2(n);
forn(i, p.size()){
pos1[p[i]] = pos2[p[i]];
pos2[p[i]] = i;
}
forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){
forn(j, n) if (!((mask >> j) & 1)){
dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
}
}
forn(i, n) if (dp2[(1 << n) - 1][i]){
long long num = 0;
for (int x : p) num = num * 6 + x;
dp[num] = true;
break;
}
return;
}
for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
p[x] = p[y] = n;
brute(n + 1, p);
p[x] = p[y] = -1;
}
}
bool dfs(vector<int> p){
vector<int> used(int(p.size()), -1);
int cnt = 0;
forn(i, p.size()) if (used[p[i]] == -1)
used[p[i]] = cnt++;
long long num = 0;
for (int& x : p){
x = used[x];
num = num * 6 + x;
}
if (dp.count(num)) return dp[num];
bool res = false;
vector<int> cur(cnt);
forn(i, p.size()) ++cur[p[i]];
forn(i, p.size()) if (cur[p[i]] > 2){
int x = p[i];
for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){
p[i] = p[j] = cnt;
if (dfs(p)){
res = true;
break;
}
p[i] = p[j] = x;
}
break;
}
return dp[num] = res;
}
void brute2(int n, vector<int> &p){
int x = find(p.begin(), p.end(), -1) - p.begin();
if (x == int(p.size())){
dfs(p);
return;
}
forn(i, n + 1){
for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
p[x] = p[y] = i;
brute2(max(n, i + 1), p);
p[x] = p[y] = -1;
}
}
}
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
g.resize(n, vector<char>(n));
forn(_, m){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v][u] = g[u][v] = 1;
}
vector<int> cur(n, -1);
brute(0, cur);
brute2(0, cur);
vector<long long> fact(k + 1);
fact[0] = 1;
for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
long long ans = 0;
for (auto it : dp) if (it.second){
long long num = it.first;
long long mx = 1;
while (num){
mx = max(mx, num % 6 + 1);
num /= 6;
}
if (mx <= k){
ans += fact[k] / fact[k - mx];
}
}
printf("%lld\n", ans);
return 0;
}
```

Fastest editorial I've seen

Stop disliking him.

nice contest =))

Lesson learned: Don't use segment trees unless required.

(My segment tree implementation for D gave TLE on system testing.)

Interesting. I used segment trees and maps as well, and the highest runtime was ~1 second.

My submission 128269298

code and explanation for problem DSpoilerJust separate the points into two parts one where the x of the point matches with any of the x of vertical roads and other part where the y of the point matches with the y of any horizontal road. these two parts may or may not be disjoint as it is also possible that point's x as well as y matches with any vertical and horizontal road then this point will be the part of both parts.

Now solve the answers for both the parts separately ->

for 1st part Sort it using a comparater which sorts first according to y and then according to x. Now just iterate one by one on the points since the points are sorted using the above comparater so the points will be divided into groups which lie on the same horizontal line(same y) and this group is also sorted according to x also. Now we can see that the vertical roads divides the x axis into some segments. (x0,x1) (x1,x2) (x2,x3) ........

for calculating the answer we will maintain one array f of size (n-1) where ith element represents the number of points that lie in the ith segment and whose y is also less than the current y(on which we are currently at in the iteration).

f[i]=number of points which lie in the segment (x[i],x[i+1]) end points not included.

for finding the segment-number of a point (a,b) we can easily find it using binary search(using lower_bound in c++)

now let us assume we are at a point (a,b) so to find out the pairs that this point will make with other points that are already visited in the iteration we can make use of the array f.

first we find the segment to which the point (a,b) lies and then the bad pairs which it makes is equal to f[segment-number]. because f[segment-number] stores the number of points that lie in that segment in the previous horizontal line (y<b). This can be easily observed that bad pairs are the points which strictly lie inside same segment(end points not included) and which do not lie on the same line.

Now when we move to the next horizontal line (y>b) then we need to add the point (a,b) to its respective segment(increment value of f[segment-number]) so that it can contribute the points which lie on the horizontal line above it.

what we can do is we can maintain a cnt variable which stores the number of points which lie on the same horizontal line and in the same segment of x axis.When we move to next segment then we can just update the value of f[prev-segment-number]+=cnt.

for 2nd part-

Sort it using a comparater which sorts first according to x and then according to y. It's exactly same the difference is just the change of axis now we will iterate vertical line by line and in increasing order of x.Now the y axis is divided into segments.

Link to my code- https://codeforces.com/contest/1569/submission/128325617

I am facing some difficulty in understanding the equation in Problem C: $$$A_n^{n-k-1} = \frac{n!}{(k+1)!}$$$ What is $$$A$$$ here and how did we get $$$\frac{n!}{(k+1)!}$$$?

$$$A_x^y$$$ is the number of

orderedways to choose exactly $$$y$$$ different objects from $$$x$$$. So, it's like a binomial coefficient $$${x}\choose{y}$$$, but with also considering the order in which we choose the object. Hence the formula for $$$A_x^y$$$ is $$${{x}\choose{y}} \cdot y! = \frac{x!}{(x-y)!}$$$: there are $$${x}\choose{y}$$$ ways to choose exactly $$$y$$$ objects out of $$$x$$$, and $$$y!$$$ ways to order them.Okay, so it's a permutation. Thanks for your help ^_^ !

PLEASE DISREGARD THIS COMMENT.

Hi, how do you go from $$$A_n^{n-k-1}$$$ to this $$$\frac{n!}{(k+1)!}$$$? I would've thought the denominator to be (n-k-1)!. What am I missing here? Thank you.

nPr formula is n!/(n-r)! where nPr represents permutating r numbers in n places. It is basically n p (n-k-1).

Problem C : if (cmx == 1) ans = (ans — sub + MOD) % MOD; I don't know why we need plus MOD. I thought we just need : ans = ( ans — sub ) % MOD Thanks for someone explain this (^^)

I think when $$$(ans-sub)$$$ is negative, (ans-sub)%mod will also be negative. In that case, the correct answer should be mod-(ans-sub) which could be better written as (ans-sub+mod)%mod (handles both positive and negative cases).

It's because ans and sub are both %MOD, and if (ans%MOD — sub%MOD) < 0, so ( ans — sub ) % MOD will be < 0 too, that's because the % of negative numbers is also negative.

for example, if MOD = 1e9+7, sub = 5 and ans = 1e9 + 8 (but in your code ans = 1, because you do ans%= MOD): ans = (1 — 5)%MOD = -4%MOD = -4

But if you add MOD this never you be negative, because sub < MOD.

I hope you understood and sorry for my bad english, I'm not fluent.

I get that you are doing this because ans-sub can be negative but how does

`MOD+(ans-sub)`

give the right answer when`ans-sub`

is negative. Is this a property of MOD?The "taking value modulo MOD" operation basically tells you the distance between your number and the previous number that divides MOD. So in case of negative numbers (in range (-MOD; 0)) you need to find the distance between -MOD and your number. If you shift both values by adding MOD it becomes the distance between 0 and (your number + MOD) which is of course (your number + MOD).

By the way, answer can be simplified to n! * k / (k+1). That way you don't need to subtract modulo MOD :)

I can't understand why we have to do this? Why can't we just do ans-(ans/(k+1))

Moreover, I cannot understand the meaning of this line What's happening here

SpoilerYou can't just divide $$$n!$$$ by $$$k+1$$$ because of here $$$n!$$$ is actually modulo of $$$n!$$$, so either don't include $$$k+1$$$ while calculating $$$n!/(k+1)$$$ or use multiplicative modular inverse of $$$k+1$$$ for division. Hope this helps you.

Thank you for your reply Can you tell me whats "multiplicative modular inverse of k+1" is?

Here

In problem C my approach giving the wrong answer on test 2 but I couldn't understand why it is giving this error.

My SolutionIf the maximum number in the array exists more than once we can simply print

N!. Because they will go together to end of the discussion, However,if it exists only once there should beSo we can find unwanted situations and we can subtract it frommaximum-1in front of the maximum.N!.We can replace other numbersexcept maximum and maximum-1.we can do this in:Permutation(N!,number_of_maximum + number_of_maximum-1)different ways.After we have replaced others, we can put the numbers with values

maximums and maximum-1.If we don't have anymaximum-1in front of maximum it is an unwanted situation. Hence, we can replace them in:(number_of_maximum-1)!different ways.Because we can put the maximum in the end and we can permutate others.

CodeI tried to explain it well. I hope you got it and you can help me.

UPD:I added accepted solution so you can check my solution to understand the problem.It's because of this

`int x = (fact(n) / fact(mp[maxi] + mp[maxi-1])) % mod;`

fact(n) is divisible by fact(mp[maxi] + mp[maxi-1] if you don't use mod, but with mod it doesn't, for example:

16 is divisible by 8 but if i use mod 3 (16%3 = 1 and 8%3 = 2): 1 isn't divisible by 2

To fix this we can use module inverse, you can see it here or here

I hope you understood and sorry for my bad english.

upt: I don't know if the rest of your solution is correct

Thanks for your answer I got it. I didn't consider errors about mods.

For problem A you can use two pointers.

SpoilerIs it worth ?

The first idea that came to me was to use two pointers. We need to shift the pointers until we find the desired substring, so we find the longest balanced substring in $$$O(n)$$$. This algorithm is not the simplest one, but why not give it a try?

There are 4 methods for this question. 1. O(n) — simple traversal as described in editorial. 2. O(n^2) — brute force — generating all subarrays 3. O(n) — using two pointers. 4. O(n) — using traversal + map used to store sum till particular index

What about finding count of 'a' and 'b' for each range using segment/fenwick trees ? Isn't that useful ?

I have a different implementation for E , I am traversing on 1 match per function call by finding the people who haven't lost yet . It was giving TLE until I figured out ( yes figured out , because I didn't Google it ) how to traverse on Only set bits of a number in a given range ( range of bits ) . My submission

I think there exists a method for question D that is a little faster than the tutorial. The method used in the tutorial is to enumerate points, but I think it would be faster to enumerate edges. We divide the points into two groups, on x and on y, and discard the ones that satisfy both, since they cannot be composed. This way a pointer can be used to model the points that are between the two edges. Here the practice of my idea link

Your codes for D/E/F are soo looooong

Easy D approach -

Count no of points between each adjacent vertical lines. Let this count be n. Total no of pairs will be n*(n-1)/2. Subtract those pairs which lie on same horizontal line. This can be easily done using map.

Do the same for each adjacent horizontal lines

128428875

Hello, Can anybody please explain what does (1<<(1<<k))-1 represent in problem E??

It means $$$2^{2^k}-1$$$. The << (bitwise shift) operator shifts the bits in the left number by the right number of times.

[deleted]

Both $$$m$$$ and $$$n$$$ can be upto $$$2e5$$$. So yes, $$$O(mn)$$$ will exceed both memory and time limits.

Hi I was upsolving the C problem, can someone tell me why this wont pass the second test case? Thanks in advanced! my solution

If you want to modulo division, you should use the inverse.

128528815

Hi The solution shared from problem A

Does it produce the output as shown in https://codeforces.com/contest/1569/problem/A ?

I am getting the output as

instead of

Am i missing something?

Thanx for the editorial. I'm practicing now and I think i've misunderstood the logic of the tutorial for problem B. why the answer is "NO" if there are only tow players of the second type? like the following test:

there are tow matches here, in the first one player one can win, and in the other match player tow can win, and then they are both pleased. could anyone explain it for me please.

my submission 129265572 in my submission, I replaced each player of the second type who win at least 1 match by character '0', and a player of the second type win a single matchm and this when he face a player whose value is not '1'.

They cannot both win against each other. If one wins, the other automatically loses

Can someone help me with my solution for problem C. So I came up with the same idea as the solution that a nice permutation must have at least 1 pair of i, j that i < j, a[i] is the largest number of the array and a[j] = a[i] — 1. I will call the largest number M. So using that, I will choose 2 position for M and M-1 , so there will be n*(n-1)/2 ways to place M and M-1. Suppose there are k number equal to M-1, there will be k*n*(n-1)/2 such ways. The remaining element can be placed anywhere so there will be (n-2)! ways. So in total there will be k*n*(n-1)/2*(n-2)! pair of nice permutation. But this formula gives the wrong answer for the 4th example test. I haven't known what is wrong with my solution yet so I hope u guys will help me with it. Thanks in advance!

There is a typo in the last line of paragraph 5, 1569D. strret->street :D @awoo