Problem idea: adamant

Preparation: adamant

**Editorial**

**Solution**

```
void solve() {
int n, k;
cin >> n >> k;
string t[n];
int ans = n;
for(int i = 0; i < n; i++) {
cin >> t[i];
if(t[i] != t[0]) {
ans--;
}
}
cout << ans << "\n";
}
```

Problem idea: adamant

Preparation: adamant

**Editorial**

**Solution**

```
void solve() {
int n;
cin >> n;
if(n == 1) {
cout << 1 << "\n";
} else if(n % 2) {
cout << -1 << "\n";
} else {
int a[n];
iota(a, a + n, 1);
for(int i = 0; i < n; i += 2) {
swap(a[i], a[i + 1]);
}
for(auto it: a) {
cout << it << ' ';
}
cout << "\n";
}
}
```

1817A - Почти возрастающая подпоследовательность

Problem idea: dario2994

Preparation: jeroenodb

**Editorial**

**Solution**

```
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q; cin >> n >> q;
vi a(n);
for(int& i : a) cin >> i;
vi p(n-1);
for(int i=1;i<n-1;++i) {
int downhill = a[i-1]>=a[i] and a[i]>=a[i+1];
p[i] = p[i-1] + downhill;
}
while(q--) {
int l,r; cin >> l >> r;
--l,--r;
if(l==r) {
cout << "1\n";
} else {
int ans = (r-l+1) - p[r-1] + p[l];
cout << ans << '\n';
}
}
}
```

Problem idea: jeroenodb

Preparation: jeroenodb

**Hint 1**

Can you find a necessary condition for whether a Fish Subgraph exists?

**Hint 2**

For the Fish Subgraph to exist, the graph must have a cycle with one node in the cycle having degree at least 4.

**Hint 3**

When the necessary condition is satisfied, actually, you can always find a Fish Subgraph. Try to prove this, and see if your proof can be turned into an algorithm.

**Editorial**

**Solution**

```
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
void solve() {
int n,m; cin >> n >> m;
vvi adj(n);
while(m--) {
int u,v; cin >> u >> v;
--u,--v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// find cycle and node with big degree.
for(int u=0;u<n;++u) if(adj[u].size()>=4) for(int v : adj[u]) {
// find path from u to v, without edge (u,v)
vi cur;
vi p;
vector<bool> vis(n);
auto dfs = [&](auto&& self, int at) -> void {
vis[at]=1;
cur.push_back(at);
if(at==v) {
p=cur;
return;
}
for(int to : adj[at]) if(!vis[to]) {
if(at==u and to==v) continue;
self(self,to);
if(!p.empty()) return;
}
cur.pop_back();
};
dfs(dfs,u);
if(p.empty()) continue;
// found cycle, with a node with degree >=4
vi extra = adj[u];
extra.resize(4);
int mn = p.size();
for(auto i : extra) {
auto it = find(all(p),i);
if(it!=p.begin()+1) {
mn = min(mn,int(it-p.begin())+1);
}
}
p.resize(mn);
partition(all(extra),[&](int i) {return count(all(p),i)==0;});
extra.resize(2);
cout << "YES\n";
cout << p.size()+2 << '\n';
auto out = [&](int a, int b) {cout << a+1 << ' ' << b+1 << '\n';};
int prv=p.back();
for(auto i : p) {
out(i,prv);
prv=i;
}
out(u,extra[0]);
out(u,extra[1]);
return;
}
cout << "NO\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while(t--) solve();
}
```

Problem idea: adamant

Preparation: adamant

**Editorial**

**Solution**

