salyg1n's blog

By salyg1n, 14 months ago, translation, In English

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
  • Vote: I like it
  • +107
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +71 Vote: I do not like it

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

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

Video Editorial for A-E2 ...I hope it will helpful to Newbies and Pupils..! YOUTUBE EDITORIAL LINK

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

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

»
14 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

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

    Nice solution!

    Here's a sort of visual proof of why this works: image

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

    Yeah, we know, our solution does 51 queries too. Number 57 is just cool. Also the limit of 51 quiries could be a hint

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

    Nice! Easy to understand!

»
14 months ago, # |
  Vote: I like it +73 Vote: I do not like it

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

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]

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

Thank you for editorial <3

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

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

    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.

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

It was possible to make problem E1 and E2 more interesting by pushing extra condition (n+k)%2==0.

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

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?

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

    Read problem statement clearly , here n and k always even. And the information you got ,is not enough.

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

      Thank you. I should have been more careful.

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

Can someone please explain why was this submission skipped https://codeforces.me/contest/1867/submission/222952890 ? It have gotten AC on pretests and i also sent almost identical one (added pragmas) later and it got AC.

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

    Because later you submitted another submission and it also passed pretests. Only your last AC submission is tested on sistests

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

    bhaiya i watched the video but not able to get the B what should i do

»
14 months ago, # |
Rev. 4   Vote: I like it +18 Vote: I do not like it

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.

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

Can someone please explain why in the A problem I cannot use a multimap?

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

    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.

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

Do anyone know 42th subtest of test 2 of problem D. I can not pass this anyway

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    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

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

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.

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

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.me/contest/1867/submission/223380152

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

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.

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

    Notice that problem statement states n and k are even numbers. It can be shown that this ensures uniqueness of the answer.

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

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:

Note: Can someone please confirm my claim or prove me wrong?

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

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

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

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?

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

    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.

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

why hacks in third problem are forbidden?

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

Can some one explain in problem D, what is the insight that leads to constructing a directed graph with edges going from i to b[i] ? Specifically, why use edges from i to b[i] ?

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

for(int j = 0;j <= max_2;++j) { for(int k = 0;k <= max_1;++k) { t[ans + j*2 + k] = '1'; } } in B can you explain this part