Разбор Educational Codeforces Round 174

#	User	Rating
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

#	User	Contrib.
1	Qingyu	157
2	maspy	150
3	nik_exists	147
4	Um_nik	145
5	Errichto	139
6	adamant	136
7	maroonrk	134
8	DNR	132
8	AmShZ	132
10	BledDest	130

2069A - Was there an Array?

Tutorial

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')

2069B - Set of Strangers

Idea: adedalic

Tutorial

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))

2069C - Beautiful Sequence

Idea: BledDest

Tutorial

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';
  }
}

2069D - Palindrome Shuffle

Idea: BledDest

Tutorial

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';
  }
}

2069E - A, B, AB and BA

Idea: adedalic

Tutorial

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;
}

2069F - Graph Inclusion

Idea: BledDest

Tutorial

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";
}

long ways = 0; int ones = 0; int twos = 0; long totalWays = 0; for(int j = 0; j<n; j++){ int val = arr[j]; if(val == 1){ ones++; } if(val == 2){ ways = ways*2 + ones; ways = ways % 998244353; } if(val == 3){ totalWays += ways; totalWays = totalWays % 998244353; } } out.println(totalWays);

Comments (62)

Show archived | Write comment?

bsdsdb

19 months ago, hide # |

← Rev. 2 →

+39

rating update when

Spoiler

→ Reply

esh_war2

19 months ago, hide # ^ |

gamma

+18

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

future_zyl

-41

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.

Gamin8ing

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 :/)

chenxi2009

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.

termindev

define "count the sequence"?

andrei_n

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.

fingerdash

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$$$ :

if $$$s_i$$$ is $$$1$$$ you have one more $$$1$$$ to start a sequence with, so $$$dp_{i+1,1} = dp_{i,1}+1$$$
if $$$s_i$$$ is $$$2$$$ you can add one more $$$2$$$ to one of the available sequences (from state 1 or state 2), you can also choose not to add a $$$2$$$, so $$$dp_{i+1,2} = 2*dp_{i,2}+dp_{i,1}$$$
if $$$s_i$$$ is $$$3$$$ then you can choose to end all sequences from state $$$2$$$, so $$$dp_{i+1,3} = dp_{i,3}+dp_{i,2}$$$.

The number you're looking for is the count of finished sequences at index $$$n$$$ so $$$dp_{n,3}$$$.

barbarian

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 :

First one is to have a sequence containing only $$$1$$$ and add $$$s_i$$$ to the sequence, this is $$$dp_{i,1}$$$ possibilities
Second one is to have a sequence of the form $$$1, 2, 2, ...$$$ and add $$$s_i$$$ to the sequence, this is $$$dp_{i,2}$$$ possibilities
Third one is to have a sequence of the form $$$1, 2, 2, ...$$$ and not add $$$s_i$$$ to the sequence, this is also $$$dp_{i,2}$$$ possibilities

You add up all possibilities and you get $$$dp_{i+1,2}=2*dp_{i,2}+dp_{i,1}$$$

TusharGupta11

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

123gjweq2

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.

tfg

+27

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.

+13

Thanks for your experience, I'll change my strategy in the future ECR.

Sul_A.

Awesome contest!!!

masonpop

+11

F is way too standard for experienced coders(especially Chinese),shouldn't appear at this position.

prakary

+16

I would like to take this opportunity to ask,are there any standard problemsets that Chinese CP guys solve? :)

Proof_by_QED

Disagree, literally the whole point of edu rounds is to introduce standard concepts to more programmers...

old_man_die_hard

+17

Super slow editorial!

Luckwet

+14

Lighting slow editorial

But the problems were very interesting

nocap

Why can't we use DSU with rollbacks together with paths compression?

case3

What is this method(DSU with rollbacks)? Resources please!!

dinohaur

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$$$ respectively

The thing with rollbacks is you want to undo the unite(x, y) operation.

If you look at the following code for this function

void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (size[x] < size[y]) swap(x, y);
  parent[y] = x;
  size[x] += size[y];
  components--;
}

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:

void rollback(int x, int y) {
  parent[y] = y;
  size[x] -= size[y];
  components++;
}

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.

lrvideckis

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

twolazy

+19

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.

unarch

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

Knights_of_Yuri

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

TraudeIOI

-26

broken Englash ahh shi

maruf004

Any solution of C without dp?

redreoicy

I realized my code is basically the same thing as all the dp code, but I wouldn't have called it dp. I guess the dp is so simple the line is a bit blurred.

v0rtex

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.

codevode

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...

PG_Mazen

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:

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;

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?

naivedyam_mishra

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.

_Kee

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.)

vedic86

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

Surge226

18 months ago, hide # |

I am getting TLE in problem D even though the my solution runs in $$$O(nlogn)$$$ (I think)

