Ashishgup's blog

By Ashishgup, history, 3 years ago, In English

We invite you to participate in CodeChef’s January Cookoff, today — 23rd January from 8:00 PM — 10:30 PM IST.

The contest will be 2.5 hours long. There will be 7 problems in Div 1/2 and 8 problems in Div 3. It will be rated for all three Divisions.

Joining us on the problem setting panel are:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes:

  • The top 10 Global Division 1 users will get $100 each.
  • The top 100 Indian Division 1 will get Amazon Vouchers worth Rs. 1500 each.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good luck and have fun!

  • Vote: I like it
  • +146
  • Vote: I do not like it

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

Servers down again?

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Submission page not loading :(

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Submission page not working for me!

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

    How come this is not working for only me and working for others?

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

      It seems I am the only one not able to see ranklist:(

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

Codechef is not working for me

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve ERASE? I doubt it is DSU, but I wasn't able to implement it correctly :')

And loved the problems MERGEDLIS and PRIMEGRAPH. SEGDIV was rather a puzzle problem, but it was also good, except the position.

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

    Direction of thinking is already right for you I guess. Maybe you just want to keep connected components and want to check if there is one component or more than 1 at the end. However, I didn't find how to achieve it using DSU. But, here's a way I found..

    let's iterate on permutation array from end and somehow maintain components . Now how can cur element help us. If there are two connected components to the right side, and both have at least one element larger than cur, then those two components can be connected. If we repeat this process, all the connected components which have at least 1 element greater than cur, can now combine.

    How do we maintain these components and combine operation ?

    Spoiler

    Code

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

    Yeah the idea is finding number of components. To avoid actually creating the graph, you can show that if the graph has $$$k$$$ components, each component must be a subarray. So, letting [i] denote the ith component, the array is like [1] [2] ... [k], where [1]>[2]>...>[k]. (By [1]>[2] I mean all elements in component 1 are greater than all elements in component 2.) Consider the first component, say it ends at index i, then $$$min_{1...i} > max_{i+1...n}$$$. This condition is necessary and sufficient, so you can just check it every $$$i$$$.

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

      You mean to say $$$<$$$ instead of $$$>$$$, right? Because, then only the components can be merged.

      Thanks, it was a nice problem too!

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

    You can go through each number and maintain some current minimum mn (initially it is a[0]) and a vector consisting of decreasing numbers to delete.

    Suppose that you are at a[i] now:

    if a[i] < mn -> add mn to the vector of erasable elements and set mn := a[i];

    otherwise, remove the vector elements (x) from the back while x < a[i], and after that, remove a[i] using mn;

    Finally, the answer is YES if and only if the vector is empty.

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

    The DSU approach is very interesting. It didn't even remotely come to my mind during this whole time. There hasn't been any official editorial published for this problem yet.

    But here's the draft solution I submitted when proposing the problem.
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why is ranklist not visible?

»
3 years ago, # |
Rev. 2   Vote: I like it +87 Vote: I do not like it

Feedback on the problem set:

  • Merged LIS: Not particularly interesting; for me it is as interesting as asking to compute the LIS of a sequence.
  • Subsegment Divisibility: Very cool easy problem. I guessed that the constraints are not hard to satisfy with a greedy and implemented it. Maybe there is a provable solution for all $$$n$$$, but I don't care and I actually think that the problem is cooler if there is not.
  • Prime Graph: Boring problem. In general, a problem which mentions prime numbers but its solution uses only that most prime numbers are odd is not particularly interesting.
  • Erase All But One: Nice problem. I have the vague feeling that this appeared somewhere else, but I am not sure. After first reading it, it reminded me of 1375C - Element Extermination, but the solution is completely different.
  • Boring Trip: Standard problem with medium difficulty. I enjoyed coding it to relax the mind before the next one.
  • Beautiful Permutation: Amazing problem. This was a pleasure to solve and I am proud of myself for solving it. My solution uses generating functions with two variables and obtains a closed formula (involving Stirling numbers of the first kind) for the answer. Since I really like my solution, if it does not coincide with the one described in the editorial I might post it later.

I really enjoyed Beautiful Permutation and therefore I really enjoyed the contest (even though I started competing half an hour late because I saw the announcement late), thanks to the authors.

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

    It is funny that I wrongly bruteforced then produced Stirling numbers of the second kind.

    Beautiful Permutation: It is easily oeis-able, I believe lol.

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

      Yeah, Beautiful Permutaion is oeis-able, I just searched 40, 200, 280, 160

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

    I came up with a solution which works for any N for Subsegment Divisibility, basically we can output 4 * i + (i%2).

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

    About Erase All But One: This problem did actually originate from the problem you linked (the sample explanation section should make it obvious, I tried to keep the new statement similar to that one to respect the original problem). I missed the most important constraint in that problem when solving it, and coincidentally found the new version quite interesting too. Glad you liked the problem :)

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

    I found it interesting that the first four problems all had simplistic solutions, although participants could get lost trying complicated ideas.

    Boring trip was somewhat standard as you say, it has lesser submissions than I would expect.

    Beautiful Permutation: I took the longest for this one, was thinking about two variable generating functions, etc. for long time. I saw that quite a few participants had solved this very quickly so looked for something simpler.

    Later realized that answer could be derived from number of permutations in $$$n$$$ having $$$k$$$ records, and multiplying by $$$2^k$$$. This coupled with the fact that the probability of the $$$i$$$th number being a record in a permutation is $$$1/i$$$ independently of the other probabilities led to Stirling numbers of the first kind. I think this probabilistic reasoning would be much simpler than derivation from two variable generating functions.

    Overall I enjoyed the contest.

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

      There is actually bijection between number of prefix max and number of cycles in permutation. Hence that leads to Stirling number of first kind.

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

        Aha right, you can use each record and all elements till the next record, in that order, to form a cycle.

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

      How is Boring Trip a standard problem? Can you please elaborate? At first glance, it looks like TSP to me. Can't think of anything else. Can you give some hints about the idea to be used?

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

        You can think on how will we arrange a fixed set of attractives (the sum of S is fixed, so only coordinates matters now). The first test in example is probably a big hint.

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

          Thanks for the hint, Yeah the first sample test case helped a lot.

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

          The problem would have been easier if k was odd, in that case, we just have to choose (k+1)/2 points on the right side which maximizes 2*disfrom middle point + s, and similarly for the left side. But if k is even, then the nearest point to the middle point will be traversed only once and the rest of the points will be traversed twice. I don't know how to handle this. Can someone please help as the editorial is also not published yet?

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

            Actually it is easier when k is even. I think you get even and odd mixed up?

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

              For example, if we take the sample test case, the middle point (or starting point) is having x=3, now I am telling the answer will be a summation of 2*dis + s, for all points except one which is just to right of it having x=5:
              (2*(6-3)+4) + (2*(3-1)+7) + (1*(5-3)+7)
              = 10 + 11 + 9
              = 30
              Finally add the s value of the middle point, i.e., 9 to get the final answer.
              If k would have been odd, then each point will have 2*dis+s, and it would have been easier to handle as in this case we could have kept two multisets for left and right separately and then iterate for the middle point and update the two multisets as we shift the middle point.

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

                I see. Even solution is pretty similar. How would you solve a task- the maximum non overlapping (prefix sum + suffix sum) of an array?

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

                I have solved using this approach, hope it helps you in the implementation part. Although the code is quite long :(

                Code

                You will have to modify a little bit and you will get the answers even when k is odd.I learned a lot from this problem and not publishing editorial has actually helped me :)

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

    The editorial for beautiful permutation didn't appear yet, but I suppose it wouldn't contain generating functions (at least I know much easier way to prove the formula $$$2^k \cdot s(n, k)$$$), so can you please share your solution? :)

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

      Start with one element $$$x$$$ and add others in order $$$n, n-1, \dots , x+1$$$. For every element there will be 2 positions next to $$$x$$$ that will increase the number of elements in $$$S$$$ by 1 and other positions will not increase $$$|S|$$$. Elements $$$x-1, \dots , 1$$$ also don’t increase $$$|S|$$$. So the answers will be the coefficients of

      $$$ (2\cdot y)\cdot (2\cdot y+1)\cdot\dots \cdot (2\cdot y + n-x)\cdot(n-x+2)\cdot \dots \cdot(n) $$$

      as a polynomial of $$$y$$$.

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

      Yes! The solution is technical, but it requires fundamentally no ideas. I like when standard methods are powerful enough to replace brilliancy.

      We can assume that $$$x=1$$$ (handling general values of $$$x$$$ is easy). Let $$$q(n, k)$$$ be the number of permutations of $$$1,2,\dots, n$$$ with exactly $$$k$$$ prefix maximums. The answer to the problem is

      $$$ ANS = \sum\limits_{k_1+k_2=k-1} \sum\limits_{n_1+n_2=n-1} q(n_1, k_1) q(n_2, k_2) \binom{n-1}{n_1,n_2} ,$$$

      indeed we count the permutations grouping them by "$$$n_1$$$ elements before $$$1$$$ and $$$n_2$$$ elements after" and "$$$k_1$$$ maximums of good subarrays are before $$$1$$$ and $$$k_2$$$ maximums of good subarrays are after $$$1$$$". Fundamentally we are splitting the problem between the elements before and after $$$1$$$.

      So, how can we compute such sum? Let us define the (exponential) generating functions (for $$$k\ge 0$$$)

      $$$ Q(s, t) := \sum\limits_{n, k\ge 0} \frac{q(n, k)}{n!} s^nt^k . $$$

      This generating function is important for us because (straightforward from the definition)

      $$$ ANS = (n-1)![s^{n-1}t^{k-1}]Q^2 . $$$

      Thus, we have to find a good expression for $$$Q$$$ (and then for $$$Q^2$$$). We have the following recurrence relation for $$$q(n, k)$$$ ($$$m+1$$$ represents the position of $$$n$$$ in the permutation)

      $$$ q(n, k) = \sum_{m=0}^{n-1} q(m, k-1)(n-1)(n-2)\cdots (m+1), $$$

      which is equivalent to the following ODE for $$$Q$$$

      $$$ tQ = (1-s)\partial_sQ . $$$

      Hence, we end up with the Cauchy-system (when $$$t$$$ is fixed):

      $$$ \begin{cases} Q(0, t) = 1 ,\\ \partial_sQ = \frac{t}{1-s}Q . \end{cases} $$$

      Solving this (using that $$$\partial_s\log(Q) = \partial_s Q / Q$$$) one obtains the magical formula

      $$$ Q(s, t) = (1-s)^{-t} . $$$

      Notice that this is the exponential generating function for (unsigned) Stirling numbers of the first kind (one can prove it by differentiating with respect to $$$s$$$, which is what I did during the contest). Hence, we conclude

      $$$ ANS = (n-1)![s^{n-1}t^{k-1}]Q^2 = (n-1)![s^{n-1}t^{k-1}](1-s)^{-2t} = $$$
      $$$ = 2^{k-1} (n-1)![s^{n-1}t^{k-1}](1-s)^{-t} = 2^{k-1}{n-1\brack k-1}. $$$
