### salyg1n's blog

By salyg1n, 2 weeks ago, translation,

Hello everyone! We're very sorry for the delay >_<

We hope you enjoyed the tasks! Sorry for too tight limits in C so that Java solutions don't pass (actually one of our authors nickname used to be "java." :D), we'll hopefully do a better job next time! Feel free to leave your feedback in the comments.

1867A — green_gold_dog, array and permutation

Author: green_gold_dog

Tutorial
Solution

1867B — XOR Palindromes

Author: ace5

Tutorial
Solution

1867C-Salyg1n and the MEX Game

Author: salyg1n

Tutorial
Solution

1867D-Cyclic Operations

Author: ace5

Tutorial
Solution

1867E1-Salyg1n and Array (simple version)

Author: salyg1n

Tutorial
Solution

1867E2-Salyg1n and Array (hard version)

Author: salyg1n

Tutorial
Solution

1867F-Most Different Tree

Author: green_gold_dog

Tutorial
Solution
• +107

 » 2 weeks ago, # |   +71 If you were wondering why am I an author but didn't make any problems: a day before the contest we decided to replace my task F (because I hate it) and to give "Most Different Tree" instead, hopefully it fits better (I guess we'll never know) :]
•  » » 13 days ago, # ^ |   +7 What's the logic for this comment to gather so many upvotes?
•  » » » 13 days ago, # ^ |   +68 Become Red on CF
 » 2 weeks ago, # | ← Rev. 2 →   +11 Video Editorial for A-E2 ...I hope it will helpful to Newbies and Pupils..! YOUTUBE EDITORIAL LINK
 » 2 weeks ago, # | ← Rev. 2 →   +10 In 1867E2 - Salyg1n and Array (hard version) it is impossible to achieve $2k < x$ if $n \leq 2k$. However, in fact we do not need this condition. The second part of the solution still works in the case $k < x \leq 2k$.
 » 13 days ago, # |   +21 E2 can be actually done in 51 operations instead of 57.When k divides n then it only takes n/k queries, i.e 50 at max.Otherwise, we can separate the first n*[n/k] elements and the remaining n%k elements. Since, n%k is even then we can divide those remaining elements in 2 parts of (n%k)/2 size. First, we ask a query where the i+k-1=n-(n%k)/2. Then after the subarray gets reversed, we again ask another query where i+k-1=n. Taking XOR of their outputs, the common elements gets nullified and we get our requried value.This takes [n/k]+2=49+2=51 queries.Submission E2
•  » » 13 days ago, # ^ |   +22 Nice solution!Here's a sort of visual proof of why this works:
•  » » 13 days ago, # ^ |   +33 Yeah, we know, our solution does 51 queries too. Number 57 is just cool. Also the limit of 51 quiries could be a hint
•  » » 13 days ago, # ^ |   0 Nice! Easy to understand!
 » 13 days ago, # |   +73
•  » » 13 days ago, # ^ |   0 lol
 » 13 days ago, # |   0 Disclaimer: I'm a stupid newbie code Note: Yet plz continue reading Many accepted solutions, including this official editorial solution, are giving answers other than the correct answer (1) for the following test case:  t=1 n=9 k=4 array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