const int mod = 1e9 + 7;
namespace algebra {
const int maxn = 3e6 + 42;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T bpow(T x, size_t n) {
if(n == 0) {
return T(1);
} else {
auto t = bpow(x, n / 2);
t = t * t;
return n % 2 ? x * t : t;
}
}
const int m = mod;
struct modular {
int r;
constexpr modular(): r(0) {}
constexpr modular(int64_t rr): r(rr % m) {if(r < 0) r += m;}
modular inv() const {return bpow(*this, m - 2);}
modular operator - () const {return r ? m - r : 0;}
modular operator * (const modular &t) const {return (int64_t)r * t.r % m;}
modular operator / (const modular &t) const {return *this * t.inv();}
modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;}
modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;}
modular operator + (const modular &t) const {return modular(*this) += t;}
modular operator - (const modular &t) const {return modular(*this) -= t;}
modular operator *= (const modular &t) {return *this = *this * t;}
modular operator /= (const modular &t) {return *this = *this / t;}
bool operator == (const modular &t) const {return r == t.r;}
bool operator != (const modular &t) const {return r != t.r;}
bool operator < (const modular &t) const {return r < t.r;}
explicit operator int() const {return r;}
int64_t rem() const {return 2 * r > m ? r - m : r;}
};
istream& operator >> (istream &in, modular &x) {
return in >> x.r;
}
ostream& operator << (ostream &out, modular const& x) {
return out << x.r;
}
vector<modular> F(maxn), RF(maxn);
template<typename T>
T fact(int n) {
static bool init = false;
if(!init) {
F[0] = T(1);
for(int i = 1; i < maxn; i++) {
F[i] = F[i - 1] * T(i);
}
init = true;
}
return F[n];
}
template<typename T>
T rfact(int n) {
static bool init = false;
if(!init) {
RF[maxn - 1] = T(1) / fact<T>(maxn - 1);
for(int i = maxn - 2; i >= 0; i--) {
RF[i] = RF[i + 1] * T(i + 1);
}
init = true;
}
return RF[n];
}
}
using namespace algebra;
using base = modular;
void solve() {
int d;
cin >> d;
vector<base> A(d + 1), B(d + 1);
copy_n(istream_iterator<base>(cin), d + 1, begin(A));
copy_n(istream_iterator<base>(cin), d + 1, begin(B));
base s = 0, k2 = 0;
auto coef = [&](int i) {
return base((d - i) % 2 ? -1 : 1) * rfact<base>(i) * rfact<base>(d - i);
};
for(int i = 0; i <= d; i++) {
s += (A[i] - B[i]) * coef(i) * (d * (d + 1) / 2 - i);
k2 += (A[i] + B[i]) * coef(i);
}
s *= base(2) / (k2 * d);
cout << s << "\n";
}

Problem idea: adamant

Preparation: jeroenodb

**Editorial**

Instead of caring about the positions of all the toys, we only need to care about the position of the special toy with index $$$k$$$. The other toys can be treated as undistinguishable.

The intended way of solving this problem is playing the game in the webpage, trying to come up with some simple combinations of operations that make the special toy move to another position in a predictable way. Using these building blocks in a smart way, finding a way to move the special toy to the topleft.

As the size of the grid can be up to $$$100\,000$$$ and we can make $$$1\,000\,000$$$ moves, we will be aiming for a solution which does a linear number of moves.

There are lots of potential solutions which use a linear number of moves, here is a relatively painless one:

Do casework on $$$k$$$:

- Case $$$1$$$: If $$$1 \leq k < \frac{n-1}{2}$$$, we initally make one $$$\texttt{R}$$$ button press to align the toys with the right boundary. After this, there is an easy pattern to expose all the toys in the left halve, one by one: $$$\texttt{DRURDRUR...}$$$ repeated. When the special toy is exposed, the repeating pattern is stopped, and $$$\texttt{DL}$$$ are pressed. Toy $$$k$$$ will be moved to the topleft corner.

**Visualization**

Left halve solution for $$$n=15$$$.

- Case $$$2$$$: If $$$k = \frac{n-1}{2}$$$, the puzzle can be solved in two moves: $$$\texttt{DL}$$$.

**Visualization**

Solution for middle toy and $$$n=15$$$.

- Case $$$3$$$: If $$$\frac{n-1}{2} < k \leq n-2$$$, we try to reduce back to case $$$1$$$, by moving the special toy to the left halve, and ensuring that all other toys are in the top row. Using symmetry, we can apply case $$$1$$$ to $$$k^\prime = n-1 - k$$$, but mirror all horizontal moves, to move the toy to the topright corner. The other toys are no longer all in the top row. To fix this, the last pattern we need is again $$$\texttt{DRURDRUR...}$$$ repeated. After a while of repeating this, all toys will be in the right halve of the board, occupying the top and bottom row. To finish moving the special toy (which stayed in the topright corner), we do the buttons presses $$$\texttt{LDRU}$$$. All toys end up in the top row, and the special toy will be at position $$$k_\text{new} = \frac{n-1}{2} - 1$$$, so this successfully reduces to case $$$1$$$.

**Visualization**

Full solution for right halve for $$$n=15$$$.

How many moves does this take? In case $$$1$$$ the pattern $$$\texttt{DRUR}$$$ needs to be repeated at most $$$\approx \frac{n}{2}$$$ times. In case $$$3$$$, we need to use the first pattern $$$\frac{n}{2}$$$ times, and we use the second pattern $$$\frac{n}{2}$$$ times. We reduce down to case $$$1$$$, but luckily the special toy is already close to the correct position, so only a constant number of extra moves are done.

