Codeforces Round 855 (Div. 3) Editorial

#	User	Rating
1	Benq	3783
2	jiangly	3666
3	tourist	3611
4	Um_nik	3536
5	inaFSTream	3477
6	fantasy	3468
7	maroonrk	3464
8	QAQAutoMaton	3428
9	ecnerwala	3427
10	Ormlis	3396

#	User	Contrib.
1	Um_nik	184
2	adamant	178
3	awoo	177
4	nor	169
5	maroonrk	165
6	-is-this-fft-	164
7	antontrygubO_o	152
8	ko_osaga	151
9	dario2994	150
10	SecondThread	149

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    transform(s.begin(), s.end(), s.begin(), [] (char c) {
        return tolower(c);
    });
    s.erase(unique(s.begin(), s.end()), s.end());
    cout << (s == "meow" ? "YES" : "NO") << "\n";
}

int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

1800B - Count the Number of Pairs

Idea: myav

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 26;

void solve(){
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int>big(N, 0), small(N, 0);
    for(auto &i : s){
        if('A' <= i && 'Z' >= i) big[i - 'A']++;
        else small[i - 'a']++;
    }
    int answer = 0;
    for(int i = 0; i < N; i++){
        int pairs = min(small[i], big[i]);
        answer += pairs;
        small[i] -=pairs; big[i] -= pairs;
        int add = min(k, max(small[i], big[i]) / 2);
        k -= add; answer += add;
    }
    cout << answer << endl;
}
int main(){
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

1800C1 - Powering the Hero (easy version)

Idea: Vladosiya

Tutorial

Solution

def solve():
    n = int(input())
    s = [int(x) for x in input().split()]
    ans = 0
    buffs = [0] * n
    for e in s:
        if e > 0:
            buffs += [e]
            j = len(buffs) - 1
            while buffs[j] < buffs[j - 1]:
                buffs[j], buffs[j - 1] = buffs[j - 1], buffs[j]
                j -= 1
        else:
            ans += buffs.pop()
    print(ans)


t = int(input())
for _ in range(t):
    solve()

1800C2 - Powering the Hero (hard version)

Idea: Vladosiya

Tutorial

Solution

from queue import PriorityQueue


def solve():
    n = int(input())
    s = [int(x) for x in input().split()]
    ans = 0
    buffs = PriorityQueue()
    for e in s:
        if e > 0:
            buffs.put(-e)
        elif not buffs.empty():
            ans -= buffs.get()
    print(ans)


t = int(input())
for _ in range(t):
    solve()

1800D - Remove Two Letters

Idea: MikeMirzayanov

Tutorial

Solution

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int res = n - 1;
    for (int i = 1; i + 1 < n; ++i) {
        if (s[i - 1] == s[i + 1]) {
            res--;
        }
    }
    cout << res << '\n';
}

int main(int argc, char* argv[]) {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
}

1800E1 - Unforgivable Curse (easy version)

Idea: Aris, talant

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back


void slow_solve(int n, int k, string s, string t) {
    set<string> was;

    queue<string> q;
    q.push(s);
    was.insert(s);

    auto add = [&](string& s, int i, int j) {
        if (i >= 0 && i < j && j < n) {
            swap(s[i], s[j]);
            if (!was.count(s)) {
                was.insert(s);
                q.push(s);
            }
            swap(s[i], s[j]);
        }

    };

    while (!q.empty()) {
        s = q.front(); q.pop();
        for (int i = 0; i < n; ++i) {
            add(s, i, i+k);
            add(s, i, i+k+1);
            add(s, i-k, i);
            add(s, i-k-1, i);
        }
    }
    cout << (was.count(t) ? "Yes" : "No") << '\n';
}

void solve() {
    int n,k; cin >> n >> k;
    string s; cin >> s;
    string t; cin >> t;

    if (n <= 5) {
        slow_solve(n, k, s, t);
        return;
    }
    map<char, int> cnt;
    for (char c : s) {
        cnt[c]++;
    }

    for (char c : t) {
        cnt[c]--;
    }

    bool ok = true;
    for (auto [c, x] : cnt) {
        ok &= x == 0;
    }
    cout << (ok ? "Yes" : "No") << '\n';
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        solve();
    }
}

1800E2 - Unforgivable Curse (hard version)

Idea: Aris, Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back

