All problems are not ad-hoc check again

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

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

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}$$$.

How to solve Calculus without OEIS?

solve it with wolframalpha

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$$$.

Dp is not required for that

Did you use this?

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.

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.

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

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

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!