»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

SEGDIV: do a[i] = rng(), while array is bad, then increase i.

»
3 years ago, # |
Rev. 2   Vote: I like it +85 Vote: I do not like it

Simple construction for SEGDIV:

$$$a_i = 2\cdot i + i \% 2$$$

It works because $$$\sum_{i=l}^r a_i = (r-l+1)\cdot(r+l) + \sum_{i=l}^r i \% 2$$$ and the second part is strictly more than 0 and less than $$$r-l+1$$$.

»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

fun facts from tester:

  • AtCoder Beginner Contest 236 ends before my testing work ends.
  • Beautiful Permutation was mod $$$10^9+7$$$ originally.
  • I tried to put Boring Trip as second easiest problem of div1, admin stopped me and he was right.

Anyway, thanks for your participation. We hope you like the contest!

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

An easy solution for SEGDIV.

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

Can anyone give a test case where merging the two arrays ( similar to how they are merged in merge sort) the length of the LIS would not be the sum of the lis of the smaller arrays in the problem Merged LIS.

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

    A=[1,5,6] B=[10,3,4]

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

    I tried with the same approach initially and then realized that we can merge the two lis in the same way and that will be the maximum length possible.

    Testcase:
    1
    4 3
    3 2 2 2
    6 1 2

»
3 years ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

One more easy solution for SEGDIV:

Just use this series. My Solution

Updated Proof
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Did not receive Amazon vouchers for December Cook-Off 2021 Division 1 ;/

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Is there any website or some extension through which our deltas in Codechef round can be predicted?

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

Any tips to improve in this type of contest I was only able to solve MERGEDLIS in div1. And don't have any idea about all the other problems. Thanks in advance