void solve() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    string t; cin >> t;
    vector<int> cnt(26, 0);

    bool ok = true;
    for (int i = 0; i < n; ++i) {
        if (i >= k || i+k < n){
            cnt[s[i] - 'a']++;
            cnt[t[i] - 'a']--;
        } else {
            ok &= s[i] == t[i];
        }
    }

    cout << (ok && count(all(cnt), 0) == 26 ? "YES" : "NO") << '\n';
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        solve();
    }
}

1800F - Dasha and Nightmares

Idea: Gornak40

Tutorial

Solution

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,avx,fma,bmi2")

#include <bits/stdc++.h>
#include <immintrin.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
//#define int long long
#define all(arr) arr.begin(), arr.end()
#define multitest() int _gorilla_silverback; cin >> _gorilla_silverback; while (_gorilla_silverback --> 0)
#define pikachu push_back
#define ls(id) (id << 1 | 1)
#define rs(id) ((id << 1) + 2)
#define sqr(x) ((x) * (x))
#define dlg(x) (31 - __builtin_clz(x))
#define ulg(x) (32 - __builtin_clz(x))

typedef pair<int, int> ipair;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 200200;
const int L = 26;

int n;
string srr[MAXN];
int arr[MAXN], brr[MAXN], crr[MAXN];

void build() {
	for (int i = 0; i < n; ++i) {
		for (char c: srr[i]) {
			arr[i] ^= (1 << (c - 'a'));
			brr[i] |= (1 << (c - 'a'));
		}
	}
}

long long calc(int c) {
	int k = 0;
	for (int i = 0; i < n; ++i)
		if (brr[i] >> c & 1 ^ 1) crr[k++] = arr[i];
	sort(crr, crr + k);
	int mask = -1 & ((1 << L) - 1) ^ (1 << c);
	long long ans = 0;
	for (int i = 0; i < k; ++i) {
		auto itl = lower_bound(crr, crr + k, crr[i] ^ mask);
		auto itr = upper_bound(crr, crr + k, crr[i] ^ mask);
		ans += itr - itl;
	}
	return ans >> 1LL;
}

long long solve() {
	long long ans = 0;
	for (int c = 0; c < L; ++c)
		ans += calc(c);
	return ans;
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> srr[i];
	build();
	cout << solve() << endl;
}

1800G - Symmetree

Idea: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>

#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long double ld;
typedef long long ll;

using namespace std;

mt19937 rnd(time(nullptr));

const int inf = 2e18;
const ll M = 1e9;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;

int last;
map<vector<int>, int> eq;
map<int, bool> symmetrical;

int dfs(int v, int p, vector<vector<int>> &sl){
    vector<int> children;
    for(int u: sl[v]){
        if(u == p) continue;
        children.emplace_back(dfs(u, v, sl));
    }
    sort(all(children));
    if(!eq.count(children)){
        map<int, int> cnt;
        for(int e: children){
            cnt[e]++;
        }
        int odd = 0, bad = 0;
        for(auto e: cnt){
            if(e.y & 1){
                odd++;
                bad += !symmetrical[e.x];
            }
        }
        eq[children] = last;
        symmetrical[last] = odd < 2 && bad == 0;
        last++;
    }
    return eq[children];
}

void solve(int tc){
    int n;
    cin >> n;
    eq.clear();
    symmetrical.clear();
    eq[vector<int>(0)] = 0;
    symmetrical[0] = true;
    last = 1;
    vector<vector<int>> sl(n);
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].emplace_back(--v);
        sl[v].emplace_back(u);
    }
    cout << (symmetrical[dfs(0, 0, sl)]? "YES" : "NO");
}

bool multi = true;

signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

import java.util.*; import java.io.*; public class RemoveTwoLetters { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out)); int t = Integer.parseInt(br.readLine().trim()); while (t-- > 0) { int n = Integer.parseInt(br.readLine().trim()); String s = br.readLine(); Set<String> set = new HashSet<>(); for (int i = 1; i < n; i++) { StringBuilder sb = new StringBuilder(s.substring(0, i - 1)); sb.append(s.substring(i + 1)); set.add(sb.toString()); } pw.print(set.size()); pw.print('\n'); } pw.flush(); pw.close(); br.close(); } }

