300iq's blog

By 300iq, 4 years ago, In English

We invite you to participate in CodeChef’s December Long Challenge, this Friday, 4th December, from 15:00 IST onwards. The contest will be open for 10 days i.e. until 14th December.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Joining me on the problem setting panel are:

Prizes:

Top 20 performers in the Indian category and top 10 performers in the Global 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

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!
Hope to see you participating!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it -28 Vote: I do not like it

sir all problems are adhoc can u plz add some data structure problem

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

    All problems are not ad-hoc check again

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

      dude like all of them are adhoc there is no dp or graph problem

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

        You have all the solutions already?

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

          no i have got the first but i am having a little bit trouble with the rest because adhoc problems are my weakness.

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

            So can we conclude that you don't know that the problems are ad hoc, you're only guessing based on the statements?

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 2   Vote: I like it -16 Vote: I do not like it

              I read the statement in depth and first 3 are definitely adhoc but sir is postive prefix not adhoc?

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

                Hi, I just talked with the authors of this round.

                Apparently, it seems to be an elaborate ploy by the Russians to lower your rating by setting ad-hoc problems.

                I'm very sorry this has happened to you.

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

How to solve Calculus without OEIS?

I'm kinda sad because as it is not present in Div 2 it seems this problem was intended to be one of the hardest in the set. But on the other hand I probably wouldn't have solved it without.

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

    Aha! I have a really cool solution using — suprisingly — calculus.

    First, let's extend the integral to $$$\mathbb{R}$$$, since the integrand is an even function; we divide by $$$2$$$ at the end. Then

    $$$\int_{\mathbb{R}} w(x) \left(\frac{1}{x}-\frac{x}{N^2+x^2}\right) \mathrm{d} x = \int_{\mathbb{R}} w(x)\frac{1}{2x} \mathrm{d} x - \int_{\mathbb{R}} w(x) \frac{1}{2(x-iN)} \mathrm{d} x - \int_{\mathbb{R}} w(x) \frac{1}{2(x+iN)} \mathrm{d} x = \frac{I_0 - I_N}{2} + \frac{I_0 - I_{-N}}{2} \,.$$$

    We need to compute $$$I_0 - I_N$$$ for each $$$N$$$. Consider the integral of $$$w(z)/z$$$ over a rectangle in the complex plane with vertices $$$(x,y) = (-C, 0)$$$, $$$(C, 0)$$$, $$$(C, N)$$$, $$$(-C, N)$$$ in this order. In the limit $$$C \rightarrow \infty$$$:

    • The integral over the side $$$(-C, 0)$$$ to $$$(C, 0)$$$ converges to $$$I_0$$$ (this is basically the definition of the Newton integral over an unbounded interval).
    • The integral over the side $$$(C, N)$$$ to $$$(-C, N)$$$ converges to $$$-I_N$$$. Here we used the important observation that $$$w(z+2\pi) = w(z)$$$.
    • Since $$$w(x)$$$ is bounded for large $$$|x|$$$, integrals over the vertical sides are $$$O(1/C)$$$ and converge to $$$0$$$.
    • The limit of this rectangular interval is therefore $$$I_0 - I_N$$$.

    What are the singularities of $$$w(z)/z = \frac{e^{2\pi z}-1}{z(e^{2\pi z} + 1)}$$$? The point $$$z = 0$$$ is a removable singularity because $$$\frac{e^{2\pi z}-1}{z}$$$ can be continuously defined at that point and so we can ignore it. Then there are points where $$$e^{2\pi z} = -1$$$, i.e. $$$z = i(k+1/2)$$$. Fortunately, none of these points are crossed by our integral. Now the residue theorem applies!

    For each $$$k$$$, the residue of $$$w(z)/z = \frac{e^{2\pi z}-1}{z} \frac{1}{e^{2\pi z} + 1} = f(z) \frac{1}{g(z)}$$$ at $$$z = z_k = i(k+1/2)$$$ is $$$r_k = f(z_k) / g'(z_k) = \frac{e^{2\pi z_k}-1}{2\pi z_k e^{2\pi z_k}} = 1/\left(i \pi (k+1/2)\right)$$$. By the residue theorem, the limit of our rectangular interval is

    $$$I_0-I_N = \sum_{k=0}^{|N|-1} i\pi r_k = 1/(1/2) + 1/(3/2) + \ldots + 1/(|N|-1/2)\,,$$$

    where we used the fact that the residues for $-N$ are the same as for $$$N$$$ just multiplied by $$$-1$$$, but we're also circling the singularities in the other direction (counterclockwise / clockwise respectively for $$$N > 0$$$ and $$$N < 0$$$).

    The final result is $$$\sum_0^{N-1} \frac{1}{2k+1}$$$.

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

    How to solve Calculus without OEIS?

    solve it with wolframalpha

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

      Modern problems require modern solutions!

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

      Can you give me more details about it,like I typed entire latex in Wolfram alpha,but it didn't work??

      P.S. just curious, as there was one question previous year where one person solved it Wolfram alpha, hence I tried.

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

        my mind came up with random thought: what is $$$f(n)-f(n-1)$$$?

        probably because of $$$n \leq 10^6$$$...

        so I started to write simplified formula to wolfram one by one from $$$n=2$$$ and soon recognized a pattern

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

          I solved it using Weierstrass Factorisation theorem and changing the order of summation of integration and summation(can be done here because of uniform convergence)

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

