Enchom's blog

By Enchom, history, 5 years ago, In English

Greetings Codeforces community!

This March, CodeChef is celebrating 10 years of cooking delicious problems and I would like to invite you all to participate in the March Long Challenge, sponsored by ShareChat. The long challenge is a 10-day long contest with 8 problems for you to solve. This month, there are some additional birthday gifts up for grabs! For more details, head over to the contest page now!

ShareChat — India’s fastest growing social network is offering internship and job opportunities to participants of March Long Challenge. The contest and job opportunities are open to programmers across the globe and problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese. Visit the contest link to know more.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

Contest Details:

  • Start Date & Time: 1st March 2019 (1500 hrs) to 11th March 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
  • Contest link: https://www.codechef.com/MARCH19
  • Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
  • Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://www.codechef.com/laddu
    (For those who have not yet got their previous winning, please send an email to [email protected]) Good Luck!
    Hope to see you participating!!
    Happy Programming!!
  • Vote: I like it
  • +53
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

You promise editorials on time ??

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Oh no, the new admin is my archnemesis teja[some numbers]!

The organization took over codechef, but don't worry the mad sp Hououin Riela will protect cf.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

seem's this long will be interesting...

»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Please don't extend it this time .

»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

When will you add the remaining two problems to the contest? It's been almost half a day since the contest started.

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

    Before the contest ends.
    P.S. — In case they fail to follow this deadline. They will extend the contest. So, that they can meet this deadline. :P

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Time limits could have been less strict :\

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Enchom, you have tagged pranjalr34 instead of me. Please correct the blog, if possible. Thanks.