•  » » 13 days ago, # ^ | ← Rev. 2 →   +5 The problem statement mentions both n and k will be even
•  » » » 11 days ago, # ^ |   +13 Yeah, you just answered your own question.
 » 13 days ago, # |   0 The necessity to learn C++ to literally write the same code for Problem C pisses me off. TLEs in Java :(
 » 13 days ago, # |   0 Thank you for editorial <3
 » 13 days ago, # |   0 runtime error @testcase3 for D, grateful if someone can find the error ! fk this shit mann! for _ in range(int(input())): n,k=map(int,input().split()) arr = [x - 1 for x in map(int, input().split())] if k==1: if arr==list(range(n)): print('YES') else: print('NO') else: memo={} def dfs(node,c): if node in memo: return memo[node] count[node]=c ch=arr[node] if count[ch] is None: local=dfs(ch,c+1) else: if abs(count[node]-count[ch])+1==k: local=True else: local= False memo[node]=local return local final='YES' for i in range(n): count=[None for _ in range(n)] ans=dfs(i,0) if ans is False: final='NO' break print(final) 
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 Python has a default maximum recursion depth of 1000. Since n is of the order 2e5, it is not possible to do it in a recursive fashion. Try writing your dfs using stacks or just use while loops.Note that you may also try increasing the recursion depth limit ( sys.setrecursionlimit(N) ) but that would just lead to MLE.
•  » » » 13 days ago, # ^ |   -10 what's MLE
•  » » » » 13 days ago, # ^ |   0 Memory limit exceeded
 » 13 days ago, # |   +1 It was possible to make problem E1 and E2 more interesting by pushing extra condition (n+k)%2==0.
 » 13 days ago, # | ← Rev. 2 →   0 In the problem 1867E2 — Salyg1n and Array (hard version) for a case where n = 3, k = 2 and a = [4, 2, 5] the answer should be 3. But the given solution in the editorial is providing the answer 6. The interaction is given below, 1 3 2 ? 1 6 ? 1 6 ? 1 6 ! 6 Can someone explain the case?
•  » » 13 days ago, # ^ | ← Rev. 2 →   +1 Read problem statement clearly , here n and k always even. And the information you got ,is not enough.
•  » » » 13 days ago, # ^ |   +1 Thank you. I should have been more careful.
 » 13 days ago, # |   0 Can someone please explain why was this submission skipped https://codeforces.com/contest/1867/submission/222952890 ? It have gotten AC on pretests and i also sent almost identical one (added pragmas) later and it got AC.
•  » » 13 days ago, # ^ |   +8 Because later you submitted another submission and it also passed pretests. Only your last AC submission is tested on sistests
•  » » » 13 days ago, # ^ |   0 OK, thanks. It wasn’t the case for previous contests as far as i remember though…
 » 13 days ago, # |   0 वीडियो स्पष्टीकरण A,B,C,D
 » 13 days ago, # |   0 223167780Can anyone give me an edge case which should give wrong answer for this code?
 » 13 days ago, # | ← Rev. 4 →   +18 I was too lazy to code some general tree enumeration for F, so I got a slightly different solution.Expand a little on the jury's observations. The answer always (except for $n=2$) looks like that: some tree that is not in $P(G)$, all its children are in $P(G)$ and there's a long bamboo attached to its root. The value of the answer is the sum of the sizes of the children.Now, recall the hashing part of the isomorphism check procedure. We take the isomorphism classes of all children of a vertex, sort them and get the class of the whole tree based on that list. Imagine building the answer with that procedure. The resulting list should not appear among the existing classes. However, during the procedure, all prefixes of the list have to appear among them. Otherwise, we could've taken that prefix as the answer.Thus, the answer looks like that: an existing subtree with another existing subtree attached to it as the last child. Additionally, the class of the last child should be not less than the class of the last child of the initial subtree.So the solution could look like that. Iterate over the existing classes as the initial tree, then iterate over them again as the last child. If the last child is smaller than the last element of the initial list, skip it. If the list with the new element appended appears among the existing classes, skip it. Find the smallest tree among everything that's left.Unfortunately, it's too slow as is. Let's optimize.The second condition is easy to circumvent. Find all existing lists that are the current one with one element appended. You can think of it as building a trie of these lists, then traversing it. Now, you can remove them from some structure of options, then find the best option, then add them back. That would be $O(n)$ removals and additions in total.The first condition is harder. I chose to abuse the fact the answer is really small. For each size, store the indices of the classes of all existing trees of that size in the increasing order. Now, we can iterate over the size of the option tree, then lower_bound for the index that is at least as large as the last element of the current list. If the iterator isn't at the end, update the answer and break. If you use a set for that, you can easily support the removals and additions as well.I believe, that is $O(n \cdot \mathit{ans} \cdot \log n)$. The submission is 222999827 if anyone is curious.
 » 13 days ago, # |   0 Can someone please explain why in the A problem I cannot use a multimap?