So in total, this solution uses $$$O(1) + \max \left( 4\frac{n}{2}, 4 \cdot 2 \frac{n}{2} \right) = 4n + O(1)$$$ moves. So this solution fits well within the constraints, although it is pretty wasteful.

Bonus: Can you prove that the optimal number of moves needed in the worstcase (over all $$$k$$$) for a width of $$$n$$$ is $$$\Omega(n)$$$? We only did some testing of small cases, with a bruteforce BFS solution, and found that the worstcase is around $$$n/2$$$ button presses.

**Solution**

```
#include "bits/stdc++.h"
using namespace std;
int main() {
int n,k; cin >> n >> k;
--k;
int half = (n-3)/2;
string res = "";
if(k==half) {
res = "DL";
} else {
while(true) {
if(k<half) {
res+="R";
int need = half-1-k;
while(need--) {
res+="DRUR";
}
res+="DL";
break;
} else {
int need = k-half-1;
while(need--) {
res+="LDLU";
}
res+="LDR";
for(int i=0;i<half+1;++i) {
res+="DRUR";
}
res+="LDRU";
k = half-1;
}
}
}
cout << res << '\n';
}
```

Problem idea: adamant

Preparation: adamant

**Editorial**

**Solution**

```
// split into 1, ..., k and k+1, ..., n
pair<int, istring> check_k(istring const& a, int k) {
int n = size(a);
istring A(n, 0), B(n, 0);
for(int i = 0; i < n; i++) {
if(i <= k) {
A[min(k, i + 1)] += a[i];
} else {
B[min(n - k - 2, n - i)] += a[i];
}
}
// multiply by 2^(n - i - 1) instead of dividing by 2^i
reverse(all(A));
reverse(all(B));
int carry = 0;
// subtract A from B and normalize base 2
for(int i = 0; i < n; i++) {
B[i] -= A[i] - carry;
carry = B[i] >> 1; // floor(B[i] / 2)
B[i] &= 1;
}
if(carry < 0) {
return {-1, {}}; // it's always possible to make it positive
}
while(carry) {
B.push_back(carry & 1);
carry >>= 1;
}
while(!B.empty() && B.back() == 0) {
B.pop_back();
}
reverse(all(B));
return {(int)size(B) - n, B};
}
const int mod = 1e9 + 7;
int bpow(int x, int n) {
if(!n) {
return 1;
} else if(n % 2) {
return int64_t(x) * bpow(x, n - 1) % mod;
} else {
return bpow(int64_t(x) * x % mod, n / 2);
}
}
int inv(int x) {
return bpow(x, mod - 2);
}
void solve() {
int n;
cin >> n;
istring a(n, 0);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(all(a));
auto cand = check_k(a, 0);
int cnt = 0;
for(int i = 1; i < n; i++) {
if(a[i] != a[i - 1]) {
cand = max(cand, check_k(a, i - 1));
cnt++;
if(cnt == 30) {
break;
}
}
}
cnt = 0;
istring b = a;
reverse(all(b));
for(int i = 1; i < n; i++) {
if(b[i] != b[i - 1]) {
cand = max(cand, check_k(a, n - i - 1));
cnt++;
if(cnt == 30) {
break;
}
}
}
auto [sz, ansf] = cand;
int ans = 0;
for(size_t i = 0; i < size(ansf); i++) {
ans = (ans + bpow(2, (mod - 1) + (sz - i)) * ansf[i]) % mod;
}
cout << ans << "\n";
}
```

Problem idea: adamant

Preparation: adamant

**Editorial**

**Solution**

