kartel's blog

By kartel, history, 22 months 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

| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Links for the codes not working

»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank you very much for interesting problems and good tutorial!

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

Thank you! :)

»
22 months 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.

»
22 months 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]$$$.

  • »
    »
    22 months 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    One more
    if $$$s[ind] = a$$$ for $$$1 \leq ind \leq n-2$$$, then we can have $$$s_1 = s[0...ind-1], s_2 = s[ind], s_3 = s[ind+1...n-1]$$$
    Otherwise, $$$s_1 = s[0], s_2 = s[1...n-2], s_3 = s[n-1]$$$

»
22 months 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?

  • »
    »
    22 months 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

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

A-F video editorial for Chinese

BiliBili

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

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

  • »
    »
    22 months 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

»
22 months 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 :')

  • »
    »
    22 months 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

    • »
      »
      »
      22 months 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.

      • »
        »
        »
        »
        22 months 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 ?

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

          Creating problems is not so easy as you think.

»
22 months 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.

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

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

  • »
    »
    22 months 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

  • »
    »
    22 months 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

  • »
    »
    22 months 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.

»
22 months 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

»
22 months 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)$$$.

»
22 months 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?

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months 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.

      • »
        »
        »
        »
        22 months 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

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

    Nice approch .no of nodes will be in order of 3e4 .each number can have different prime factirs more than 7 .Total no of nodes will be in order of O(1e7) + multisource bfs great.Some times we break a node into edges .here u have model it in opposite way

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

How to solve C using binary search?

  • »
    »
    22 months 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

  • »
    »
    22 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
22 months 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?

»
22 months 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?

  • »
    »
    22 months 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):

    ...#######

    ..########

    .#########

    ##########

    ##########

    ##########

    ##########

    ##########

    ##########

    ##########

    • »
      »
      »
      21 month(s) 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 ?

      • »
        »
        »
        »
        21 month(s) 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

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

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

»
22 months 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

  • »
    »
    22 months 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$$$.

    • »
      »
      »
      22 months 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.

      • »
        »
        »
        »
        22 months 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.

        • »
          »
          »
          »
          »
          22 months 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!

»
22 months 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

»
22 months 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.

»
22 months 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 ?

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

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

    • »
      »
      »
      22 months 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.

      • »
        »
        »
        »
        22 months 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

        • »
          »
          »
          »
          »
          22 months 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?

          • »
            »
            »
            »
            »
            »
            22 months 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$$$.

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

Problem F can be solved in $$$O(n^{0.75}+Tn^{0.25})$$$.

We want to calculate $$$(\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})$$$.

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

    Can u explain it in more details?

    • »
      »
      »
      22 months 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})$$$.

  • »
    »
    22 months 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 :)

»
22 months 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.

»
22 months 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.

»
22 months 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 :)

»
22 months 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?

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

Alternate (and I believe simpler) solution for E: Link

We can just iterate over $$$i$$$, and maintain the minimum number of subsequences ending with a $$$+1$$$ element before the $$$i'th$$$ element, and minimum number of subsequences ending with a $$$-1$$$ element before $$$i$$$. For each $$$i$$$ greedily choose the subsequences that the $$$i'th$$$ element will be part of, and create new subsequences if required, such that $$$a[i]$$$ becomes equal to $$$0$$$.

Intuition: Just observe the 1st element, we can easily show that it if is negative, it will only be part of subsequences in which odd elements are positive, and vice versa if it is positive. Then just use some greedy ideas and induction.

I have no clue what the editorial is trying to say, but this problem should be 1500 rated tbh.

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

In question B making an array of size N * K, isn't that like 10 ^ 10 space, and isn't maximum space allowed 10 ^ 10, then how does the solution still work, please correct me if I am wrong and guide me about what can be the maximum dimension of the array so that it won't give memory limit exceeded

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

    It is guaranteed that the total sum of k[i] in all tests does not exceed 10^5

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

i did same for b but it's giving tle what's the problem with my submission 241361102