You are not logged in. Please login at www.codechef.com to post your questions!

×

GEEK05 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

Sieving Techniques, Modular Arithmetic, Prefix Sums.

Problem

Find the sum of ${a}*{l} \dots {a}*{r}$, where array $a$ satisfy the follwoing property,

$\sum_{d | n} {a}_{d} = {2}^{n}$

Explanation

First of all, we see some basic properties of modular arithmetic:

  1. (a + b) % m = ((a % m) + (b % m)) % m
  2. (a - b) % m = ((a % m) - (b % m) + m) % m
  3. (a * b) % m = ((a % m) * (b % m)) % m

For the 3rd property, care must be taken while doing the multiplication, as the value may be an integer, while there may be overflow in the intermediate multiplication operation.

Now, assume we have all the values of $a_i$ calculted in efficient way, then we can answer the sums in every query naively in $O(r-l)$. To do this efficiently, we can simply precompute the prefix sums and then answer the query in $O(1)$, as :

ANS = prefix[r] - prefix[l-1], where prefix[i] = $\sum_{j=1}^{j=i} a[i]$

To calculate $a_i$ efficiently, we will use the general sieving technique. The pseudocode is given below :

for i in [1 : 100000]: a[i] = 2^i for i in [1 : 100000]: for j in [2i, 3i, ... 100000]: a[j] -= a[i]

To check why this code works, let us look at simple observations.

  1. We know initial terms are as a[1] = 2, a[1] + a[2] = 4, a[1] + a[3] = 8, a[1] + a[2] + a[4] = 16, a[1] + a[5] = 32 and so on.
  2. Thus, once we have calculated the correct answer for particular $i$, we will subtract its contribution from other $a_j$, to which it contributes to their sum. For example, we know $a[1]$ initially, so, we subtract it from $2, 3, \\dots$. Thus, we get the correct values of a[2], a[3], a[5] etc. Now, we subtract $a[2]$ from $4, 6, 8 \\dots$, and we get the correct value of 4. Thus the process continues.

The time complexity of this approach is $O(n/1 + n/2 + n/3 + n/4 + \dots + n/n)$ = $O(n \log{n})$.

Bonus Problems

  1. As the constraints are not that large, we can even do a naive brute force to calculate the values, in $O(N * sqrt(N)). See setter's solution 2 below.
  2. As constraints allowed storing the pre-computed values in an array, the above approaches were good enough. What is the number of queries were reduced, but $L, R$ were up to now ${10}^{11}$. We can still use the idea of mobius inversions and some other transforms to give the answer to each query in $O({n}^{3/4})$. Try to think about this one? You can also refer to [this video](https://www.youtube.com/watch?v=_noJI8UkTq8&t=31s) by kevinsogo for some help.

Time Complexity

$O(N * \log{N} + Q)$, where $N$ = Max value of R i.e ${10}^{5}$

Space Complexity

$O(N)$, where $N = {10}^{5}$

Solution Links

Setter's solution

Setter's solution - 2

asked 20 Nov '17, 22:01

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 26 Nov '17, 16:34

admin's gravatar image

0★admin ♦♦
19.7k350498541


Can you please provide the solution using mobius inversions?

link

answered 20 Nov '17, 23:31

bansal1232's gravatar image

5★bansal1232
2.8k1418
accept rate: 16%

$a_n = \sum_{d|n} {\mu(d) * {2}^{n/d}}$. The second point in bonus part is wrong, as the complexity will be still $O(n \log{n})$, but the 3rd part is correct.

(21 Nov '17, 00:56) likecs6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,497
×2,559
×593
×301
×65
×6

question asked: 20 Nov '17, 22:01

question was seen: 413 times

last updated: 26 Nov '17, 16:34