```
map<char, int> to[maxn];
int len[maxn], link[maxn];
int last, sz = 1;
void add_letter(char c) {
int p = last;
last = sz++;
len[last] = len[p] + 1;
for(; to[p][c] == 0; p = link[p]) {
to[p][c] = last;
}
int q = to[p][c];
if(q != last) {
if(len[q] == len[p] + 1) {
link[last] = q;
} else {
int cl = sz++;
len[cl] = len[p] + 1;
link[cl] = link[q];
to[cl] = to[q];
link[last] = link[q] = cl;
for(; to[p][c] == q; p = link[p]) {
to[p][c] = cl;
}
}
}
}
int term[maxn];
int used[maxn], comp[maxn], dist[maxn];
vector<int> in_comp[maxn];
void dfs(int v = 0) {
comp[v] = v;
dist[v] = 0;
used[v] = 1;
for(auto [c, u]: to[v]) {
if(!used[u]) {
dfs(u);
}
if(to[v].size() == 1 && !term[v]) {
comp[v] = comp[u];
dist[v] = dist[u] + 1;
}
}
in_comp[comp[v]].push_back(v);
}
void solve() {
string s;
cin >> s;
for(auto c: s) {
add_letter(c);
}
for(int p = last; p; p = link[p]) {
term[p] = 1;
}
term[0] = 1;
dfs();
int64_t ans = 0;
for(int v = 0; v < sz; v++) {
if(in_comp[v].size()) {
int m = in_comp[v].size();
sort(all(in_comp[v]), [&](int a, int b) {
return dist[a] > dist[b];
});
vector<int64_t> A(m), B(m);
for(int i = 0; i < m; i++) {
int u = in_comp[v][i];
int L = dist[u];
int R = L + len[link[u]];
// L' must be larger than R
int cnt = len[u] - len[link[u]];
A[i] = (int64_t)cnt * L;
B[i] = cnt;
if(i > 0) {
A[i] += A[i - 1];
B[i] += B[i - 1];
}
auto it = upper_bound(all(in_comp[v]), R, [&](int R, int b) {
return R > dist[b];
}) - begin(in_comp[v]);
if(it) {
it--;
ans += A[it] - B[it] * R;
}
}
}
}
cout << ans << "\n";
}
```

Thanks for fast tutorial!

Light speed tutorial sheeeesh!

so fast

Why is it impossible for a python solution to pass div1C/div2E?

For Fish Graph, can you do a DFS-Tree like thing with which you can find the node with degree

`>=4`

in a cycle and get to O(N+M) or am I missing something?`degree >= 4`

won't ensure that that the tail of fish don't lie inside the cycle.Refer to editorial, if you still think it is not enough then try to make a counterexample and prove that it is impossible

Sorry. The editorial came so fast that I thought I was replying on announcement blog.

It does. If a fish tail is inside the cycle, then use that tail to make a smaller cycle instead. The edge that used to be in the old cycle but isn't in the new cycle will be a correct tail outside the cycle.

i don't know what is wrong here, firstly i found every cycle and then check if it can be used as fish graph. but getting WA every time. Can anyone tell me what is wrong here? https://mirror.codeforces.com/contest/1818/submission/203991640

I guess your solution will not work if the graph is not connected because you are calling DFS only for vertex 1

Ohh, i missed it! thanks a lot!!

What if we form a bridge tree ( biconnected component decomposition) and then do dfs on the new tree and find a node with degree >=3 (as here we squeezed all cycles into a single node).

That works, however, you don’t really need to do condensation on the graph.

You only need to check if there exists $$$u$$$ such that $$$deg(u) \ge 4 \land \text{size}(\text{BCC}[u]) > 1$$$. Then you can find the cycle with a DFS (similar to CSES Round Trip).

do you mean a tarjan approach?

For problem Div2.D I don't know this approach is correct or not:

For each vertex with degree >= 4, find the shortest cycle through it, add those edges to answer, find another 2 vertices that are not in the found cycle, include those 2 edges as well.

The wrong submission, the system verdicted WA, wrote that I'm using an edge twice, while I check again the output, it doesn't seem like that. 203958546

Nvm, I forgot to output the number of edges, dumb mistake, thank you the board for answering my question

.

what is the original problem?

Problem

`Similar Polynomials`

...and for the coefficient near $$$d−1$$$ we should note that $$$[x_{d−1}](x−x_1)\dots(x−x_n)=−(x_1+\dots+x_n)$$$, thus...

What happenes on the next line?

Understood

Get back to Lagrange formula. Write it as $$$\sum_{i=0}^{d}y_i\Pi_{j \neq i}(x - x_j)\Pi_{j \neq i}\frac{1}{x_i - x_j}$$$. We have $$$x$$$ only in first product — $$$\Pi_{j \neq i}(x - x_j)$$$. We want to get its $$$[x^{d-1}]$$$. Its minus sum of its roots. So we get $$$[x^{d-1}]f(x)=\sum_{i=0}^{d}y_i c_i \cdot -\sum_{j \neq i}{x_j}$$$.

Alternative solution for 1817D - Автомат с игрушками

If the bottom left part of the toy is full, and it contains $$$k$$$, you can win using

`LDRU`

. To get this configuration, use`DLUL`

$$$3n/10$$$ times, then simulate $$$1000$$$ random moves.AC submission: 203960705

Little note: for E, you can tighten the bound to $$$\frac{n}{2} \pm \frac{\log(MAX)}{2}$$$ (possibly with some off-by-one).

For problem

`Similar Polynomials`

I changed the input from scanf() to getchar().

The running time changed from 4000+ms (203942742) to 1590ms (203961795).