#include"bits/stdc++.h" using namespace std; #define ll long long #define m 9007199254740991 void solve() { int n; cin >> n; string s; cin >> s; vector<ll> hash1(n + 2), hash2(n + 2); for (ll p = 1, i = 0; i < n; i++) { hash1[i + 1] = (hash1[i] + (((s[i] - 'a' + 1) * p) % m)) % m; p = (p * 31) % m; } for (ll i = 2, p = 1; i < n; i++) { hash2[i + 1] = (hash2[i] + (((s[i] - 'a' + 1) * p ) % m)) % m; p = (p * 31) % m; } unordered_set<ll> st; for (int i = 2; i <= n; i++) { ll temp = (hash2[n] - hash2[i] + m) % m; temp = (temp + hash1[i - 2]) % m; st.insert(temp); } cout << st.size() << '\n'; } int main() { int tc; cin >> tc; while (tc--) { solve(); } return 0; }

Comments (112)

Write comment?

Vladosiya

3 months ago, # |

← Rev. 2 →

+12

P.S. I haven't found good articles about hashing root trees so I'll post one soon.

UPD: Here it is

→ Reply

aonbel

3 months ago, # ^ |

Isn't that blog enough for understanding hashing root trees? http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html

I just hope to make a bit better topic with showing approaches as main point.

abdelrahman_samir

could u check my solution for e1 it gives a wrong answer when a char array is used but accepted when a string is used

tulip9

-32

C1 was easier than A and B.

Dauzhen

no it wasnt, A is easier

kvcodereaper

Same for me! I suck at strings gotta practice.

M-uwu

+22

StringForces

itachi_fam

i dont understand BFS solution of task E can anyone explain please?

Raito_Yagami

There is an observation that if you turn the string to a graph where the edges are like this: $$$(i,i+k)$$$ when $$$i+k \le n$$$ , $$$(i,i+k+1)$$$ when $$$i+k+1 \le n$$$. So you can swap characters in indices in the same component however you like. You can try a few examples if you want.

thanks

economist

F. i guess it should be bj = bi XOR (1<<26 -1) XOR (1<<k)

brownfox2k6

Except C1, C2 and F, all other problems are about strings

jahid_hridoy

F is also string

ah sorry, I meant except C1, C2 and G

djay24

So many FST's on A, such a tricky easy question !

tn757

Amazing, I have never seen so many FST on a problem A

So many FST's on F too, jiangly and SSRS got hacked, I don't feel too bad now after getting hacked, XD

meow_power

what is FST . sorry i m a newbie

Failed System Test

Chifwin

What does count(all(cnt), 0) == 26 mean in solution of E2? What is the logic behind this? Can anyone tell me, please

← Rev. 4 →

He is simply checking if count of all letters that are not in the interval [n-k; k] is equal. Count(all(cnt), 0) returns number of zero elements in the array.

So, with this line: cnt[s[i] - 'a']++; he is counting letters in string s, and with this: cnt[t[i] - 'a']--; he is deleting letters from cnt, and when all letters were processed there will be only zeros in cnt if counts of letters were equal

Thanks!)

Tom66

← Rev. 3 →

D&G two hashing problems!

+19

E can be solved using disjoint set union. Just check whether each connected component are the same.

tavishim2005

can u plz elaborate more on this?

195970968

Traverser_25

Can we solve c1 and C2 like this:-

1) sort every non zero segment in place , intialiazed int bal=0; 2)iterate end of array if we get zero do bal++; else if bal>0 ad current element to ans and do bal--;

Will this work? How can we implement this?

LUFFY_02

It can be implemented, but will be quite annoying implementation. We have to first store indexes of array where 0 comes, then we have to sort for srt(arr.begin()+start_0,arr.begin()+end_0) for all range of that 0. Then j pointer as last positive number before a 0 and so ans so. That is as per your logic.

And if you are not good with priority_queues, we can implement double stack, 1 stack for storing numbers greater than 0 and other to push curr_max every time we get a number greater than 0.

I upsolved using priority queue,i was stuck on this implementation. Thanks ,sure this implementation is annoying

+10

Thank you for the contest, loved all the questions. Kudos to authors, coordinators. I may finally become expert after being a specialist for 6 months now, :')

__HiM_001

Good tutorial. Thanks for explaining the solutions properly.

ppip

G is too obsivious for people who know hash of trees.

YocyCraft

I thought my solution of G could fail on system test by hash-collision, but unexpectedly my solution of A got FST. There should be something like "eow" in the pretest of A.

