### kartel's blog

By kartel, history, 4 weeks ago, translation,

1775A1 - Gardener and the Capybaras (easy version)

Solution

1775A2 - Gardener and the Capybaras (hard version)

Solution

1775B - Gardener and the Array

Solution

1775C - Interesting Sequence

Solution

1775D - Friendly Spiders

Solution

1775E - The Human Equation

Solution

1775F - Laboratory on Pluto

Solution

Now it is time for the bonus task and author solutions!

Bonus
Code for Problem A (solution for large alphabet)
Code for Problem B

• +87

 » 4 weeks ago, # |   0 Links for the codes not working
•  » » 4 weeks ago, # ^ |   0 Will be fixed soon.
•  » » » 4 weeks ago, # ^ |   +27 Kay! The arts in the problems were really great btw.
•  » » » » 4 weeks ago, # ^ |   +4 Big thanks BaluconisTima for it)
•  » » » 12 days ago, # ^ |   0 Not working yet
 » 4 weeks ago, # |   +18 Thank you very much for interesting problems and good tutorial!
 » 4 weeks ago, # |   +8 Thank you! :)
 » 4 weeks ago, # | ← Rev. 2 →   +13 In solution for A1, shouldn't there be just $O(n^2)$ ways to do the splitting because the third segment is completely defined by the first two? The time complexity of the algorithm would still be $O(n^3)$ though since string equality checking takes $O(n)$ time if I'm not mistaken.
 » 4 weeks ago, # |   +90 Easier solution for A2:If $s[1]=a$, then we can split it into $a=s[0], b=s[1], c=s[2...n-1]$.If $s[1]=b$, then we can split it into $a=s[0], b=s[1....n-2], c=s[n-1]$.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for this (: I was curious whether there is some cool(Really easy to interpret) solution for it or not.
 » 4 weeks ago, # |   +6 Very cool bipartite idea, I couldn't find an elegant way to set up the graph for problem D. Also because it is bipartite it is easy to print the path because we know to skip every other element if I'm not mistaken?
•  » » 4 weeks ago, # ^ |   0 My first bipartite problem solved! My bipartite implementation using a red and blue adjacency list if anyone is interested 188940781
 » 4 weeks ago, # |   -8 Wait, so my bruteforce submission somehow eventually covered all possible cases?
 » 4 weeks ago, # |   +11 A-F video editorial for ChineseBiliBili
 » 4 weeks ago, # |   0 In problem D, why is output the distance divided by 2?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Because in the author solution they draw edges between the number of legs and prime factors and traverse the graph that way. But the prime factors just serve to connect the number of legs, and don't truly count towards the distance
 » 4 weeks ago, # | ← Rev. 2 →   +6 I didn't notice that the string consisted of only 'a' and 'b' in problem A and solved it for all letters. just realized it after seeing the editorial :')
•  » » 4 weeks ago, # ^ |   0 Same, it was lucky that this problem had a linear solution for the whole alphabet or I would have been really screwed
•  » » » 4 weeks ago, # ^ |   0 Actually the original problem was set for the whole alphabet, and then it was made easier to fit for D2A.
•  » » » » 4 weeks ago, # ^ |   0 Hey Why cant the original problem kept as B or C and you could have created Problem A ?
•  » » » » » 3 weeks ago, # ^ |   0 Creating problems is not so easy as you think.
•  » » 3 weeks ago, # ^ |   0 Same i also did for all letters like i was upsolving my friend was why u taking so time think it as 800 problem but i was doing it for all letters after solving i noticed it was only for ab
 » 4 weeks ago, # |   +27 E is a great problem. A 2000+ problem with a solution which can be implemented by any beginner is pretty hard to propose. I just completely didn't thought about that such easy solution could exist, and wrote an O(n*log(n)) solution using double linked-list and priority queue, which I failed to debug before the contest ended.
