Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
s = list(input().split())
s = "".join(s)
if "101" in s:
print('NO')
else:
print('YES')
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
for _ in range(int(input())):
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
hasColor = [0] * (n * m)
hasBad = [0] * (n * m)
for i in range(n):
for j in range(m):
hasColor[a[i][j] - 1] = 1
if i + 1 < n and a[i][j] == a[i + 1][j]:
hasBad[a[i][j] - 1] = 1
if j + 1 < m and a[i][j] == a[i][j + 1]:
hasBad[a[i][j] - 1] = 1
print(sum(hasColor) + sum(hasBad) - 1 - max(hasBad))
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 main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> dp(4, 0);
dp[0] = 1;
while (n--) {
int x;
cin >> x;
if (x == 2) dp[x] = add(dp[x], dp[x]);
dp[x] = add(dp[x], dp[x - 1]);
}
cout << dp[3] << '\n';
}
}
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;
int n = s.size();
int i = 0;
while (i < n / 2 && s[i] == s[n - i - 1]) ++i;
n -= 2 * i;
s = s.substr(i, n);
int ans = n;
for (int z = 0; z < 2; ++z) {
int l = 0, r = n;
while (l <= r) {
int m = (l + r) / 2;
vector<int> cnt(26);
for (int i = 0; i < m; ++i)
cnt[s[i] - 'a']++;
bool ok = true;
for (int i = 0; i < min(n / 2, n - m); ++i) {
char c = s[n - i - 1];
if (i < m) {
ok &= cnt[c - 'a'] > 0;
cnt[c - 'a']--;
} else {
ok &= (c == s[i]);
}
}
for (auto x : cnt)
ok &= (x % 2 == 0);
if (ok) {
r = m - 1;
} else {
l = m + 1;
}
}
ans = min(ans, r + 1);
reverse(s.begin(), s.end());
}
cout << ans << '\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())
typedef long long li;
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);
string s;
int a, b, ab, ba;
inline bool read() {
if(!(cin >> s))
return false;
cin >> a >> b >> ab >> ba;
return true;
}
int process(vector<int> &rem, int &tot) {
int placed = 0;
sort(rem.begin(), rem.end(), greater<int>());
while (!rem.empty() && tot > 0) {
int cnt = min(rem.back() / 2, tot);
placed += cnt;
tot -= cnt;
rem.back() -= 2 * cnt;
if (rem.back() == 0)
rem.pop_back();
}
return placed;
}
int remnants(vector<int> &rem, int &tot) {
int placed = 0;
for (int &cur : rem) {
int cnt = min(tot, (cur - 2) / 2);
placed += cnt;
tot -= cnt;
cur -= 2 * cnt + 2;
}
return placed;
}
inline void solve() {
s.push_back(s.back());
int eq = 0, placedPairs = 0;
vector<int> remAB, remBA;
int lst = 0;
// cerr << "s = " << s << endl;
fore (i, 1, sz(s)) {
if (s[i] != s[i - 1])
continue;
if (s[lst] == s[i - 1]) {
// ABA..A or BAB..B
eq += (i - lst) / 2;
}
else {
int len = i - lst;
if (s[lst] == 'A') {
// ABA..B
remAB.push_back(len);
}
else {
// BAB..A
remBA.push_back(len);
}
}
// cerr << lst << ", " << i << endl;
lst = i;
}
s.pop_back();
placedPairs += process(remAB, ab);
assert(remAB.empty() || ab == 0);
placedPairs += process(remBA, ba);
assert(remBA.empty() || ba == 0);
placedPairs += remnants(remAB, ba);
placedPairs += remnants(remBA, ab);
int remPlaced = min(eq, ab + ba);
placedPairs += remPlaced;
int needA = count(s.begin(), s.end(), 'A') - placedPairs;
int needB = count(s.begin(), s.end(), 'B') - placedPairs;
if (needA <= a && needB <= b)
cout << "YES\n";
else
cout << "NO\n";
}
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 N = 400043;
const int BUF = N * 20;
int* where[BUF];
int val[BUF];
int cur = 0;
void change(int& x, int y)
{
val[cur] = x;
where[cur] = &x;
x = y;
cur++;
}
void rollback()
{
cur--;
(*where[cur]) = val[cur];
}
struct DSU
{
vector<int> p, s;
int n;
int comps;
int get(int x)
{
if(p[x] == x) return x;
return get(p[x]);
}
void merge(int x, int y)
{
x = get(x);
y = get(y);
if(x == y) return;
change(comps, comps - 1);
if(s[x] < s[y]) swap(x, y);
change(p[y], x);
change(s[x], s[x] + s[y]);
}
DSU(int n = 0)
{
this->n = n;
s = vector<int>(n, 1);
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
comps = n;
}
};
struct edge
{
char g;
int x;
int y;
edge(char g = 'A', int x = 0, int y = 0) : g(g), x(x), y(y) {};
};
DSU A, united;
vector<edge> T[4 * N];
int ans[N];
void dfs(int v, int l, int r)
{
int state = cur;
for(auto e : T[v])
{
united.merge(e.x, e.y);
if(e.g == 'A') A.merge(e.x, e.y);
}
if(l == r - 1)
{
ans[l] = A.comps - united.comps;
}
else
{
int m = (l + r) / 2;
dfs(v * 2 + 1, l, m);
dfs(v * 2 + 2, m, r);
}
while(state != cur) rollback();
}
void add_edge(int v, int l, int r, int L, int R, edge e)
{
if(L >= R) return;
if(L == l && R == r) T[v].push_back(e);
else
{
int m = (l + r) / 2;
add_edge(v * 2 + 1, l, m, L, min(m, R), e);
add_edge(v * 2 + 2, m, r, max(L, m), R, e);
}
}
map<pair<int, int>, int> last[2];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
A = DSU(n);
united = DSU(n);
for(int i = 0; i < q; i++)
{
string s;
int x, y;
cin >> s >> x >> y;
--x;
--y;
int idx = (s[0] == 'A' ? 0 : 1);
if(x > y) swap(x, y);
if(last[idx].count(make_pair(x, y)) == 0)
{
last[idx][make_pair(x, y)] = i;
}
else
{
add_edge(0, 0, q, last[idx][make_pair(x, y)], i, edge(s[0], x, y));
last[idx].erase(make_pair(x, y));
}
}
for(int i = 0; i < 2; i++)
for(auto a : last[i])
add_edge(0, 0, q, a.second, q, edge(char(i + 'A'), a.first.first, a.first.second));
dfs(0, 0, q);
for(int i = 0; i < q; i++)
cout << ans[i] << "\n";
}
rating update when
1685B - Linguistics
105444G - Gig Combinatorics
System testing is running right now.
Oh
next year
probably lol
seems like it...
tbh, I would rather they spend longer doing anti-cheating measures than for rating to appear and then rolled back bc they found loads of cheaters
makes sense
A ~ E all have tag "greedy". I think it might be better to swap E and F so that programming skills can be improved as well.
can you pls tell me how to do C using greedy? I scratched my head over C for $$$1.5$$$ hrs staright (cuz i do not know dp :/)
Actually you can find that a beautiful sequence in this condition shows like this:
$$$1,2,2,2,\cdots,2,2,3$$$
count the sequence. That's all.
define "count the sequence"?
Count how many 1, 2, 2, 2, ..., 2 you have (or maybe just 1).
You get an 1 : add 1;
You get a 2 : multiply by 2;
You get a 3 : add the number to the result.
same I too got 7 TLE
You can see dynamic programming as splitting the problem into multiple states, each state representing the solution to a subproblem of the main problem. The splitting should be done in a way that solving one subproblem makes solving the next subproblem easy (this is called a transition).
One of the usual way to split the problem is to cut the array you're given at some index and calculate the value for this shorter array. That way if you know the value for the subarray from index $$$1$$$ to $$$i$$$, it can be easy to calculate the value for the subarray from index $$$1$$$ to $$$i+1$$$.
For problem C, you know the beautiful sequences look like $$$1, 2, 2, ..., 2, 2, 3$$$. One way to construct such a sequence is to start with a $$$1$$$, then add any number of $$$2$$$s you want and finally end with a $$$3$$$. This gives us three different states for our dp (called state $$$j$$$ in the editorial). Then there are three different transition for each index $$$i$$$ :
The number you're looking for is the count of finished sequences at index $$$n$$$ so $$$dp_{n,3}$$$.
can some one please help me understand the transition when si = 2, I didnt get
If $$$s_i=2$$$, then you want to find all ways of creating a sequence of the form $$$1, 2, 2, ...$$$. There are three possibilities :
You add up all possibilities and you get $$$dp_{i+1,2}=2*dp_{i,2}+dp_{i,1}$$$
Thanks, got it
NVM I got it
I was just thinking how would we solve if all conditions were removed except the order that is 123,1123,12233,1233 ... Are allowed?
Do you know some resources using which i could practice such dp on subsequences problems??
You can just filter problems with the 'dp' tag on codeforces. There are plenty of problems for every level if you want to pratice and learn dp
Another way you can do it is like this: iterate from right to left, and store a current variable and when you
see a $$$2$$$, multiply your current variable by 2 because all the subsequences to the right can either contain the two or not.
see a $$$3$$$, add 1 to your current variable to start a new chain of subsequences ending at that $$$3$$$.
see a $$$1$$$, just add the current variable to your total result since everything else is accounted for.
The only problem is that you also count the subsequences $$$1, 3$$$, so just whenever you encounter a $$$1$$$, subtract off all $$$3$$$ s that have appeared after it.
thanks, this was much more intuitive than the dp solution
My experience on educational rounds is that the last problem is often easier than the second last problem if you have knowledge about many data structures/algorithms.
Thanks for your experience, I'll change my strategy in the future ECR.
Awesome contest!!!
F is way too standard for experienced coders(especially Chinese),shouldn't appear at this position.
I would like to take this opportunity to ask,are there any standard problemsets that Chinese CP guys solve? :)
Go to luogu, I think quite a few Chinese competitive programmers solve problem sets on that
Super slow editorial!
Lighting slow editorial
But the problems were very interesting
Why can't we use DSU with rollbacks together with paths compression?
What is this method(DSU with rollbacks)? Resources please!!
When using DSU you have two functions
find(x)
— find the leader of the set that contains $$$x$$$ (not really important for rollbacks)unite(x, y)
— unite sets containing $$$x$$$ and $$$y$$$ respectivelyThe thing with rollbacks is you want to undo the
unite(x, y)
operation.If you look at the following code for this function
you can see we do $$$O(1)$$$ changes (last three lines of function).
We can save these changes in stack-like structure and when we need to rollback we can easily do it by reading the top tuple of the stack.
Here we can just save pairs $$$(x, y)$$$ and do the following:
More about this:
https://cp-algorithms.com/data_structures/deleting_in_log_n.html
https://usaco.guide/adv/offline-del?lang=cpp
Thanks for detailed reply, but as I understood, the main thing is not in rollbacks structure. If we had paths compressions, it's anyway some changes in arrays size and par, so we can just push pairs {v, par[v]} and {v, sz[v]} on stack before operations and rollback them easily, even with path compression. I think in DCP offline case, as tfg mentioned, it`s redundant, because anyway after rollback we decompress paths, so it seems like we dont achieve alpha in asymptotics and it stays log n anyways.
You can but it won't change the complexity. As long as you still do union by rank or union by size.
oh interesting, for some reason, I thought that path compression+by rank/size+rollbacks would be O(n) but I guess that was silly to think that
Of course you can't.
If only path compression is implemented (without union by rank), there exists a possibility of generating a chain of length O(n).
Although amortized analysis suggests that one only needs to pay a single $$$O(n)$$$ cost for path compression, after which all subsequent queries achieve $$$O(1)$$$ time complexity,
the existence of rollback operations fundamentally breaks this guarantee! A single rollback operation could nullify the effects of previous path compressions.
This occurs because amortized complexity and persistence are inherently conflicting concepts—persistence invalidates the assumptions of amortized analysis.
For similar reasons, data structures like the Splay Tree cannot be made persistent either.
Can someone explain the dp transition equation of problem C.
I did it there if you want to take a look : https://codeforces.me/blog/entry/139774?#comment-1248589
thx. very helpful
I think in question B, it's easy to misunderstand. That is, select a cell that wants to meet no connections around it
For problem D, I have an alternate solution for the 2nd half after you cast out the prefix and suffix of the original string. When a string is palindrome, for n/2 first character, the number of each character is equal to half of the total. For example, in the string "abccccccba", there are 2/2 = 1 'a', 2/2 = 1 'b', 6/2 = 3 'c'
So I will run from 1 to n/2, and whenever the number of each character exceeds half of the total, for example position i, it is sure that I will have to reshuffle [i, n], thus reshuffle n — i + 1 character. Then, I do a similar run from n back to n/2 + 1 to find the position i such that I have to reshuffle [1, i]
However, if I can't find such position i (for example "acbddbac"), I know I have to reshuffle at most n/2 character. To optimize the answer, I found out you don't have to reshuffle the center if it is a palindrome (I mean, in the string "acbddbac", the center "bddb" is already a palindrome, and I shouldn't reshuffle it but reshuffle the prefix "ac").
So, it's my O(n) solution, you can see my code here: https://codeforces.me/contest/2069/submission/306731691. Sorry for my bad English
broken Englash ahh shi
thanks!!
Any solution of C without dp?
Can you please explain me the part where you are calculating the "ways"?
Number of ways to make an array with the first element a 1 and all other elements a 2, using any elements up to the current index.
But for that I was thinking counting the no of 2's (let's say X) and whenever I encounter a 3, I will just add 2^X — 1. But I couldn't understand ur formula "ways = 2 * ways + ones". All the top participants have done the same thing. Am I missing something?
Your idea would work, if there was exactly one 1 at the start of the array and no 1s anywhere else.
I actually tried something similiar, and it tled :( The reason is definitely obvious. 306989184
Yes ofcourse by precomputing powers of two and using a little maths , you can solve this without dp also , Here below is one way to do so (i don't quite know how to implement DP so i use maths as a bonus tool for myself):-
306917242
PLS UPVOTe...
For a pair of $$$1$$$ and $$$3$$$ such that position of $$$1$$$ < position of $$$3$$$, let $$$x$$$ be the number of $$$2s$$$ between them, so the pair $$$1$$$ and $$$3$$$ contributes with $$$2^x - 1$$$ to the answer. For now, forget about the $$$-1$$$ and let the contribution be just $$$2^x$$$
Let's iterate on the array from left to right and calculate the total contribution for each $$$3$$$ to the answer.
Let $$$suf_i$$$ is the number of $$$2s$$$ in the suffix $$$i$$$, and $$$p(i,j)$$$ is the number of $$$2s$$$ between $$$i$$$ and $$$j$$$
So $$$P(i,j) = suf_i - suf_j$$$
Let the current $$$3$$$ we are calculation is at position $$$j$$$, then its contribution is $$$\sum_{i = 1, a_i = 1}^{j-1} 2^{p(i,j)} = \sum_{i = 1, a_i = 1}^{j-1} 2^{suf_i - suf_j}$$$
Since $$$suf_j$$$ is constant for each $$$i$$$ so we can take it as common factor and the contribution will be $$$\frac{\sum_{i = 1, a_i = 1}^{j-1} 2^{suf_i}} {2^{suf_j}}$$$
The term $$$\sum_{i = 1, a_i = 1}^{j-1} 2^{suf_i}$$$ can be updated on the fly in the loop.
And finally, Let $$$rem$$$ be the number of pairs ($$$i$$$,$$$j$$$) such that $$$i$$$ < $$$j$$$, $$$a_i = 1$$$, $$$a_j = 3$$$, so that we can compensate all the $$$-1$$$ that we have ignored
Check my code here: https://codeforces.me/contest/2069/submission/306743594
Kind of similar to what i have done, actually the same , I feel like doing maths that dp, because i do not know much of it , Any suggestions on where to learn it?? like some resources ?PG_Mazen
I couldn't understand your question. Do you mean resources for Math or dp ?
DP i mean
Check the following:
Source 1
Source 2
Source 3
hey i have done similar, but my code gives wrong answer and overflows , could you please help me out ?306751479
I think that the problem is in this part:
tmp=(tmp%mod-cnt%mod)%mod;
It should be:
tmp=(tmp%mod-cnt%mod+mod)%mod;
thankyou, got it!!
Is it this usual to not get delta updated in the rating for the educational rounds or is it this time that taking too much time to get updated? Anyone , is it me or everyone?
Taking too long. Something wrong with the round ig because many reds in official standings when it's supposed to be unrated for Div 1.
It's normal that div1 participants appear in the official standings (check out past Edu contests). Unrated participants and unofficial participants are different concepts.
What's the difference btw? In the last edu round there was a difference of 500 in my official and unofficial standings ranks this times it's about 50.
In Edu rounds, almost all people are official participants -- I think just virtual participants are excluded as unofficial participants. (So your rank in unofficial standings may change over time.)
My solution for problem is different from the editorial : 306925674
Really great editorial on D.
Here I would like to discuss an alternative approach which is a bit more bland I guess but which I found easier to implement. (Read the editorial answer if you already haven't, it's really great.)
Basically after reducing the substring as discussed in the editorial, the answer would be a prefix or suffix. Let's say its a prefix. Then, there are two cases:
The required length is <=n/2. In this case, the right half of the string decides the left half, and hence, the length of the prefix we need to shuffle is the position of the last character, where the character does not match the corresponding character of the palindrome determined by the right half. If that length is <=n/2 we have our answer.
The required length is >n/2. In this case, the only necessary and sufficient condition is that the frequency of elements in the left half is >= that in the right half, and their parity is same (as the length of the string is even, and equal number of characters were removed from start and finish, so length of the reduced string is also even). This is because if the frequency is less, then the left half won't have sufficient characters to fill in corresponding places with the right half to form the palindrome. If it is more, then we can always arrange the characters with some characters in both left and the occupied right half in the prefix (this is always consistent as sum of character frequency is required length (fixed for fixed length).) The parity ensures that all characters have even final frequency, which is necessary for even length palindrome. We can perform this check using prefixes in (26*n) time.
We can repeat the similar process once again by reversing the string so as to get the shortest length for the suffix case also. Overall it's complexity is (26*n) which works pretty well under the given constraints.
Solution Link