Looks like this would have been my expert round had I not made a stupid error and got a penalty for overflow on problem C. Still, I won't cry about +100 delta :)

SirIronHeart

Let's push it today.

FlyCube

Can not understand why O(26⋅n⋅log n) for F got TL. Can anyone suggest what I am doing wrong? https://codeforces.com/contest/1800/submission/195673951

yuexiAOvO

all you need is to lower your constant. change bitset to long long or using unordered_map instead of map. it finally runs 2000ms

Niket_Bahety

same my solution of O(26.n.log n) is also gave TLE on test 26 195813129 Can somebody please explain why is this happening? (also unordered map is also not working)

In your case I think that problem is that it is O(26 * 26 * n * log n) instead of O(26 * n * log n). Upd, actually it is O(26 * 26 * n + 26 * sum_of_len + 26 n * log n), but probably it also should be fine.

You are right it is because of the constant. If I use find from std::map instead of operator[] it pass tests. https://codeforces.com/contest/1800/submission/195806091 But anyway too close to TL.

yes, I also tried find instead of [] and it passed, can you please tell why is this happening shouldn't both take same O(log n) time?

-10

Vladosiya Could you consider changing the time limit for F? The map based solution should also pass tests. It is div3 you should not care about constant too much.

__Clouds

I agree

mt_cs

I can't believe I failed the problem A. Checking the order wasn't enough. I should've checked whether it repeated too. Making it unique was also simpler.

SpongeCodes

did not understand the "abudance" example in E1. Can anyone explain it to me?

alexiuscp

4 weeks ago, # ^ |

It is saying you can essentially swap two adjacent characters without affecting the rest of the string (provided that n>=5), by these steps.

say I want to swap 'bc' axxbc cxxba bxxca axxcb

I believe in the example there is a typo,"budka" should've been "budca"

panwar2001

Is there any particular name of hashing tree algorithm used in problem G also thanks for good editorial.

RobinFromTheHood

D is a nice problem. I worried about the cases where 2 removals are not overlapping. Did it worry you too? Consider: R1+R2+S+R3+R4 where S is a string, and removals of R1+R2 and R3+R4 gives the same results: S+R3+R4 = R1+R2+S then S[even index]=R1 and S[odd index]=R2. If S has even length, R3=R1 and R4=R2; if S has odd length, R3=R2 and R4=R1. Thankfully, this shows checking overlapping removals will cover the non-overlapping ones too.

Folka

A,B,C1,C2,D were leaked on YT. This isn't fair. people think and try to solve and may get negative delta and others just copy and paste and get positive delta. I think Codeforses must prevent the new accounts and that solved less than N of problems in problem set to participate in Div 4 or 3

like that one : 195674461 which is for Mohamed_712 and got +44 and this answer is 100% simmilar that was leaked !

Mohamed_712

newman111

[deleted] Oh, my method is the same with editorial.

NekoYellow

Could someone explain why we need to do "1&" and "-1&" in calc() in the solution of problem F? I thought that they wouldn't take any effect since 1 & 1 = 1 and 1 & 0 = 0, but removing them indeed resulted in WA. Here's the WA submission: 195819749

Oh I think I know why. The "-1&" is unnecessary but the "1&" is not. Sorry for the stupid question

xyz_000

in the -1& case, i guess it just trying to find the mask where only the position of letter c is unset. So in my view, -1& is completely not required.

NO__OB

How to proof C? I am not convinced even the solution magically works.

As we know all the cards before we take action, we can just discard those that aren't good enough. That ensures the greedy solution using priority queue.

swseverance

5 weeks ago, # ^ |

Adding to this explanation.. the priority queue doesn't tell us which hero will get which card, it simply tells us whether or not a card will be given to some hero. For example, assume our list is 1 8 3 0 0

When we reach the first hero our priority queue contains {8, 3, 1} and we think to ourselves we will be using 8 because it is the highest card we have seen. We will give it to some hero but it might not be the first hero.

When we reach the second hero our priority queue contains {3, 1} and we think to ourselves we will be using 3 as well. We've seen two heroes and we want to give them the two highest cards.

After we are done iterating over the list we can visualize a new list containing just the cards we are going to use, as well as the heroes, which would be 8 3 0 0.

At that point you can actually see which hero gets which exact card by using a stack.

joelgun14

I solved G without using hashing, but instead I "sorted" the subtrees in a certain order. Did I do a fakesolve? or is it a valid method?