•  » » 4 weeks ago, # ^ |   +4 E is amazing. SSRS could AC problem E in just 2 minutes.
•  » » 4 weeks ago, # ^ |   +5 lol I had the same idea, I went through three different implementations and finally settled on using two multisets storing {value, index} and {index, value} pairs and spent like an hour debugging — felt so stupid after reading other people's solution post contest
•  » » 4 weeks ago, # ^ |   +11 E is 2000+ only because everyone was stuck on D.If E was swapped with C, it would have a rating of 1600 max
•  » » 3 weeks ago, # ^ |   0 Did you manage to debug it? I'd love to see an alternate solution.
•  » » » 3 weeks ago, # ^ |   0 My submission:188766704 It's too complicated compared with the intended solution.
 » 4 weeks ago, # | ← Rev. 3 →   0 Share a solution for Problem C. First, n & x = x. Second, n became less from lowbit to highbit, and the value make n less is lowbit<<1, for example, n = 10101, x = 10100, lowbit is 1, n became 10100, m is 10100 + 10. However, here has a exception, n = 11010, x = 10000. After n bacame 10000, lowbit = 1000, m = 10000+10000 is illegal.188746063
 » 4 weeks ago, # | ← Rev. 3 →   0 In problem F we could let $x=\lfloor \frac{p}{2} \rfloor$, $y=\lceil \frac{p}{2} \rceil$ at first, and after each step do $x = x-1$, $y = y+1$ until $xy  » 4 weeks ago, # | +24 Interesting to see the official solution for problem D. I solved it in a slightly different way, by making the vertices prime numbers and the edges the indices of the arrays. For each pair of prime factors of$a_i$, I added edge$i$. I ran a breadth first search, initializing the queue with all prime factors of$a_s$, running it until I hit edge$t$. Did anyone else do something similar? •  » » 4 weeks ago, # ^ | 0 Yes, I also happened to use the same approach but was getting TLE on test #132. Here is the link to the submission if someone can help. •  » » » 4 weeks ago, # ^ | +8 I don't recommend using maps and sets for your adjacency list because you introduce a log factor into your time complexity unnecessarily. Try using C++ vectors instead. •  » » » » 4 weeks ago, # ^ | 0 I was able to make it work by adding another if statement to check if the starting and end node have same value. Here is the submission I made, you can compare with previous one.I have no idea why adding this condition makes the test pass, although the runtime is still 1.7s, so it just might be what you said and I got lucky.Thanks  » 4 weeks ago, # | 0 Problem A2 for some reason solved easier than in the parse. For each letter I looked for a substring before it and a substring after it. And checked the condition of the inequalities. Trying the letters of the string from left to right resulted in TL2, and trying the letters of the string from right to left resulted in the complete solution.  » 4 weeks ago, # | 0 How to solve C using binary search? •  » » 4 weeks ago, # ^ | +3 Bitwise & is non-increasing. So we just need a function to efficiently calculate the biwise & over a range. We can derive it ourself or look it up. https://www.geeksforgeeks.org/bitwise-and-or-of-a-range/ . Then we just use binary search over all possible values of M that are >= n, setting r = mid-1 if the result is too low and l = mid+1 if the result is too high. My submission: 188831318 •  » » 4 weeks ago, # ^ | ← Rev. 2 → +3 Observe that the range AND will be either greater than$x$, equal to$x$, or smaller than$x$, and these three conditions will appear in order (interval equal to$x$may be empty). So, you can find the smallest value$t$where the range AND of$[n,t]$is equal to or smaller than$x$, and do a simple sanity check on whether the range AND is actually equal to$x$.UPD: submission (ruby) — 188951229  » 4 weeks ago, # | 0 I do not understand the logic of B's question. According to the solution if any bit is less than or equal to 1 answer is "No" otherwise "YES". But what if we don't take that number? eg. [2, 4, 4]; binary representation: 10 100 100 the first bit in the 2 is set and unset in 4. But the answer should be "YES". Because we can take subsequence [4], [4]. •  » » 4 weeks ago, # ^ | 0 I think there are some problems in the description of question B, so I didn't understand it  » 4 weeks ago, # | ← Rev. 2 → 0 I don't understand how dp works to find number of ways to choose staircases in 4 corners of problem F, can anyone explain it clearer? •  » » 4 weeks ago, # ^ | 0 Look at my comment. It can be calculated directly from the partition numbers •  » » » 4 weeks ago, # ^ | ← Rev. 2 → 0 Is the final result the F[X*Y — n] where F is the 4th convolution power of the partitions array? •  » » » » 4 weeks ago, # ^ | 0 you need iterate for all possible (x,y) and sum up f[x*y-n]. •  » » » » » 4 weeks ago, # ^ | 0 Thank u so much <3  » 4 weeks ago, # | 0 I can't understand editorial of F, in second para, what does 4 figures that form empty cells in the matrix mean? Where do they come from? And how staircase came into the picture? •  » » 4 weeks ago, # ^ | -8 Imagine, that you have a rectangle with weight X and height Y. It must have minimal perimeter for N cells and$N \leq X \cdot Y$. If we iterate deleting cells with outside 'wall' in this rectangle we can see, that empty cells form 'ladder'.For example, X = 10, Y = 10 and we delete 6 cells( 3 in the 1st column, 2 in the 2nd and 3 in the 3th column):...#######..########.############################################################################### •  » » » 13 days ago, # ^ | 0 I have small doubt regarding F's editorial. In the DP transition what is maxP ? •  » » » » 13 days ago, # ^ | 0 It is constant that means a maximal possible perimeter which can be in the task  » 4 weeks ago, # | 0 Did I understand that? Tell me. For task B, the first test. According to the test, it turns out that the fifth bit is only in the 1st number, the fourth bit is contained only in the 2nd number, and the 3rd bit is only in the third number. Each number contains one unique bit. So that's why the numbers are different and the answer is No. If I'm not reasoning like that, then someone explain in detail on this example how the answer turns out. Thanks.  » 4 weeks ago, # | 0 Why it said "Code for Problem A", and "Code for Task C"?  » 4 weeks ago, # | 0 How binary search works in problem C? Can someone explain in simple words please •  » » 4 weeks ago, # ^ | 0 Let$F(x,y)$be$x \text{ & } (x+1) \text{ & } ... \text{ & } y$.For fixed$x$we see that$F(x,y) \geq F(x, w)$if$y \le w$, in other words the$F(x,y)$for fixed$x$is non increasing function.Let's look at$F(n, m) \leq x$. If for some value$m$it is true, it is also true for$\forall y \geq m$. So just binary search value$m$. •  » » » 4 weeks ago, # ^ | 0 Thanks i got it now. Since every bit starting from 0 will get turned off after at most 2 ^i steps so this will gradually decrease the overall value hence makes it a decreasing function. •  » » » » 4 weeks ago, # ^ | 0 There is other solution in$\mathcal{O}(\log{n})$, since we are "and-bitting" increasing values, soon or late, but we will get a zero on every bit position, so let's calculate the number$f(i)$,$f(i)$is the first number, since$i$-th bit in number$x \text{ & } (x+1) \text{ & } ... \text{ & } f(i)$is zero. For example, for$x = 5(101_2)f(0) = 6$,$f(1) = 5$,$f(2) = 8$. So if$i$-th bit is$1$in start number, but it is$0$in the end number, then we have to choose$m \geq f(i)$, but if$i$-th bit is$1$in start number, and it is still$1$in the end number, then$m$must be strictly lower than$f(i)$(otherwise, we will get$0$at this bit position!). So we just calculate$f(i)$for all$i$, it can be done at$\mathcal{O}(\log{n})$, and choose maximum value. •  » » » » » 4 weeks ago, # ^ | +3 Actually this is what my brain was thinking to solve this problem. Thanks , its such a wonderful solution for me!  » 4 weeks ago, # | 0 D is nice tho, you have to use set to minimize the complexity of bfs through verticles  » 4 weeks ago, # | 0 Problem E can also be solved with dp.Thanks to callmepandey for explaining this approach to me. For dp we will maintain 2 states.We will be maintaining the types of operations we have done and then at each index updating accoringly. Sample code. •  » » 3 weeks ago, # ^ | 0 Hi, can you please tell me the intuition behind this dp solution? I am not getting it. I was unable to solve the problem and now after seeing the editorial I can't unsee the solution provided by the author. I would like to know your approach. Thank you.  » 4 weeks ago, # | 0 Can anyone explain why (max_prefix — min_prefix) in problem E is working ? •  » » 4 weeks ago, # ^ | 0 What don't you understand in editorial for task E? •  » » » 4 weeks ago, # ^ | 0 "If we calculate the array of prefix sums, we'll see that the operations now look like "add 1 on a subsequence" or "take away 1 on a subsequence". Why? If we take the indices i and j and apply our operation to them (i.e. ai=ai+1 and aj=aj−1 ), it will appear that we added 1 on the segment [i...j−1] in the prefix sums array." I didn't understand this. •  » » » » 4 weeks ago, # ^ | 0 For example:we have an array$52-1090$. Pref sums will be$57-366$. If we do operation for subsequence${1, 3, 4}$we sub$1$from$a_1$, add$1$to$a_3$and sub 1 from$a_4$. Our array became$42-98$. Pref sums:$46-355$. And we can see, that we decrease$pf_1$,$pf_2$,$pf_4$and$pf_5$. As said in editorial, if we do an operation for$a_i$and$a_j$we decrease/increase$1$in segment$[i; j)$. We can see that in example above •  » » » » » 4 weeks ago, # ^ | 0 Ok, now I understand how that the prefix will increase/decrease. But , how the prefix will give me the minimum number of steps , it just increase /decrease by 1 only not until reach 0. In other words, what is the relationship between the (max_prefix — min_prefix) and the minimum number of steps? •  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 → 0 After this observation we need do our prefix sums equals to 0, because we need all$a_i=0$. And we can increase or decrease subsequence by 1. So, we decrease all positive integers until they become 0 and increase all negative integers until they become 0. And count of operations equals$maxPF-minPF$.Note, that we also have prefix sum$pf_0=0$. •  » » » » » » » 4 weeks ago, # ^ | +5 yeah ,got it thank u <3 •  » » » » » 3 weeks ago, # ^ | 0 Why do local prefix sums have impact on whole array?  » 4 weeks ago, # | 0 For broblem B If you remove this line, then everything will work: --a[i][j];  » 4 weeks ago, # | +28 Problem F can be solve in$O(n^{0.75}+Tn^{0.25})$.We need to calculation$(\prod_{i\ge 1}(1-x^i))^{-4}$, which can be solved in$O(n^{0.75})$by differentiating the function.If the width of rectangle is$\sqrt n-x$, we can found that$x$is at most$O(n^{0.25})$because$(\sqrt n+x)(\sqrt n-x)=n-x^2$, it's easily to found that$x^2\le \sqrt n$.So the problem can be solved in$O(n^{0.75}+Tn^{0.25})$. •  » » 4 weeks ago, # ^ | 0 Can u explain it in more details? •  » » » 4 weeks ago, # ^ | ← Rev. 2 → 0$ F=\prod_{i\ge 1}(1-x^i)=1+\sum_{k\ge 1}(-1)^kx^{\frac{k(3k\pm 1)}{3}}\\ G=F^{-4}\\ G'=-4F^{-5}F'\\ G'F=-4GF' $We only need to calculate the first$\sqrt n$coefficients of$F,G$. and there are only$O(n^{0.25})$coefficients which is not$0$in$F$. So we can calculate$G$in$O(n^{0.75})$. •  » » 3 weeks ago, # ^ | 0 Belarusian students don't know differentiating functions(may be have minimal knowledge about it)Interesting solve, thanks :)  » 3 weeks ago, # | 0 I used DP for E, since I noticed that the last element$a_n$must have exactly$a_n$operations applied to it (since any more would just be redundant, if$a_n > 0$, there's no point in adding 1 to it since we can just choose not to include it in our subsequence)So then I just apply this idea backwards, keeping track of the operations done so far (how many increases and decreases), and making sure to alternate increases to decreases when necessary. I don't like how messy my solution is though lol.  » 3 weeks ago, # | 0 NEED HELP FOR E! I was going through many solutions to problem E solved by different persons. Maximum people have done it using either DP or having 2 variables (i.e inc & dec) and linearly traversing and solving accordingly.My understanding of the problem is if I have 5 numbers, i.e 4 -8 -4 7 -3 Then It's better to perform 4 "Decreasing" operations because it is a terminal element. So if it's reasonable to make it 0 here. Now I can say I have 4 "Decreasing" operations in my pocket which I can distribute further but the problem is these EVEN ODD criteria. How to take care of this thing I am not getting at all.Is there some observation/fact I am missing?  » 3 weeks ago, # | +10 I have an$O(max_n + t n^{1/4})$solution for pF.A "good shape" can be viewed as a$h \times w$square delete some "staircase" for each corner, consider calculate the number of "staircase" consist of$x$blocks, which is equivalent to the number of non-decreasing sequence$s$whose sum is$x$and$s_1 > 0$, which can be further transform to a unbounded knapsack problem by seeing every object with weight$w$as "adding$1$to the last$w$elements of$s$".And here comes the interesting part, consider an$h \times w(h < w)$square, we can't delete all element in one row/col, otherwise we can achieve lower perimeter of shape, so it means the calculation of "staircase" for each corner are independent! So after calculate the above dp in$O(max_n)$($\sqrt{max_n}$different object weighted from$1$to$\sqrt{max_n}$, max_sum_of_weight =$\sqrt{max_n}$), and let the final result be$cnt$, where$cnt_i$means the number of "staircase" with$i$blocks, then by independence, the number of combination of "staircase" for four corner is just$cnt^4$, which can be calculate naively in$O(max_n)$since the size of$cnt$is$O(sqrt(max_n))$.Finally, for an$n$, enumerate all possible height and width of square, let say it is$h \times w$, then the answer for this square is$[x^{(h\times w-n)}]cnt^4$, and there are$O(n^{1/4})$possible$(h, w)$. why?let say$h = w = x$is a possible square, then you can delete atmost$x-1$blocks from it, and all other possible combination of$h, w$will be$(x + 1, x - 1), (x + 2, x - 2), ..., (x + d, x - d)$, and its area is$x^2 - d^2$, and we need to make sure$d^2$is less than$x-1$otherwise we can't fit$n$blocks in this square, and we have$d^2 < x \le sqrt(n)$, so the number of possible$d$is$O(n^{1/4})$, same argument apply for the case$h = x, w = x - 1$.So we can do it with$O(n)$precompute and$O(n^{1/4})$per query.  » 3 weeks ago, # | 0 in problem B, why using a vector instead of map for counting the number occurrences would cause TLE? •  » » 3 weeks ago, # ^ | 0 The number of active bits is limited. lets say n = 2, and num1 having 1 active bit at 20 and num2 having active bit at 10000. now even though for the map you would need only O(1) space but for vector you need at least a 10001 length vector to count active bits which will cause TLE.  » 3 weeks ago, # | +15 The difficulty of the solution of F can be optimized to$O(n+t\times \sqrt{\sqrt n})\$,just by going through less (x,y) when answering each query.One specific way can be seen in jiangly's solution.(Just where I find it hah :)
•  » » 3 weeks ago, # ^ |   0 well...Somebody had proved it above.
 » 2 weeks ago, # | ← Rev. 3 →   0 188759886 This submission passed during the contest. But now it gives MLE on test 130 which is one of the hack testcases. Still even after system testing this submission appears to be accepted in the standings. How???Also, how can I correct the MLE verdict?
 » 2 weeks ago, # |   0 Really great tournament! had a blast! very interesting questions indeed