Can I request to skip this TLE result 203942742?

TLE results that were non-trivial, i.e., you had to change ur code even the slightest, they don't regrade it.

Well, you remind me.

I tried the same code and got AC now, it's really a judge fault.

Well, my fault.

I tried the same code with different compiler.

`GNU C++17`

for AC,`GNU C++20 (64)`

for TLE.Bad luck for me :(

C++17 has been patched on CF to make scanf faster. See this blog . It isn't uncommon to see scanf users submitting using C++17 for this reason.

I think the best thing to do is to use cin/cout and use C++20(64 bit). Using cin/cout is the intended way to parse input in C++.

Using cin/cout and C++20(64 bit) brings it down to 841 ms 204067531

Thanks for the tips.

It seems that it is time to embrace the new century.

Toy Machine was fun. The web page was a great addition!

Is there a constructive way to figure out B? Or was it just observation?

I have used the brute force approach to generate all possible answer to see any answer for each test case follow some pattern.

if you run this code for small test, like from 1 to 11, you will observe that answer exist if n is even and if n==1, and for each n(keep in mind that it is even) there is permuatation which follow some pattern like

2 1 4 3 6 5 ..... n-2 n-3 n n-1

you can try the above code and check it out yourself

The only problem is that this brute force will work till n=11, after that it will take very long time to produce answer. So, we cannot check it for large test cases.

Also n=1 is the only odd number that produce valid answer which is 1 only.

After 1 hour of trying, this is what I did to find the pattern.

First, I think it helps a lot if you realize that solutions of odd length are impossible (with N=1 as the sole exception) because the sum of 1..N is always divisible by N. The fact that the sample data shows N=3 is impossible suggests this also.

ProofFrom the formula for triangular numbers, sum 1..N = N(N + 1)/2. When N is odd, i.e. N = 2k + 1 for some integer k, then N(N + 1)/2 = (2k + 1)(2k + 2)/2 = (2k + 1)(k + 1) = N(k + 1) which is a multiple of N.

Then, a good solution approach is to try to generate solutions manually. For N=4, you can observe that you can never have "13" or "24" or "123" or "234" or any permutation of these as substrings (since e.g. 1+2+3=6 is a multiple of 3), so that means 2 and 3 must go at the ends and 1 and 4 in the middle, leaving only "2143" and its reverse "3412" as possibilities.

Now you might have already noticed that "2143" is an extension of the solution for N=2 ("21") but if you didn't, it's natural to try and see if you can build the solution for N=6 by adding 5 and 6 somewhere to the previous solution. You cannot add "56" (because 3+5=8) but "65" works to build "214365".

At this point it seems like a safe guess that you can always add a pair of numbers to the end. There is a formal proof in the editorial but I ended up writing a brute-force solution to double-check the answers and spot-checked a few other numbers.

F can be solved with suffix automaton in $$$\mathcal{O}(n)$$$.

Hi, could you share some details please?

I solved it in $$$O(n)$$$ time using suffix array/tree; after building the suffix tree with suffix links, solving each chain can be done with two pointers instead of segment tree. I think it's the same with suffix automaton, since the suffix links of a suffix tree essentially form the suffix automaton of the reversed string.

https://mirror.codeforces.com/contest/1817/submission/203993098

what is the point from problems like div2B ? problems that depends on a pattern/sequence is pointless

Observing patterns over time is important because it: utilises the students' natural curiosity and observational skills, promoting deeper curiosity and engagement. supports a more scientific approach to observation, looking beyond the obvious features.

that seems like chat gpt answer

I believe D could be solved in O(n+m) Via DSU. To check if it is possible to reach a node from another would be O(1). And to erase edges, we would simply connect the nodes to a virtual node that sits independent from the graph. But I am not sure. .

You can also solve in $$$O(n+m)$$$ by finding bridges and running one BFS or DFS to print the cycle.

Thank you, could you please elaborate on the bridges part? I am not really familiar with bridges and articulation points

An edge is a bridge if removing that edge splits its component into two. There is an $$$O(n+m)$$$ algorithm to find all bridges in a graph.

Once you have found all bridges, you can iterate through all nodes with degree at least $$$4$$$. For each node $$$v$$$, if all of its incident edges are bridges, then it does not lie on a cycle. If there is an edge that is not a bridge, then $$$v$$$ does lie on a cycle.

Let's say the non-bridge edge is between $$$v$$$ and $$$u$$$. To find a cycle, simply run a BFS from $$$u$$$ but block the edge back to $$$v$$$. Since the edge $$$u-v$$$ is not a bridge, there must be another path from $$$u$$$ to $$$v$$$, which the BFS will find. Adding the edge $$$u-v$$$ to the path found forms a cycle. And any two other edges incident to $$$v$$$ can be added to make a fish graph.

Note this would not be a valid fish graph if any of the extra two edges incident to $$$v$$$ connected $$$v$$$ to a vertex already in the cycle. But this will never happen, since the BFS will always find the shortest path from $$$u$$$ to $$$v$$$ without traversing the edge $$$u-v$$$, so there cannot be a diagonal edge that cuts through the cycle, since that would imply a shorter path exists. This is also explained in the editorial.

Amazing, thank you so much!

Yes can you please elaborate?

Nice contest! Although my B failed the system test.

I used the same approach you mentioned in problem d fish graph , but it shows wrong answer. Here's my solution https://mirror.codeforces.com/contest/1818/submission/203940101 , I can't find wats wrong

If there were no constraints that required the club president to remain in the club (that is, if we were just trying to maximize the number of remaining members), would problem div2 A still be solvable?

Wouldn't it then be the max number of strings that are the same?

I see, that seems to work. Thanks!

Problem Div1A can be solved another way. Let’s think how the subsequence is organized. It can be created greedy: let the last included integer be a[i]. 1) if a[i+1] > a[i], so the next subsequence’s number will be a[i+1]. 2) else we need to find the first j such that a[j] < a[j+1], and the next subsequence’s numbers will be a[j] and a[j+1]. This observation can be used to calculate next[i]. So the answer is built by jumping from l to next[l], next[next[l]]… while <= r. To answer queries fast we can just count binary jumps on next[] array.