»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Codechef is celebrating double digits by maintaining a single digit number of problems

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Any hints for Perfect Tree Problem? Btw, Enjoyed a long challenge so much, after a long time. Nice Problems !

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

    Though, I found TL of this problem too strict.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it
      Spoiler

      I got really angry at the TL in the Sonya and Tree problem, though.

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

        How to solve in $$$O(\sqrt N)$$$ per query? I somehow manage to squeeze $$$O(\sqrt N log(N))$$$, but it was hard enough and as far as I understand such solutions shouldn't pass.

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

          Basically u need to calculate some powers and some sums of gps rootn times. U can calculate power in O(1) by precomputing. Like if u precompute all powers a^x and a^1000x for x<=1000 then a^y = a^(y/1000)*a^(y%1000) For the gp thing, basically what u get is Sum of gp with r = a^x and n = y. You can use the sum of gp formula but inverse will be log(1e9+7) or calculate gp in log(y) where y is very small and if you do some complexity analysis, u'll realize its ammortized O(1) See my code — https://www.codechef.com/viewsolution/23391726

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

            How does a^y = a^(y/1000) * a^(y%1000)? Also, can you explain how you compute the gp in O(1)?

            Edit: Did you mean (a^1000)^(y/1000) * a^(y%1000)?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it
          • Say you have blackboxes which can compute $$$a^k$$$, $$$1+a+a^2+\cdots+a^{k-1}$$$, $$$a+2a^2+3a^3+\cdots+(k-1)a^{k-1}$$$ in $$$O(\log k)$$$ time for any $$$a, k$$$ (it's a pretty straightforward binary lifting).

          • After $$$O(n \sqrt{n})$$$ preprocessing, each query boils down to computing the sum of $$$O(\sqrt{n})$$$ values of the form

          $$$S(a, t_0, d_0, w, h) = \sum_{i=0}^{h-1} (d_0+i) \sum_{j=0}^{w-1} a^{t_0+iw+j}$$$

          (the number of vertices is non-decreasing at consecutive heights; each S corresponds to the interval of $h$ consecutive heights where this number is equal to $$$w$$$).

          • Obviously,
          $$$S(a, t_0, d_0, w, h) = a^{t_0} \left( \sum_{j=0}^{w-1} a^j \right) \left( \sum_{i=0}^{h-1} (d_0 + i)(a^w)^i \right). $$$
          • Compute the sums from top to bottom. Say that we computed $a^{t_0}$, $$$a^w$$$ and $$$\sum_{j=0}^{w-1} a^j$$$ from the higher layer. Then $$$a^{t'_0} = a^{t_0} (a^w)^h$$$, $$$a^{w'} = a^w \cdot a^{\Delta w}$$$, $$$\sum_{j=0}^{w'-1} a^j = \sum_{j=0}^{w-1} a^j + a^w \left(\sum_{j=0}^{\Delta w - 1} a^j\right)$$$. Using all these formulas, we can update the values above and compute a single term $$$S$$$ in $$$O(\log h + \log (\Delta w))$$$ time.

          • Let's prove this gives us $$$O(\sqrt{n})$$$ time per query. Now, I think there should be a couple of simpler ways to do it, but let's do it my way. We compute $$$S$$$ for a series of values $$$(w_1, h_1), (w_2, h_2), \dots, (w_k, h_k)$$$ such that $$$w_i < w_{i+1}$$$ and $$$\sum w_i h_i \leq n$$$. As $$$w_i \geq i$$$ and $$$h_i \geq 1$$$, we get that $$$\sum_{i=1}^{k} i h_i \leq n$$$ and $$$\sum_{i=1}^{k} i \Delta w_i \leq n$$$. Using AM-GM inequality, we get that

          $$$ \sum_{i=1}^{k} \log h_i = \log \left( \prod_{i=1}^{k} h_i \right) = \log \left(\frac1{k!} \prod_{i=1}^{k} ih_i \right) \leq -\log(k!) + k\log\left(\frac{\sum ih_i}{k}\right) \leq -k \log \frac{k}{e} + k \log \frac{n}{k} = k \log \frac{ne}{k^2}.$$$

          One can optimize the function in the end to see that the maximum is attained at $$$k \approx O(\sqrt{n})$$$, giving $$$O(\sqrt{n})$$$ time complexity. Exactly same bound can be produced for $$$\Delta w$$$'s.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for explanation! Now I understand that my solution's complexity is also $$$O(\sqrt N)$$$ per query because of reasons you mentioned :)

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I got all of this except for one thing: how do you compute $$$a+2a^2+3a^3+...+(k-1)a^{k-1}$$$ in $$$O(\log k)$$$? More specifically, how do you avoid computing the modular inverse of $$$a-1$$$, which takes $$$O(\log(mod)) = \log(10^9)$$$? This modular inverse is the bottleneck which is causing me TLE...

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it
              $$$ a + 2a^2 + 3a^3 + \cdots + (2k-1)a^{2k-1} = (a + 2a^2 + 3a^3 + \cdots + (k-1)a^{k-1})(1 + a^k) + k a^k (1 + a + a^2 + \cdots + a^{k-1}) $$$

              (You also compute $$$1 + a + a^2 + \cdots + a^{k-1}$$$ and $$$a^k$$$ at the same time.)

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

              This inverse was also the bottleneck in my solution (everything else was O(1) per "step" — by step I mean group of consecutive levels in the subtree having the same number of vertices). I used a very simple fix: if k is small (<= 20), just compute the sum in O(k) time :) Otherwise just use the usual logic (which involves computing the inverse). That was enough to pass the test cases. I'm not sure if they were just weak or there can be some proof behind it (no time to think about proofs — I barely had time to compete at all).

              But computing the sum in O(log(k)) is much more elegant. I even remember using this "trick" in the past for some similar types of sums, but I didn't think about it this time.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                Rev. 2   Vote: I like it +9 Vote: I do not like it

                You could have avoided the inverse simply by cancelling it out with numerator in sum of GP. And Your Solution is $$$O(\sqrt{Nlog(MOD)})$$$. Most of these solutions would have failed if test cases were strong. But you could have further improved on this if you maintain inverse for small values (say till 1e7). Than the complexity reduces to $$$O(\sqrt{Nlog(100)}) $$$.

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

                  Does it cancel out though? The expression I have is:

                  $$$1 + 2a + 3a^3 + ... + ka^{k-1} = \frac{ka^{k+1} - (k+1)a^k + 1}{(a-1)^2}$$$

                  Since the inverse is squared in the denominator, it doesn't fully cancel out with the term in the numerator of the GP. Is there a different expression such that it cancels?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You don't need to produce the closed form. I'm computing $$$x(k) = a + 2a^2 + 3a^3 + ... + (k-1)a^{k-1}$$$ using some kind of binary lifting:

                  • we know that $$$x(1) = 0$$$.
                  • given $$$x(j)$$$, we can compute $$$x(j+1)$$$ in constant time (simply add $$$jx^j$$$).
                  • given $$$x(j)$$$, we can compute $$$x(2j)$$$ in constant time (using the formula I mentioned above).

                  We need to simultaneously compute $$$y(k)=1+a+a^2+...+a^{k-1}$$$ and $$$z(k)=a^k$$$ in a similar fashion to achieve the constant time transitions. This enables us to compute any $$$x(k)$$$ in $$$O(\log k)$$$ time.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, exactly. That's the form I also used. I cancelled out one (a-1)^(-1) (actually I replaced it by the inverse of (y-1), where y is the argument of the query — this inverse is computed only once per query, so it's fine). But I couldn't cancel out the 2nd one. So, as I said, when k is small, I just computed the sum directly in O(k) time instead of using the formula which required the computation of (a-1)^(-1).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, I understand your method and I've gotten AC with it. Thanks for the help!

                  I'm now trying to understand what appears to be a simpler solution where the modular inverse cancels out in the closed form. I don't see how it works though.

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

                  Sorry, I didn't meant that you wont need binary lifting. As you said you can cancel out one power. Then you are left with $$$ka^{k}-ka^{k-1}-\sum_{i=0}^{k-1} a^{i} $$$. You will still need binary lifting but now problem reduces to calculating sum of GP (instead of AGP) in $$$O(logk)$$$ instead of $$$O(k)$$$. You can also compute the sum of AGP directly in $$$O(logk)$$$ as already mentioned

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I see, thanks.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve Sonya and Tree?

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

    I see it is tree version of problem "seats" in IOI 2018.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    My idea
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had a solution which ran in O(sqrt(N)) time per query/update (even in the case of general trees). For general trees it was O(deg) for "light" vertices (deg <= sqrt(N)) to perform some updates, and then had some special logic for "heavy" vertices (deg > sqrt(N)). The hardest case for my solution was when one "light" vertex had many "heavy" neighbors and the swaps involved such a light vertex and a heavy vertex. However, surprise-surprise, none of the large test cases had any heavy vertices! So you could just recompute the minimum and 2nd minimum neighbor of each updated vertex in O(deg) time (because deg was always <= sqrt(N) in the official large test cases).