Nightmaresss

I also solve G without hashing, it seems like we have similar idea, I scan nodes in depth ascending order to maintain some equivalent groups among them.

Lauane

Really good contest!

https://codeforces.com/contest/1800/submission/195826604, isn't the tc of this code same as the tc suggested for problem F? Why did it TLE? Can anyone help?

Andrei_Kuz

When viewing your code, I saw two variables: ev and od. They eat a lot of time and memory, because this is a hashmap array, try to pull them apart a little and reformat the code. If it's not clear what I'm saying, then here's an idea: do not cycle(1...n) cycle (0...26) and vice versa cycle(0...26) cycle(1...n) then you can remove huge arrays and put the use of hashmap into the cycle itself, made the code faster. Sorry for grammatical errors, I do not know English.

Check this. 195837788 sorry for replace.

Thanks a lot, a minor tweak but it worked!

AlphaUranUS

Literally StringFORCES!

enerneo

Someone pls explain this conclusion in the last paragraph of tutorial of problem F:
To count the number of pairs that include our word, we need to count the number of words with the characteristic $$$b_j=b_i\oplus(2^{26} − 1)$$$.

Letter with odd count will be represented as digit 1, and that with even count will be digit 0. To find pair (i, j) which meets the condition, we should check if they miss a certain letter and all the remaining 25 letters have odd count. Note that $$$odd = odd + even$$$ is similar to $$$1 = 1 \oplus 0$$$. So the pairs we are finding are (i,j) which have $$$b_i \oplus b_j = 2^{26}-1$$$ (the right side is 26 1's). (In the implementation, we actually count words meeting $$$b_j = b_i \oplus ((2^{26}-1) \oplus 2^{c})$$$ to handle the missing letter $$$c$$$.)

I heard that many people did not want to understand priority_queue, so I can advise multiset. Or learn to write yourself at least a Treap).

_Papaya_

Great tutorial!!!!

madghostek

I had dp-ish thinking in D: Assume we know there are dp[i] ways for for some string S of length i, now we can add some new letter x at end, and we get S+x. Compared to just S not much changes, if we had dp[i] different ways, we can slap x at the end of all of them, and we still get dp[i] ways, however there's the new case where we remove last two characters from S+x... is this case new? When is it new? Since it's like we only removed last character from S, it will be different than anything what we have right now, if S[i-1] is not x. So: dp[i+1]=dp[i], +1 if S[i+1]==S[i-1]

What is the meaning of this line in solution F if (brr[i] >> c & 1 ^ 1)

It aims to pick words that miss the certain letter c

For example c = 2 which indicates the letter c.

Consider string 01100 the last from 2 bits indicates c. brr[i] >> c will equate the value to 011. brr[i] >> c & 1 does 011 & 001 which gives value one gives c is available. xoring the value with 1 will make it 0. so we don't consider this string because it has letter c.

ihnaqi

I wrote this java solution to D, I got out of memory exception on test case 5, this could be optimized, reading insights about my solution would be fun. Please comment.

RealBossCoder

same solution and same mle on test 5, except i used just string and scanner instead of those fancy things . Maybe pupil is not so close

That is not fancy thing this makes java IO faster, scanner sucks when on bulk IO.

yadavDipesh

this would have given mle in cpp as well

Why so?

SleepyOverlord

You are trying to store 200 000 strings of size 200 000 in the memory. You would need 4 * 10^10 bytes of memory to do that, which is about 40 GB. Not to mention that substring has linear time complexity, so your overall solution is quadratic and would TLE even with enough memory.

quilir

What does the -1 & do inside the F solution? For me it looks like no-op because -1 has 1111...111 binary representation and bitwise-and with such number shouldn't change the second number

It's just my understanding so that someone can point out what is wrong with it — I don't know much about bitwise operations

It does nothing and removing it won't have any problem. Here's a such AC code: 195838110

adarshk28

10 days ago, # ^ |

Can you explain why do we need to keep distinct maps based on parity of lengths? As per my understanding, if we can find two strings such (b_i ^ b_j) = 25, won't the odd length of the s_i.s_j concatenation hold already? In that case, do we really need to count masks of odd length strings and even length strings separately?

Tsuki_Kun

Can someone please tell me why my submission 195888152 with unodered_map doesn't work while the solution with map 195888396 works.

KushagrJaiswal

https://codeforces.com/blog/entry/62393