i think there's some problem in Problem D test cases. according to the statement, 1 <= m, n <= 2000 but in test 12, m = 0 in many testcases, that makes my submission 203956585 got WA.

Why is the leading coefficient of B(x-s) in 1C equal to 1? I think it's k.

On the third line of the editorial.

In the tutorial of D1C,

It should be "SA(x)=A(x+1)"

Thanks for noticing! I will fix it soon.

jeroenodb thank you very much for interesting problems !

I would like to share the solution of problem D in O(N + M). We can divide all vertices according to the components of the edge biconnection, and solve the problem for each vertex (v) in 3 cases:

1) Check that V has 2 or more edges to the vertices of other components (take them as 2 tails), and at least 2 edges to the vertices of its own component (find a cycle)

2) Check that V has 1 edge to the vertex of the other component (take as 1 tail), and at least 3 edges to the vertices of its own component, taking one vertex as the tail, and find a cycle between the remaining two.

3) Check that V has at least 4 edges to the vertices of its own component and select 2 of the 4 vertices as parts of the tail and check that removing them from the component can find a path between the remaining two.

Link to my solution: https://mirror.codeforces.com/contest/1818/submission/203962283

For C, it can be observed both polynomials have to be in the form $$$(ax+b)^d + C$$$ . The problem can then be rephrased as finding $$$(b_B-b_A)/a$$$. Taking the $$$d-1$$$ derivative gives us $$$n!a^dx+n!ba^{(d-1)}$$$ which means we can get $$$b/a$$$ or the answer by finding the differences.

For Div1C, does anybody know why this submission is giving WA on test 5? Staring at code with no luck :) Many thanks.

Edit: I found it.

`sumd % mod`

should be`sumd %= mod`

. Just took 4 hours.No

`-Wall -Wextra`

momentI tried it and it tells me statement has no effect! Thank u.

Glad to help ;)

Can anyone give a testcase in which the following code is giving wrong answer . Problem C div 2 Submission link Thanks

Thanks for Div1D/Div2F.

Very frustrated that my div2D submission (203945910) only failed because of a stack overflow. I wrote in Python, so a possible solution to this situation is to increase the stack limit using the method

`sys.setrecursionlimit()`

which allows to set the maximum depth of the Python interpreter stack to the required limit. Thus, adding it to the code (203980915), all tests were passed successfully. Definitely worth considering this experience in the future.Can someone tell me why my binary search submission for Div 2 C is wrong?

Thanks!

Can anyone explain more the div2 C problem? I still don't understand the solution very much, thanks

for an increasing subsequence, this condition must hold: x >= y >= z, you can remove one of the elements from each triplet so this no longer holds

