kartel's blog

By kartel, history, 4 weeks ago, translation, In English

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
Bonus answer
Code for Problem A (solution for large alphabet)
Code for Problem B
Code for Task C
Code for Task D
Code for Task E
Code for Task F
 
 
 
 
  • Vote: I like it
  • +87
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Links for the codes not working

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank you very much for interesting problems and good tutorial!

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you! :)

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

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, # |
  Vote: I like it +90 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    Thanks for this (: I was curious whether there is some cool(Really easy to interpret) solution for it or not.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My first bipartite problem solved! My bipartite implementation using a red and blue adjacency list if anyone is interested 188940781

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Wait, so my bruteforce submission somehow eventually covered all possible cases?

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

A-F video editorial for Chinese

BiliBili

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why is output the distance divided by 2?

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

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

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually the original problem was set for the whole alphabet, and then it was made easier to fit for D2A.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey Why cant the original problem kept as B or C and you could have created Problem A ?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Creating problems is not so easy as you think.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +27 Vote: I do not like it

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, # ^ |
      Vote: I like it +4 Vote: I do not like it

    E is amazing. SSRS could AC problem E in just 2 minutes.

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

    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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you manage to debug it? I'd love to see an alternate solution.

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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<n$$$. Also if $$$x \neq y$$$ we need to consider the symmetric situation. Thus the complexity of each query will be $$$O(n^{1/4})$$$.

Also the official solution just said "you must optimize to $$$O(n)$$$". In fact the final array we get is the 4th convolution power of the array of partition number: $$$p=[1, 1, 2, 3, 5, 7, 11...]$$$ where $$$p[n] = \sum_{i \neq 0}(p[n+(-1)^{i}i(3i-1)/2])$$$ where $$$i$$$ iterate among all non-zero integers. We only need it's value up to $$$\sqrt{maxn}$$$, so we can calculate $$$p[n]$$$ in $$$O(maxn^{3/4})$$$ and calculate the convolution in $$$O(maxn)$$$.

»
4 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C using binary search?

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

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think there are some problems in the description of question B, so I didn't understand it

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

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have small doubt regarding F's editorial. In the DP transition what is maxP ?

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

        It is constant that means a maximal possible perimeter which can be in the task

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Why it said "Code for Problem A", and "Code for Task C"?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How binary search works in problem C? Can someone explain in simple words please

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Actually this is what my brain was thinking to solve this problem. Thanks , its such a wonderful solution for me!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D is nice tho, you have to use set to minimize the complexity of bfs through verticles

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why (max_prefix — min_prefix) in problem E is working ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What don't you understand in editorial for task E?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For example:

        we have an array $$$5$$$ $$$2$$$ $$$-10$$$ $$$9$$$ $$$0$$$. Pref sums will be $$$5$$$ $$$7$$$ $$$-3$$$ $$$6$$$ $$$6$$$. 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 $$$4$$$ $$$2$$$ $$$-9$$$ $$$8$$$. Pref sums: $$$4$$$ $$$6$$$ $$$-3$$$ $$$5$$$ $$$5$$$. 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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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   Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why do local prefix sums have impact on whole array?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For broblem B If you remove this line, then everything will work: --a[i][j];

»
4 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u explain it in more details?

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

    Belarusian students don't know differentiating functions(may be have minimal knowledge about it)

    Interesting solve, thanks :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +10 Vote: I do not like it

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?

So we can do it with $$$O(n)$$$ precompute and $$$O(n^{1/4})$$$ per query.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B, why using a vector instead of map for counting the number occurrences would cause TLE?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +15 Vote: I do not like it

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

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

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, # |
  Vote: I like it 0 Vote: I do not like it

Really great tournament! had a blast! very interesting questions indeed