Vladosiya's blog

By Vladosiya, history, 13 months ago, translation, In English

1800A - Is It a Cat?

Idea: Vladosiya, MikeMirzayanov

Tutorial
Solution

1800B - Count the Number of Pairs

Idea: myav

Tutorial
Solution

1800C1 - Powering the Hero (easy version)

Idea: Vladosiya

Tutorial
Solution

1800C2 - Powering the Hero (hard version)

Idea: Vladosiya

Tutorial
Solution

1800D - Remove Two Letters

Idea: MikeMirzayanov

Tutorial
Solution

1800E1 - Unforgivable Curse (easy version)

Idea: Aris, talant

Tutorial
Solution

1800E2 - Unforgivable Curse (hard version)

Idea: Aris, Vladosiya

Tutorial
Solution

1800F - Dasha and Nightmares

Idea: Gornak40

Tutorial
Solution

1800G - Symmetree

Idea: Vladosiya

Tutorial
Solution
  • Vote: I like it
  • +46
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

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

UPD: Here it is

»
13 months ago, # |
  Vote: I like it -32 Vote: I do not like it

C1 was easier than A and B.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    no it wasnt, A is easier

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why?? i spent apporximately 2 hour solving C1 by using dp 2-D.however, i can not complete it :)) maybe i thought too much

»
13 months ago, # |
  Vote: I like it +22 Vote: I do not like it

StringForces

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      what is FST . sorry i m a newbie

»
13 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    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

»
13 months ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

D&G two hashing problems!

»
13 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good tutorial. Thanks for explaining the solutions properly.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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"

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 !

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Really good contest!

»
13 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Literally StringFORCES!

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Great tutorial!!!!

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It aims to pick words that miss the certain letter c

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it
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();
   }
}

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.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    this would have given mle in cpp as well

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why so?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    try to understand in graph. What are the possible connected indexes where we can adjust the elements in any permutation. if you make graph of the indexes for k then there are exactly 2+(n-2*k) connected components where (n+2-2*k)-1 components are single node graphs which means these indexes cannot be swaped in anyway so we check that these indexes must have same characters other wise we can never make s to t. Indexes which are not part of these indexes are interconnected (which means all these indexes belong to single connected components) so all characters of these indexes can be adjust(or swap) in any permutation so we adjust these characters according to t. Note : for n>=2*k: all indexes are interconnected so it is always possible to convert s to t for n<k : all indexes are not interconnected so ans is yes only if s=t otherwise it is never possible to convert s to t.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

#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;
}
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So many problems based on strings

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a much easier solution to E. You don't need to use anything except one map container. Refer my submission for the same:- 244026758

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I dont understand for problem E when i >= k or i + k < n it doesn't guarantee the possibility of moving the letter in any direction by 1 because if i = k we aren't guaranteed to be able to move i to the right if i also equals n.

Can someone prove it to me? Thank you in advance