Educational Codeforces Round 118 Editorial

1613A - Long Comparison

Idea: BledDest

1613B - Absent Remainder

Idea: BledDest

1613C - Poisoned Dagger

Idea: BledDest

1613D - MEX Sequences

Idea: BledDest

1613E - Crazy Robot

Idea: BledDest

1613F - Tree Coloring

Idea: BledDest

• 7 months ago, # ^ | Umnik: "Idk how Elegia's mind works"

  • 7 months ago, # ^ | Those interested in how um_nik's mind works can read how to solve it in in simpler notations here

• 7 months ago, # ^ | Captain EI txdy txdy txdy

• 7 months ago, # ^ | by the fast algorithm for P-recursive sequence I've never heard of this before, could you link to a tutorial / paper or something?

  • 7 months ago, # ^ | The brief idea is to evaluate for where is a matrix with polynomial entries. Min-25 gives an algorithm that achieves the smallest log factor currently. Though his original blog was not available for some reason, there is a detailed description of this algorithm in the editorial of CF Round #700 div1. E.

    • 7 months ago, # ^ | I read that editorial, but unfortunately don't see how it is connected to this problem. Oh, also, what's the P-recursive equation for ?

      • 7 months ago, # ^ | Since , we take derivation on both sides, then we obtain By extracting the coefficients on both sides you obtained a P-recursive equation of immediately. Consider is P-recursive, then is also P-recursive (You can obtain the equation by simply replacing with and then multiplying on both sides of the equation). So its sum can be evaluated through the algorithm. There are more tricky ways to deal with the recurrence to reduce the factor, but I omitted the details here since it's not the bottleneck of the entire problem :)

• 7 months ago, # ^ | it would be very interesting to see the code for the solution

• 7 months ago, # ^ | Do you have an implementation? This sounds cool.

  • 7 months ago, # ^ | ← Rev. 3 →   +1 I didn't solve this problem, I'm simply reading the solution from the editorial and wondering why their implementation is instead of . I think my mistake is probably that the 3rd case of the master theorem doesn't apply here, and the master theorem cannot be used. To use the master theorem case 3 there must exist a constant such that , and it might not exist.

    • 7 months ago, # ^ | ← Rev. 2 →   +3 Because the , this recurrence actually falls in case 2 of the master theorem (if you hold on the order of cases in wikipedia). This solves to a running time of

      • 7 months ago, # ^ | I was referring to the cases from CLRS (page 94) and the case 2 is more specific there, and it doesn't fall into it. Indeed if I look at Wikipedia the case 2 is more generic and it does apply in this case, thanks!

• 7 months ago, # ^ | ← Rev. 2 →   +9 We initialize with a , which represents an empty subsequence (which has MEX equal to ). At the end we accumulate the answers and count it in. Since we are asked to count only non-empty subsequences, we should subtract it.

  • 7 months ago, # ^ | Thank you,I got it.

• 7 months ago, # ^ | ← Rev. 3 →   +11 I can give an intuitive idea behind that. For every violated constraint, a node of the tree is already defined by its parent (it's just their parent's number minus one). So basically out of the nodes, we can focus on the nodes which aren't tied to their parents and think about the relative order between them. Let's build a sequence of these untied nodes in which the first node has the highest value , the second the next highest value and so on. Of course you can choose any of them to have the highest value , then choose any other node to have the next highest value (which depends on the previous node as it might have induced the value to one of its children and maybe more values to its descendants) and so on. The thing is you can choose any of the untied nodes to go next in this sequence. Therefore you can have any possible relative order between them, so the number of colorings is

  • 6 months ago, # ^ | Thank you, it was very helpful !

• 7 months ago, # ^ | Try replacing your endl by "\n" endl is slower. It also flushes the output

  • 7 months ago, # ^ | Thanks a lot! In a million years I wouldn't have thought of that

  • 6 months ago, # ^ | It's a very bad thing!!! How could one handle this at the contest time? Please explain anyone, who had handled such things. Is it a reason for a problem left unsolved? Those who have solved this problem by putting just "\n" instead of endl, please tell me, how did you figure out that at the contest time? BledDest awoo