Simply use map/set instead of unordered_map/unordered_set, unless you want to use a custom hash function.

Actually, it has nothing to do with hash collisions. When you iterate over your map you add new elements by using operator[]. This leads to visiting some characters multiple times in the case of unordered maps. By iterating over a copy of the map your code gets accepted: 196522048

I'll keep that in mind. Next time for sure.

laki09

When it comes to B, why are we adding min(k,max(small[i],big[i])) / 2 I don't think we need to divide by 2. For example if we have 2 big letters(there are no small letters) and k = 1, min will return 1 and after division we will get 0 even though we can make one whole pair.

You're right, I think the formula is wrong in text of solution, but in code its correctly $$$\min\left(k,\frac{\max\left(small\left[i\right],big\left[i\right]\right)}{2}\right)$$$

Epilogue

F is easy but I didn't solve it ontime, otherwise I would be Expert now :V

Aditya_Prakash_59

1800F - 31 - Dasha and Nightmares I tried solving it using bitsets in C++ but it ended up giving WA on TC3.Can anyone help me with my approach. 195952648

In tutorial for F: "Observation 1: the product of odd numbers is odd, so the condition for the length of nightmare is automatically completed." What does this have to do with concatenation? shouldn't we be checking if sum is odd?

Since the number of different letters in the final string is exactly 25 (i.e. odd) and the number of occurrences of each letter is odd, therefore the length of the final string is odd (odd numbers summed up an odd number of times gives an odd number). So, we don't have to worry about satisfying this condition separately, as it will be satisfied automatically.

oh okay, i thought it refeers to the first condition

bashNewbie

Is the argument given in the tutorial for D sufficient? i.e. what about potential over counting (the argument only considers consecutive positions)? Or is this obvious?

puspendra_09

In problem 1800E2 — Unforgivable Curse (hard version) it is enough to check if index of mismatching character in string s and string t is within the limit k <= index <= n — (k + 1). accepted Code

071_Prashant

Can someone explain why am I getting Wrong Answer in Problem F by using unordered_map and Accepted using map.

MAP Solution

UNORDERED MAP Solution

lefegat

https://en.wikipedia.org/wiki/Hash_collision

Actually, it has nothing to do with hash collisions. When you iterate over your map you add new elements by using operator[]. This leads to visiting some masks multiple times in the case of unordered maps. By iterating over a copy of the map your code gets accepted: 196526230

Thanks. But I'm still wondering that order of elements in unordered map changes while traversing as I was not updating the map, just traversing it.

If you call operator[] on an element that didn't exist before in the map, it gets created. As the map is unordered, you don't know where it gets inserted in the traversing order.

relentless69

Why is it that in problem D just checking ith and (i+2)th characters continuously gives the right answer? It doesn't seem that intuitive to me. Can anyone explain?

Hey just check that

When we remove first and second two letters second letter is removed both times. If first and third letter is same it produces same results when removing first two and second two.

Example when i and i + 2 are equal "aaab" First two letters removed gives "ab" Second two letter removed gives "ab"

So here we reduce by ans by 1 because ab is already produced.

Example when not "aabb" First two letters removed -> "bb" Second two letter removed -> "ab"

Here we don't. When both are not equal it produces different outputs It doesn't matter what other parts of string consists of.

Hey did he write evenness in b in the explanation and used b as availability in the code? (Problem F)

insaneshawki

can anyone tell why this solution is not working for solution of A? https://codeforces.com/contest/1800/submission/197229297#:~:text=Judged-,197229297,-Practice%3A

yoloo123

tried really hard but i coulden't understand the tutorial of E1 and E2. Could someone please explain the logic. Thanks :((

is it true that we can swap any char with any other char in the string given that i-k>=0 and i+k<n?

nishu2002

Here is my solution for problem F. Can anybody tell me where am I getting wrong? My submission link

greenleafone7

I'm not sure how the calc function does what it does. Specifically why subtracting itr and itl provides the number of pairs that do not contain c!

imtheonly1

5 weeks ago, # |

I solved D with hashing but it required a huge prime;204035708

H-1

So many problems based on strings

B_Consistent

25 minutes ago, # |

In Promblem D,
Lets X(i,i+1) = string obtained after chars at index i,i+1 removed
Then Why X(i,i+1) and Y(j,j+1) are guarenteed to be distinct ? Why cant they be same ?

Vladosiya's blog