Let's call a Sequence Bad if it is non-increasing, a thing to be observed in such sequences is that if you wish to include elements from those sequences, the maximum number of elements you can include are 2, this is because if a sequence follows the order (a[i] >= a[i+1] >= a[i+2] >= ... >= a[i+n], no matter what subsequence you choose to hold the condition for "almost increasing subsequence" you can only include 2 elements from it. Working upon this idea for a specific range [l, r] knowing that we have (r-l+1) elements in the range, you can observe that if a sequence of the form (a[i] >= a[i+1] >= a[i+2]) lies in the range you are bound to choose only two elements from it. Hence you can count while iterating through the given array the number of bad "indices" that are included in the subsequence as a prefix array. Then to get the final answer you can simply subtract the total "bad indices" in the given range [l, r] from the total length of the range. Since you have already precalculated the value of "bad indices in [l, r]" the operation takes constant O(1) time for each query.

Here I am using the same approach but getting wrong answer on test case 3. Can you tell me the counter testcase for my submission submission link

missing 1 rating for expert

For Div 1A: 1817A — Almost Increasing Subsequence,

"A sequence is almost-increasing if it does not contain three consecutive elements x,y,z such that x≥y≥z"

May I know how to solve it if instead of 3 consecutive elements, we do k consecutive elements?

If k is big (lets say n / 2) would it still be possible to preprocess in an efficient manner to run our prefix sum / binary search?

As explained in the tutorial, we took at most 2 numbers from a group if 3 consecutive non-increasing were not allowed.

We will take at most k-1 numbers from every group if k consecutive non-increasing are not allowed.

I am not entirely sure how to take at most k-1 numbers from every group, for groups of 3 we can just take the inner elements using prefix sum, however for groups of k how do we take and count it properly?

Let's say the subarrays formed by cutting at a[i] < a[i+1] be of sizes:

x1, x2, x3, ... x(k)

Now find which subarray contains index L and R using binary search and prefix sum. How?

Let y(i) = sum from x1 to x(i) You can apply binary search on "y" array to find exactly which subarray contains indices L and R.

All the subarrays in between would contain min(k-1, |x(j)|) numbers. You can easily precompute this using prefix sums.

and

Those containing indices L and R would contain min(k-1, |y(l')|-L+1) and min(k-1, R+1-|y(r'-1)|) where l' and r' denote which subarrays contain L and R.

Oh I understand now, thank you!

For Div1A, my approach was slightly different. It is as follows:

Hypothesis: If a[i] >= a[i+1] >= a[i+2], then it does not make any sense to keep a[i+1] in a subsequence.

Proof:

=> We must not keep all 3 in any subsequence, as it won't be almost increasing. So Let's remove 1 out of the 3.

=> a[i-1] >= a[i+1] is more probable than a[i-1] >= a[i], so removing a[i+1] is preferred over removing a[i]

=> a[i+1] < a[i+3] is less probable than a[i+2] < a[i+3], so removing a[i+1] is preferred over removing a[i+2]

Algorithm: Let b[i] = 1 if b[i-1] >= b[i] >= b[i+1], else 0.

For query [L, R], result = no. of elements in [L,R] — sum(b[i]) where L < i < R.

We do not include b[L] and b[R] because they cannot lie in the middle of a triplet a[i] >= a[i+1] >= a[i+2]

Code: https://mirror.codeforces.com/contest/1817/submission/203931292

Div2 A: You have to follow the boss to not get kicked out of the meeting! Follow the boss, keep the opinion same as your boss's opinion. Couldn't solve the problem in contest time. But it's a fun problem. I enjoyed it.

can someone explain why my div 2 C code does not work? https://mirror.codeforces.com/contest/1818/submission/203953371

i found out why

Div2-D/1-B Fish Graph is a great problem. It took me about 6.5 hours to learn this well and get accepted.(submitted for 15 times) I learned a lot from this. Thanks for preparing the contest.

Can you list some important observations you made during the process?

Almost the same as the editorial. However, I had trouble implementing that code. So I implemented it in an easier way. Here's my code.

Pupil

Really sad that there wasn't a sample for highest degree not equal to 1 in D1C, would have been red otherwise (on a sidenote, don't ever try to figure out a solution to a polynomial question in your head)

hello everyone

I am curious to know if It is possible to solve div1 A

if the question was longest increasing subarray instead of subsequence

(basically we need to tell the longest increasing subarray in the bounds of l to r)?

any idea would be highly appreciated

and if its impossible to solve in the given contrains please let me know. Thank You CF Community ^_^

you can probably do it with a segment tree to query the longest almost increasing subarry, then just handle the edge cases

how with seg tree we can handle the longest increasing subarray

I have a couple of doubts regarding div1 C.

I can clarify your second doubt as why they have same coefficient. wee can write , A(x+s)-B(x) = q(x). MOD ; where for each x , q(x) is an integer. now this can be possible only when q(x) is integer for all real x. which intuitively is possible only when q(x) is constant and equal to some integer. hence , A(x+s)-B(x) is independent of x. hence the conclusion follows that their leading coefficients are same.