code


    // try to find that index at which the left character does not match with right character
    for(i=0;i<n;i++) {
        if(s[i] != s[n-1-i]) break;
    }
    if(i >= n) {
        cout << "0\n";
        return;
    }

    // store the characters in sorted order along with their indices
    vector<array<int,2>> cwi;
    for(int ii=i;ii<=n/2;ii++) {
        cwi.push_back({s[ii], ii});
        cwi.push_back({s[n-1-ii], n-1-ii});
    }
    // O(nlogn)
    sort(cwi.begin(), cwi.end());

    int ans = 0, l=i;
    // O(n) -> loop, O(nlogn) -> total
    for(;i<n/2;i++) {
        if(s[i] != s[n-1-i]) {
            // try to find leftmost index of right character and then swap it with current left
            // character 
            // (...a..b.......b.....)
            //     l  lir     r
            
            // O(logn)
            auto [ch, ind] = *lower_bound(cwi.begin(), cwi.end(), array<int,2>{s[n-1-i], i+1});

            // we would have to order s[l..lir] characters, both included
            ans = max(ans, ind - l + 1); 

            // in case of odd length, the leftmost index of right character would be right
            // character only
            // in that case, we can swap right character with middle character and check again
            // the right character
            // although, this case would never run because length of given string is always even
            if(ind == n-1-i) {
                swap(s[n/2], s[n-1-i]);
                i--;
            }
            // swap current left character with leftmost index of right character
            else {
                swap(s[i], s[ind]);
            }
        }
    }

I have added comments in the code for the explanation. If someone can explain where I am making the mistake, then it would be very helpful.

Thanks

gabriel

18 months ago, hide # ^ |

I can't think of anything that could TLE other than the lower_bound. Although it looks alright, sometimes it is O(n) (like calling std::lower_bound() over a std::set instead of using std::set::lower_bound()). If I were you, I would change that vector<array<int, 2>> to a vector<pair<int, int>>, just to test (maybe that array has something to do with a possible O(n) lower_bound?). If that doesn't solve your problem, then it has got to be some constant time optimizations (you could call reserve() on the vector "cwi" to speed things up).

I implemented both of the suggestions (I hope, I implemented them correctly), but it is still giving TLE verdict. solution. Also, I am confused that why lower bound on a sorted array can become $$$O(n)$$$. I would highly appreciate any help.

About lower_bound, I said that because, for example, lower_bound over non random access iterators is O(n), and I didn't know if std::array could have something do to with that. But it seems its not the cause.

I'm looking at your last loop, and that is literally the only remaining place where your algorithm could TLE. I see that inside the 'if' there is a 'i--'. If that runs several times, your complexity could actually not be O(nlogn). Are you sure your analysis of the time complexity is correct? (I can't help you with that now because I didn't try to solve the exercise nor understand the actual logic of your solution).

tooourist

15 months ago, hide # |

in problem D, is it necessary to check the suffix?

IhopeIllbeCMoneday

46 minutes ago, hide # ^ |

← Rev. 3 →

this is only needed when our segments (pref and suff) overlap

we need to put the characters missing from the suffix into the intersection, if we have characters that aren't in the suffix outside the overlap, we must put them into the intersection to balance things out and check if it's length of overlap is enough, otherwise, we do the same thing for the prefix, checking if there are characters missing in it, but appears in suff

satvikmittal638

7 months ago, hide # |

an O(n) solution for D: Lets first get rid of the matching prefix and suffix as mentioned in the solution. Then we need to find minm index l>=0 s.t. we can perform the operation on it(reverse the string and run the function again for operation on suffix). now we can have 2 cases for better understanding:

1) If l<n/2, then it must hold that multiset(s[0,l])=multiset(s[n-l-1,n-1]) and that the remaining substring in the middle s[l+1,n-l-2] must already be a palindrome. Thus we can find the largest palindromic substring in the middle, then check the multiset condition for the remaining prefix and suffix and get an ans from here.

2)If l>=n/2, then for a prefix [0,l] it must hold that the remaining suffix [l+1,n-1] must be derivable by some rearrangement of the prefix. So we must have the following 2 condition to be satisfied:

i) multiset(s[l+1,n-1]) must be a subset of multiset(s[0,l]) ii) In {multiset(s[0,l])-multiset(s[l+1,n-1])},i.e. remaining characters in the prefix after removing characters in the suffix, we must be able to form a palindrome in the middle, i.e. we must have freq of each remaining char to be even.

Now both checks can be done in O(n) with early breaks as soon as we find a working l. Essentially we reduce our checking function used in binary search to O(1) with smartly maintaining the multisets by simple count arrays with linear search(instead of binary) on the minm l.

Submission:https://codeforces.me/contest/2069/submission/361582752

BledDest's blog