We invite you to participate in CodeChef’s March Lunchtime, this Saturday, 27th March.

Time: 7:30 PM — 10:00 PM IST. Please note the change in timings. This contest will end at 10 PM instead of the usual 10:30 PM.

The March Lunchtime is going to have Gameskraft, Quadeye Securities, Dialpad, and BetterPlace as the official contest recruiters! Gameskraft is hiring for Javascript and Frontend Developers. Quadeye is on the lookout for brilliant Full Stack Developers in CodeChef’s community. Dialpad is looking to attract top talent from CodeChef for the role of Software Engineer. BetterPlace is looking to hire competent coders from the community for SDE 1 and SDE 2 roles.

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 us on the problem setting panel are:

• Setters: Le Duc Minh, nbmnb, nhdtxdy, Quân Anh

• Testers: Shubham TheOneYouWant Anand Jain, Aryan aryanc403 Choudhary, Trùng Mễ, Tran thenymphsofdelphi Xuan Bach, Quang xuanquang1999 Nguyen

• Statement Verifier: Jakub Xellos Safin

• Editorialist: Nishank IceKnight1093 Suresh

• Admin: Jatin jtnydv25 Yadav

• Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singla, Shivam Bohra, Radoslav radoslav11 Dimitrov, Aryan Agarwala, Meet myth_gemphir Singh Gambhir

• Mandarin Translator: Gedi gediiiiiii Zheng

• Vietnamese Translator: Team VNOI

• Russian Translator: Fedor Mediocrity Korobeinikov

• Bengali Translator: Mohammad solaimanope Solaiman

Prizes:

We are doubling the happiness this Lunchtime.

Since it's our birthday month, the Chef is in a generous mood. We shall be giving away prizes to double the number of winners than usual. For example: Instead of Top 10, Top 20 will get the winner laddus. This is applicable across all category winners.

There are also special prizes for women:

• Div 1: top 10 females (300 laddus)
• Div 2: top 6 females (150 laddus)
• Div 3: top 6 females (150 laddus)

The winners can claim cool CodeChef goodies using these 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!!
Happy Programming!!

In the static RMQ problem, one has to answer queries about the minimum in a range of a fixed array. A classic variation allows updates of the form $$$A_i \leftarrow x $$$. A good solution is segtree which solves it in $$$O(\log{n})$$$ query and update times. My question is : How fast can we update if we must answer queries in $$$O(1)$$$?

I can think of a solution which works in $$$O(\sqrt{n})$$$ per update :

We can answer queries in $$$O(1)$$$ using a sparse table. Since each element is a part of $$$O(n)$$$ ranges in the sparse table, we can clearly update a sparse table of an array of size $$$n$$$ in $$$O(n)$$$. Now, divide into $$$\sqrt{n}$$$ blocks. For each block, maintain the prefix and suffix minimums and also a sparse table. Clearly, a block can be updated in $$$O(\sqrt{n})$$$. On the upper level, maintain another sparse table which can answer minimum over a range of blocks. Clearly this can also be done in $$$O(\sqrt{n})$$$ and the query time is still $$$O(1)$$$. The memory used and precomputation done are both $$$O(n \log{n})$$$.

Can we do better, say $$$\text{polylog}(n)$$$, perhaps using more memory and/or precomputation? Is there a known lower bound?

Hi, we are hosting a mirror contest of ICPC Asia-Kharagpur Regionals. The contest has just started and is available here.

The live updates of the onsite contest are available here

Contest link

Random flips

Let $$$h_n(r) = \displaystyle \sum_{i=1}^{n} i^r$$$.

$$$h_n(r), h_m(r)$$$ can be computed for all $$$1 \leq r \leq 2k$$$ for both $$$n, m$$$ in $$$O(k^2)$$$ using the recursion:

Let $$$P_{ij}$$$ be the probability that $$$(i, j)$$$ has a $$$1$$$ in it after all the operations.

By linearity of expectation, we have to find $$$\displaystyle \sum_{i, j} P_{i,j}$$$.

Let $$$p_{i,j}$$$ be the probability that cell $$$(i, j)$$$ is flipped in one such operation.