can someone explain how method of differences works for diff 1 C if the output is modulo 10^9 + 7

Problem F can be solved by basic substring structure. Which can be solved in $$$O(n)$$$.

Div1 -B or Div2- D https://mirror.codeforces.com/contest/1817/submission/204224008

getting runtime error on test 8th some help please.

First finding all the cycles and sorting them in increasing order of their size. Checking each cycle if it has any node with degrees >=4. If yes then taking that cycle and 2 other edges for that node which are not part of the cycle.

can some body give me a simpler implementation of problem D of div 2 FISH GRAPH just the code

https://mirror.codeforces.com/contest/1818/submission/204263634

I solved it just now and feel that this is simple to implement:

So I build the path while I DFS and take the shortest cycle for nodes with >= 4 neighbours. Then I take the remaining 2 nodes from the "tail", and print out the answer. Note that shortest cycle must have length > 2, because otherwise it would be A -> B -> A which is an invalid cycle for the fish graph.

Hey, am I misunderstanding the tutorial for 1E? Shouldn't it be the case that $$$k\in [p, p + 30]\cup [q - 30, q]$$$, where $$$p$$$ is the first position that $$$a_{p + 1} - a_p > 0$$$, and $$$q$$$ is the last position that $$$a_{q + 1} - a_q > 0$$$?

Well I understand the tutorial. Both of them are correct.

How to solve Fish Graph in O(N+M)? Can anyone help?

explaination of 1818C/1817A is so good!

Can we use some greedy approach in div2C?

I made an array

`dp`

where`dp[i]`

tells the length of the longest almost-increasing subsequence from index 0 to i. Afterwards I subtracted`dp[l-1]`

from`dp[r]`

and output it as the answer. I know this approach is not full proof so I would be grateful if someone points out the mistake in my implementation or in the approach itself.Here is the link to submission (Main code starts at line 81 at

`void solve(int test_case)`

): 206277166Code snippetvoid solve(int test_case) {

}

same thing here man , any updates ? my submission used the same approach as yours

I am late, but I remember trying to find some test cases (in vain) and then accepting the given solution as final.

I was preoccupied with work and hence could not be active, so I am sorry for the late response.

1818B — Indivisible

I am a beginner guys and I thought that doing the question was just putting it in the formula r-1+1 and then finding the modulus of the value with the prefix sum of the array. This worked for the test case mentioned in the question but here I come to realize that my approach was totally wrong .

Also am I wrong ?

I mean this looks like a very high rating problem as per the editorial, Kindly advice me regarding this.

I mean, you yourself said

Okay, so I think you misunderstood the problem. We have to find a permutation for which, the given condition is true.

The condition says that modulus has to be $$$\neq 0$$$ for

allpossible combinations i.e. $$$1 \leq l \lt r \leq n$$$A and B (sometimes C as well) are generally solved with basic observations actually. Just like this one:)

I am not finding any shortest cycle but instead of finding shortest cycle, my claim is that if a node x having adj[x].size() is greater than 3 and x is part of a cycle then it must form a fish subgraph.

but my solution is Wrong On Test 15

Can Anyone tell, what i am doing wrong and provide me a testcase where my code fails.My_Code

I don't understand how is the second test case given for the question D in this contest is valid because the special node here is node 3 then it is taking extra edges as 2 <-> 3 and 3<-> 5 but the edge 3 <--> 2 is problematic I think, because the node two which is a part of extra node is already connected with the node 1 which is in the cycle and hence violating the condition of the question (that is "but they should not be connected to any other node of the cycle.", 4th line). Can anyone please clarify the statement

please consider this case for Div1B: n = 5, m = 8, edges are: {(1 2), (2 5), (5 4), (4 1), (1 3), (3 2), (3 5), (3 4)}

I don't see a Fish Graph here, although it satisfies the condition and also, it breaks the author's code

Is this a valid test? It seems to me $$$(4,5)$$$ and $$$(5,4)$$$ form parallel edges, which is not allowed.

sorry it's a typo. the last edge was supposed to be (3 4), not (5 4) (fixed now)

What power do u have?

BecauseNever gonna give you up

Never gonna let you down

Never gonna run around and desert you

Never gonna make you cry

Never gonna say goodbye

Never gonna tell a lie and hurt you

PSI can understand that you don't use English as the primary language and that's fine, but why are you being rude?

I don't think the codes are incomplete they gave you the core part that was needed.

who can tell me in the tutorial of the problem D(div2),why to resize the vector p? Isn't p's size clearly?