How to solve MODPARRS and DIVPERMS ?

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

    DIVPERMS: Let's look at any permutation $$$P$$$. Make a graph with $$$n$$$ vertices and initially no edges. If $$$\frac{P_{i + 1}}{P_i} \in S$$$ (i.e. the condition in the problem statement holds at $$$i$$$), we add an edge in the graph between vertices $$$P_{i + 1}$$$ and $$$P_i$$$. The graph we get is just a collection of disjoint paths.

    Let's first try count how many distinct graphs with $$$K$$$ connected components we can get. We can do it using a bitmask dp. Denote by $$$\mathrm{dp}[i][\mathrm{mask}]$$$ the number of ways to put the first $$$i$$$ things into the graph where the set positions of $$$\mathrm{mask}$$$ denote nodes that are already connected to a node with a higher index. Each new vertex we can either add separately or connect to a node with smaller index such that the ratio of indices is in $$$S$$$. You may notice that the $$$n/2$$$ larger bits of $$$\mathrm{mask}$$$ can never be set, so we can drop them. The complexity of the dp is $$$O(n 2^{n / 2})$$$.

    For every possible graph with $$$K$$$ connected components, the number of permutations whose graphs contain this graph as a subgraph is $$$K!$$$. You can now use inclusion-exclusion to count the number of permutations with $$$K$$$ connected components in the related graph, for every $$$K$$$. And in fact, this is the answer: if the graph has $$$K$$$ connected components, the permutation has cost $$$n - K$$$.

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

      How did you solve Digit Matrix. I formulated n*n inequalities of type x1-x2<=k1 or x1 + x2 <=k2 . i know about bellman ford algorithm to solve inequalities of type x1-x2<=k1 , but i got stuck at x1+x2<=k2.

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

        In this problem you can negate some variables (even columns, odd rows) so that all inequalities have type $$$l \le x_1 - x_2 \le r$$$.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          I think now i got it, sign of every variable in row/column will change alternately, so we can use this pattern to negate some variables.

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

            Sir, how did you do the LCASQRT problem?Would you kindly discuss your approach?

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

              Let S[u] dentoes sum of subtree rooted at u. Then $$$S[u]^2 = C[u] + S[v1]^2 + S[v2^2]..+S[vk]^2$$$, where $$$v1,v2...vk$$$ are children are of u. To find $$$S[u]$$$ we can use Tonelli-Shanks Algorithm .

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

          I don't know how hard is Digit Matrix to solve. Can you please explain more elaborately how to solve the whole problem?

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

            I suggest you watch the editorial for more details.

            But the outline is: if we know the values on the first row and the first column, we know all values. We can derive formulas for how every other value depends on these. Using the digit constraint, we can derive some constraints that must hold. Fix a value for the first row, first column square (try all values). It turns out all these constraints have the form $$$x_i - x_j \le r$$$ (if we do a little tinkering). And it turns out that there is an algorithm for solving systems of inequalities of this form (you can think about how this is related to shortest paths).

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

              What is $$$x_i$$$, $$$x_j$$$, and $$$r$$$ here?

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

                They are variables, $$$x_i$$$ and $$$x_j$$$ are unknowns, $$$r$$$ is known. You get a system of such inequalities.

                Try to work out these constraints yourself or read/watch the proper editorial, I don't have what it takes to write a full handholdy explanation for this problem.

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

Video editorials for 9 problems have been uploaded on Youtube. The other 3 videos will be uploaded over the next day or two. And the written editorials can be found here. Remaining 2 editorials will be added soon.

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

Anyone did dp for Positive Prefixes?

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

Did anyone else come across this paper while solving MODPARRS?

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

    Did you use this?

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

      Yeah. The $$$O(n!)$$$ algorithm presented there can actually be implemented in $$$O(n2^n)$$$ using DP.

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