The total number of submatrices is $$$\dfrac{n(n+1)}{2} \dfrac{m(m+1)}{2}$$$.

The number of submatrices containing $$$(i, j)$$$ is $$$i(n-i+1)j(m-j+1)$$$

So,

Now, $$$P_{i, j} = $$$ probability that this cell is flipped in odd number of operations:

So, we have to find:

Let $$$t = - \dfrac{8}{n(n+1)m(m+1)}$$$. Also, let $$$f_n(i) = i (n + 1 - i)$$$ and expand using binomial theorem:

We have :

Now,

Hence, $$$\displaystyle \sum_{i=1}^{n} f_n(i)^r$$$ can be computed in $$$O(r) = O(k)$$$.

Thus the original formula can be computed in $$$O(k^2)$$$

A forest of perpendiculars

We convert the problem into:

Given a value $$$r$$$, find the number of lines with distance $$$\leq r$$$ from point $$$q$$$.

For this, consider a circle $$$C$$$ with radius $$$r$$$ centered at $$$q$$$. Consider two points $$$A$$$ and $$$B$$$, both outside the circle $$$C$$$. The line passing through $$$A$$$ and $$$B$$$ has distance $$$\leq r$$$ from $$$q$$$ iff it intersects the circle $$$C$$$. Let $$$F_A$$$ and $$$G_A$$$ be the points of contacts of tangents drawn from $$$A$$$ to the circle. Similarly define $$$F_B$$$ and $$$G_B$$$.

We can prove that the line passing through points $$$A$$$ and $$$B$$$ intersects the circle $$$C$$$ if and only if the line segments $$$F_{A} G_{A}$$$ and $$$F_{B}G_{B}$$$ do NOT intersect.

So, we need to draw $$$2 n$$$ tangents, and then draw $$$n$$$ chords passing through the respective points of contacts, and count the number of intersections of these chords.

For this, sort the points by polar angles in $$$O(n \log{n}) $$$. Now we can count the number of intersections of line segments in $$$O(n \log{n})$$$, by iterating on the points.

Therefore, this question can be answered in $$$O(n \log{n})$$$.

Then we can just binary search to find the answer in complexity $$$O(n \log{n} \log{\frac{R}{\epsilon}})$$$

Say we need to solve a recurrence of the form :

Here, f is an arbitrary function which can be computed in O(1). An example of such a problem is 553E - Kyoya and Train. The tutorial gives a solution in .

I recently saw a similar problem in codechef may long SERSUM, where I used another technique which I had thought of when I saw the prior problem. In this post I explain this very simple and intuitive sqrt decomposition solution, running in which works in almost the same time as solution because of a very low constant. Here goes:

Let us divide into blocks of size say K, giving us a total of ⌈ N / K⌉ blocks. Block t consists of [(t - 1)K, tK - 1]

Let .

Let C_t = A_tB.

When processing the block t + 1 we assume that we know C_t, which is computed when block t has been completely processed. So, we compute C_t a total of times using FFT in time .

Consider some n between [tK, (t + 1)K - 1]. Then,

.

Clearly, the right part can be calculated in O(K), and we have an extra time of O(NK) because of this part.

Overall complexity = , which is minimized taking , and overall complexity is .

An optimization:

Note that the right part can be computed with only one mod operation if we use m2 = m * m, and keep subtracting m2 when the total sum exceeds it. Eventually we take total sum modulo m. This is a very common technique, which we use in matrix multiplication as well.

This means that we should use a block size even greater than for better results, because of a huge constant difference in the two parts. (Computing C_t using FFT, and computing the remaining sum in O(k) using brute force iteration with the optimization above.) Just as an example, for N = 10⁵, and m = 10⁹ + 7 (which is a bad mod value for FFT problems), the best performance comes when you take K ≈ 6 × 10³. For this input size it runs in about 2 seconds, which is pretty good.

Hello Codeforces Community!!!

I invite you all to take part in Hackerearth's March Easy contest.The contest will be held on 1st March,2018 at 22:00 IST.

Problems have been set by allcodeAC and tested by trytolearn and me.

You will be given 5 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners(i.e. Programmers with a rating of 1600 or less before the challenge starts).

Good luck and have fun.