•  » » 13 days ago, # ^ |   0 I think you mixed up the position of the first element of the sorted array in the original array with the position of the first element of the original array in the sorted array.
 » 13 days ago, # |   0 Do anyone know 42th subtest of test 2 of problem D. I can not pass this anyway
 » 12 days ago, # |   +8 In the editorial of F it is said that "One can see that if we generate all trees of size up to 15 we will definitely find T there."How do you prove that we only need trees with a size no more than 15?
•  » » 12 days ago, # ^ | ← Rev. 3 →   +10 Because the number of rooted trees of size 15 is more than $87000$. $87000 \cdot 15 > 10^6$, so the initial tree can't have all these trees as subtrees. Here's the sequence
 » 12 days ago, # | ← Rev. 2 →   0 ace5, can you please tell me for the problem 1867D - Cyclic Operations what is the motivation for converting this problem into graph . Its just something outside of my thought process that this problem can also be thought like this. So how we actually know of converting it. Is it by just applying other concepts and then checking if they are not working then try another some new concept. Because i have been thinking like that for the answer to be YES , all the elements in the array must have been permutation of the positions and then are overlapped in a unique fashion and if this condition does not hold somewhere in between then the answer will be NO. But i do not know how we will implement it and just went blank after that. Can you please explain it will be so kind of you as i have spent a significant amount of time but still have no idea.
•  » » 11 days ago, # ^ |   +13 Practice
 » 12 days ago, # | ← Rev. 2 →   +3 A much more sane way to implement F is to recognize that you can enumerate all RBS of length 28 to cover the euler tour of every tree of size 15 (with repetitions); there are 2.6e6 of them which barely fits in the TL. However, you can also use this method for sizes up to 14 and just use random to solve size 15 (less than 80% of size 15 trees can be subtrees), which should reduce the runtime by a factor of 3.6 and comfortably pass.https://codeforces.com/contest/1867/submission/223380152
 » 11 days ago, # |   0 I want to ask In problem E: how come this sample is accepted n=3 k=2 and the array is 1 2 4 the judges code is answering 6 when in fact it should be 7 but there is no definite way to know the answer.
•  » » 10 days ago, # ^ |   +15 Notice that problem statement states n and k are even numbers. It can be shown that this ensures uniqueness of the answer.
 » 10 days ago, # |   0 In E1/E2, if anyone is wondering if solution for any cases where n & k are not both even is possible or not. I tried some examples and found out that I can construct a solution if k is odd (doesn't matter whether n is odd or even). But when k is even we can prove that solution is not possible if n is odd. The proof is as follows:Initially, we can only get xor of even subarray sizes. Now, let's say there are 2 sets of even size (say x & y). And t elements are common in these 2 sets, after taking xor of these 2 sets we again get new set of even size i.e. x + y — 2t. So, constructing a set of odd size i.e. n is not possible when k is even.Note: Can someone please confirm my claim or prove me wrong?
 » 8 days ago, # |   0 For problem F, I can't understand why I got wa for this code. Who can help me find out the problem please qwq. https://mirror.codeforces.com/contest/1867/submission/223794337
 » 7 days ago, # |   0 Hi everyone its really hard for me to understand problem D. I have watched many videos and editorial but not able to understand problem D . Can anyone tell me what should I do?
•  » » 6 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } So, the idea is first to understand how the operation works. You can try some examples with 1 2 3 4 and play with it(reverse order of them). You will realise: you cant get a number on its index(1 cant stay on first index, 2 on second...), and you must go in cycle to come back to 1(if you set first index to 3, index 3 must be 2 or 4 lets say 4, index 4 can be only 2 and index 2 1). After that try to do example: k = 4, array = 2 3 4 1 1, you will understand that you can do 1 operation to get 1 on fifth index and after that do operation on first 4 to solve them. So the conclusion is: if you have a good cycle of 4(cycle where all numbers remain in their indexes:3 5 4 5 1 5 5 5 example where indexes 1 3 4 5 are a good cycle, you can first solve for all other indexes that have one of those 4 numbers and then solve the cycle), but if you have a cycle of 3 when k is equal 4 you cant solve the problem(you can make only 4 cycle rotations). So the problem becomes finding good cycle indexes and all other indexes that have good cycle indexes as value and hoping that after finding all of those whole array is done. So we need to find cycles between numbers and their connections to rest of the array which is nothing more than a graph.