Блог пользователя 300iq

Автор 300iq, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    All problems are not ad-hoc check again

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You have all the solutions already?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится +2 Проголосовать: не нравится

                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 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +77 Проголосовать: не нравится

    How to solve Calculus without OEIS?

    solve it with wolframalpha

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +75 Проголосовать: не нравится

      Modern problems require modern solutions!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        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 года назад, # ^ |
          Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

          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 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

How to solve MODPARRS and DIVPERMS ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится -15 Проголосовать: не нравится

          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 года назад, # ^ |
              Проголосовать: нравится -14 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            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 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Anyone did dp for Positive Prefixes?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone else come across this paper while solving MODPARRS?

»
4 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +53 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +60 Проголосовать: не нравится

      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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -17 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +52 Проголосовать: не нравится

        How did you calculate 989271733 without the full solution?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          you mean this ?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 года назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 .