Whosoever is the author of the problem calculus kindly bother to give the reason behind having such painfully bad test-cases for the problem (I have attached the AC code below)

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

    It is not just about this problem, I don't think much effort was put into preparing this contest. I had to check again if I was actually accessing Div1 problems when I opened EVEN PAIR SUM and POSITIVE PREFIXES. I'm pretty sure they were prepared no before than a week before the contest.

    HAIL XOR should have been the Div1's first problem for a long challenge.

    And then I checked CALCULUS, oh man, it's a competitive programming competition, and I'm very much fine using mathematical techniques to solve computational problems, but seriously an integral, that doesn't use any clever observations or anything but has to be solved completely with tricks from calculus? 300iq will you accept my problem proposals about hard problems from the field in mathematics I'm working on, that have no flavour of computation and can be solved using techniques that only people working in this field know?

    LCASQRT: I'd really like to know why this problem was in the problem set. It wouldn't take anyone with little knowledge of programming and maths, few seconds to realize that it asks you to compute square roots modulo prime. Did you think it will serve as an educational problem? Seriously? You may as well start to put "find square root of a polynomial" or given a "Walsh–Hadamard matrix of size 3, implement Walsh-Hadamard transformation".

    I'm not sure how well prepared or original other problems were, but they were at least not trivial.

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

      Agree on all points except that for LCASQRT. I think that was a nice problem.

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

      Don't be so harsh. It may make him depressed. The main reason is lack of proposals and we are free to enjoy them. How much you contribute to the community? At least you have non-trash thing to solve.

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

    Also give the reason behind adding such a deep mathematical question. If I am not wrong, it is a pure mathematical question & there is no programming knowledge or DSA knowledge needed in it.

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

    How would you come up with these numbers without the full solution?

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

      Given that the number of test-cases was so less one can easily binary search on the test-cases with a couple of assert statements as Errichto did here

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

        How did you calculate 989271733 without the full solution?

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

          you mean this ?

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

            Can you get it modulo $$$P$$$? Or can WolframAlpha give you the numerator and denominator (which are huge)? Does WolframAlpha even know that the value is rational?

            (It's entirely possible that with Pro you can get one of these things but for some reason I seriously doubt it.)

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

              yeah, I agree, I don't think wolfram can conclude the rationality of the result with full certainty. I did this by observing the pattern for some small values.

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

FAQ:

  • CALCULUS is trash: I don't think that it is bad to experience unusual types of problems, and Long Challenge is a good place for those. I see that community didn't like this problem, and I won't set a lot of problems like that in the future. But I like this problem, and I don't think that it is so horrible.
  • Test data is bad: Yeah, I should've had more tests in CALCULUS with random $$$n$$$ up to million, my bad. Although if you can solve for $$$n=10^6$$$, probably, you can solve the entire problem as well? The main reason to use only a few tests was that CodeChef could experience some troubles with queue if there are a lot of participants + a lot of tests in easy problems, and I don't want the round to be unrated because of that.
  • Even Pair Sum and Positive Prefixes are too easy for DIV1: Yeah, that may be the case, but the two easiest problems are not included in DIV1 anyway. I wanted to have more easy problems to make the contest better for DIV2 because most problems are hard.
  • LCASQRT is bad: I agree that this problem is mostly standard, but LCA convolution is a funny yet trivial object to play with :) Problems with fast MOD-sqrt are also rare, so this problem is great for educational purposes.

Thanks to all participants of this Long Challenge! I hope you liked my taste of problems and will participate in the Long Challenges coordinated by me in the future.

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

    I think the tests for DIVPERMS and DGMATRIX might have also been a little weak. For DIVPERMS, I coded a suboptimal solution and hardcoded two max-tests (which worked after running locally for around 40 minutes). This somehow passed all pretests, even though when I tested on pretty much any other close to max test it TLEs.

    For DGMATRIX, I reduced the problem to solving the inequalities that most people used Bellman-Ford to solve, except I didn't know Bellman-Ford at the time. So I coded a $$$\mathcal O(10^N)$$$ DFS bash with some quick early breaks to get the first subtask, but it unexpectedly passed all test cases. I put my submissions below (sorry if they're a little messy, I haven't cleaned them up).

    DIVPERMS Submission DGMATRIX Submission

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

I personally enjoyed STROPERS idea. May be it is a little bit standart, but I really liked it, thanks!

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

    I thought STROPERS was non-standard and enjoyed it as well. It would be great if you could share any similar problem(s) that you know of!

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

STROPERS . I was trying to solve this problem by making every substring , lexicographically smallest possible and keeping them in a set, but I was getting wrong ans . Can somebody explain what algorithm did they apply to make the substring lexicographically smallest substring .