• 7 months ago, # ^ | i think you should just solve problem A first..

• 7 months ago, # ^ | Please read the second announcement. You got a wrong understanding of MEX-correct sequence.

• 7 months ago, # ^ | The sequence (x1, x2, x3, .., xi) is mex-correct if :- | xi — mex(x1, x2, x3, ..., xi) | <= 1 ; where xi is the last element in sequence. Hence for sequence (0,0,1,1,1,2,3) => mex(0,0,1,1,1,2,3) = 4 and xi=3 (last_element_in_sequence). Here, | xi — mex| = |3-4| = 1 and 1 <=1. Hence it is correct

• 7 months ago, # ^ | ← Rev. 2 →   0 You can start a BFS from the lab. Mark lab as + for generalization sake. During bfs, do the following: 1. If a cell you are looking at has at most one neighbour cell which is not blocked and not with plus, then mark that cell as +. 2. If a cell is marked + now, push all of its neighbour cells to the queue unless the neighbour cell was visited from this particular cell. In other words, keep visited not just for some cell, but for a parent-child relationship. If cell a already pushed cell b to a queue, then don't let a to push b again, but some other cell c can still push b. 3. Go to the next queue element. Pretty sure there is no way to solve this problem using DFS.

  • 7 months ago, # ^ | There is a dfs solution, check my submission: 137662230. Consider the lab is the root, we follow the four "hallways". At any square we find it connects to more than 1 '.', stop there.

  • 7 months ago, # ^ | thanks I understood:)

• 7 months ago, # ^ | ← Rev. 3 →   +8 Dont use std::endl, use "\n" instead. Flushing std::cout is very slow, especially when you need to do it 1000000 times. see this: 137852168 and 137853185

• 7 months ago, # ^ | AC: https://codeforces.com/contest/1613/submission/137914304 Your mistake is using stack<char> qx; stack<char> qy;. it should be stack<int> to not overflow as a char overflows quickly. As a tip, this is how I debugged your code. Use assert() and insert it at different points of your code to see where things went wrong. I assert()ed that your values were valid just before pushing it onto the stack, as well as assert()ing the values at the start of the function. It was okay before pushing it onto the stack, but not when you used it in the function. So I can deduce that something must have went wrong when you passed it into the function, and that's how I found out.

  • 6 months ago, # ^ | Thanks bro

• 7 months ago, # ^ | No, . Your input is too large.

  • 7 months ago, # ^ | thanks for explanation, i mistakenly read that as 10^16 .

• 3 hours ago, # ^ | How did you come up with the above function ?

• 7 months ago, # ^ | Binary search tagged problems for D

• 6 months ago, # ^ | Hey, this has simply got to do with the way the binary search was written. From the code, you can see (thanks to the if else) that the variable r will be the greatest value for which the sum will be < h. You can understand this as: if the sum >= h, then r = r-1. So r will be lowered until it reaches the optimal solution-1. There is actually another way to write this binary search. In my solution, I wanted "lo" to be the smallest value such that the sum would be >= h. Link to my solution: https://codeforces.com/contest/1613/submission/138581286 I hope this is clearer to you now! Do not hesitate to reply if it is not clear enough :)

• 7 months ago, # ^ | Never mind It got resolved after passing multidimensional vectors by reference which helped me removing some unnecessary global containers.

• 7 months ago, # ^ | [0 2 1] is not correct in ith step we get mex from (x1, x2.... xi) i = 0; we have (0) now mex is 1. so |0-1| = 1 <= 1.. right. i = 1; we have (0, 2). now mex is 1. so |2 — 1| = 1 <= 1.. right. i = 2; we have (0, 2, 1). now mex is 3. so |1 — 3| = 2 > 1... wrong;

  • 7 months ago, # ^ | Thanks, Wolowitz! I didn't notice it was inside a math absolute value, LOL. Shame on me~