Разбор Educational Codeforces Round 174

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	156
6	adamant	152
6	djm03178	152
8	Qingyu	151
9	luogu_official	149
10	awoo	147

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

If we make the given string palindrome, then it must have equal no. of characters in the first half and the second half, so solution goes as follows, for every character we find the freq. of them in first and second half and then equalize accordingly.

Comments (69)

Write comment?

FeiWuLiuZiao

41 hour(s) ago, # |

← Rev. 2 →

+39

rating update when

Spoiler

→ Reply

termindev

40 hours ago, # ^ |

System testing is running right now.

esh_war2

39 hours ago, # ^ |

Square__Head

35 hours ago, # ^ |

next year

RishiCodes

34 hours ago, # ^ |

probably lol

seems like it...

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

29 hours ago, # ^ |

makes sense

future_zyl

40 hours ago, # |

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

38 hours ago, # ^ |

define "count the sequence"?

andrei_n

36 hours ago, # ^ |

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.

Harsha_12354

same I too got 7 TLE

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

25 hours ago, # ^ |

Thanks, got it

dontkno67

21 hour(s) ago, # ^ |

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?

TusharGupta11

Do you know some resources using which i could practice such dp on subsequences problems??

10 hours ago, # ^ |

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.

_whimsical_

thanks, this was much more intuitive than the dp solution

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

30 hours ago, # ^ |

Go to luogu, I think quite a few Chinese competitive programmers solve problem sets on that

old_man_die_hard

+25

Super slow editorial!

Luckwet

+14

Lighting slow editorial

But the problems were very interesting

nocap

39 hours ago, # |

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

case3

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

-adhd-

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

32 hours ago, # ^ |

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

vventi

+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

38 hours ago, # |

Can someone explain the dp transition equation of problem C.

I did it there if you want to take a look : https://codeforces.net/blog/entry/139774?#comment-1248589

26 hours ago, # ^ |

thx. very helpful

szpu_ark

I think in question B, it's easy to misunderstand. That is, select a cell that wants to meet no connections around it

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.net/contest/2069/submission/306731691. Sorry for my bad English

TraudeIOI

-26

broken Englash ahh shi

anupam_713

9 hours ago, # ^ |

thanks!!

maruf004

34 hours ago, # |

Any solution of C without dp?

redreoicy

33 hours ago, # ^ |

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

20 hours ago, # ^ |

Can you please explain me the part where you are calculating the "ways"?

18 hours ago, # ^ |

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?

17 hours ago, # ^ |

Your idea would work, if there was exactly one 1 at the start of the array and no 1s anywhere else.

LightWave

14 hours ago, # ^ |

I actually tried something similiar, and it tled :( The reason is definitely obvious. 306989184

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

31 hour(s) ago, # ^ |

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;

thankyou, got it!!

33 hours ago, # |

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

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

Lvl_Insane

31 hour(s) ago, # |

← Rev. 3 →

My solution for problem is different from the editorial : 306925674

while equalizing, we can keep track of min index and max index in between we have to shuffle all characters. (this is done after removing already equal characters from start and end)

T.C. -> O(26*n) and can be easily done in O(n) but the current T.C. is fast enough to pass

vedic86

21 hour(s) ago, # |

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

BledDest's blog