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

×

FRJUMP - Editorial

2
4

PROBLEM LINK:

Contest
Practice

Author: Vadym Prokopec
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa

DIFFICULTY:

medium

PREREQUISITES:

sqrt decomposition, log

PROBLEM:

You are given an array $a$ of size $n$. You have to answer following queries and update.

  • In each query, you are given two numbers - $i, r$. Let $prod = a_i \cdot a_{i + r} \cdot a_{i + 2 r} \cdot ... \cdot a_{i + k r}$, s.t. $i + k r \leq n$ and $k$ has largest possible value satisfying the equation. You to find $prod \pmod{10^9 + 7}$ and first digit of $prod$.
  • In the update operation, you can set $a_i$ to some value $v$.

QUICK EXPLANATION:

EXPLANATION:

Finding first digit and modulo value of product of some numbers
Finding product of some elements modulo some number is easy. Let us see how can we find the first digit of product of some elements. Note that direct multiplication could be very large and won't fit into any typical data type. Even if you use a big type, number of digits in the product could be huge and entire calculation will be quite slow.

As we know that sum of these elements would be quite smaller, so can we somehow represent the product of some numbers in terms of sum. We can take log of the product. Let $b_1, b_2, \dots, b_n$ be $n$ positive numbers. Let $prod = b_1 \cdot b_2 \cdot \dots \cdot b_n$. We get $log(prod) = log(b_1) + log(b_2) + .. \dots + log(b_n)$. So, given log of a number, can we find first digit of the number?
Yes, if we know the fractional part of the log value, we can get the first digit by calculating $10^{\text{fractional part}}$.
Fractional part of a double $x$ can be found by $x - floor(x)$.

Solution based on number of divisors of a number
Let us use 0 based indexing for the problem. For the given query of an integer $r$, we have to find first digit and modulo value of product $a_0, a_r, a_{2 * r}, a_{3 * r}, a_{k * r}$. Note that the indices are all multiples (including zero) of $r$. Due to this, we can realize that the update at index $i$ by setting $a_i$ to $v$, will modify the values of products for all $r$'s which are divisors of $r$ (0 is also counted).

Based on these observations, we can design a solution as follows.
Let $prod_r = a_0 \cdot a_r \cdot a_{2 * r} \cdot a_{3 * r} \cdot a_{k * r} \pmod{10^9 + 7}$.
Similarly, let $logSum[r] = log(a_0) + log(a_r) + log(a_{2 * r}) + \dots + \cdot a_{k * r}$.
Note that we can find the first digit of the product using $logSum[r]$ for a given query - $r$ as described above. In particular, it will be $pow(10, logSum[r] - floor(logSum[r])$.

For the given array, before processing all the queries, we can precalculate values of $prod_r and logSum_r$ for each $r$ from $1$ to $n$. Note that the time taken will be $\mathcal{O}(n log n)$.

Now let us see how to process the updates and query.

If we receive an update of setting $a_r$ to $v$, we will iterate over all the divisors $d$ of $r$ and update the corresponding $prod_d$ and $logSum_d$. Now if we receive a query of finding answer for given a $r$, we can directly answer it by using values of $prod_r$ and $logSum_r$.

Now, there is a small catch with the above solution. If we want to make an update at $r = 0$, then it will affect the answers of all the $prod$ and $logSum$ values. So if we directly update these values, we can take $O(n)$ in the worst case. To handle this case, we can separately maintain the value of first element, (i.e. $a_0$). So, whenever we receive an update of setting $a_0$ to some value, instead of changing all the $prod, logSum$ values, we will just change the value of first element we maintained. Note that we will have to change our update accordingly. For each query, we will have to additionally output the modified values of $prod$ and $logSum$ values respectively.

Note that this extra catch was because of the reason that $r = 1$ to $n$, all are divisors of 0. But for other numbers, this is not the case. Maximum number of divisors of a number $1 \leq n \leq 10^5$ are 128.

Hence, time complexity of this solution will be $\mathcal{O}(128 * n)$. Please note that in order to pass your solution with the given time limit, you have to implement this carefully, e.g. while update, don't calculate inverse of $a_r$ in the loop.

Time Complexity:

$\mathcal{O}(n \, 128)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester
Editorialist

This question is marked "community wiki".

asked 12 Jun '16, 12:02

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53136170
accept rate: 20%

edited 15 Jun '16, 20:31


Using double also works, just keep diving/multiplying by 10 so as to keep 1 digit before the decimal.

Example, store 1234.56789 as 1.23456789. And if on division you get to something like 0.0001234, make it 1.234.

Obviously there is some loss of precision here, but some tinkering allowed a full AC.

I wonder if a case that can stop this approach exists?

AC Code: https://www.codechef.com/viewsolution/10336910

link

answered 15 Jun '16, 15:31

grebnesieh's gravatar image

7★grebnesieh
757211
accept rate: 16%

2

Not sure but I had testcases failing due to precision. Had to add a small precision check, EPS = 1E-9 to avoid WA on certain testcases.

(15 Jun '16, 15:44) atulshanbhag4★

I had to do the same (EPS = 1E-10), but I can't see that check in grebnesieh's solution.

(15 Jun '16, 16:10) luc4sdreyer4★

The same code: https://www.codechef.com/viewsolution/10416244 https://www.codechef.com/viewsolution/10416229

One in C++ 14 gets a WA and TLE(by 0.1 sec ) and the other(in C++ 4.3.2) gets AC,these things should not happen with a programmer :(

Anyways what can be the reason ?

link

answered 15 Jun '16, 15:57

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%

not sure about the TLE, but I had the same problem with WA...one testacse was WA for me too. It is probably because of precision handling.

(15 Jun '16, 16:03) atulshanbhag4★

So,precision handling technique changes with language version ?

(15 Jun '16, 16:10) sandeep93★

probably.. updated versions might use updated pow functions right

(15 Jun '16, 17:56) atulshanbhag4★
Answer is hidden as author is suspended. Click here to view.

answered 20 Jun '16, 02:50

vinay_goel21's gravatar image

3★vinay_goel21
(suspended)
accept rate: 0%

This question was all about tackling the precision, once the algo was clear! Nice one

link

answered 15 Jun '16, 15:26

atulshanbhag's gravatar image

4★atulshanbhag
22629
accept rate: 9%

The pre-requisites mention about Square Root Decomposition, I did not understand how we are implementing Square Root Decomposition here?

link
This answer is marked "community wiki".

answered 15 Jun '16, 15:47

lohit_97's gravatar image

4★lohit_97
3428
accept rate: 4%

you are decomposing a number r into two products r = a * b. Where a <= b. Hence you need to search until square root of r only to find a and b. Hence, the name square root decomposition.

(15 Jun '16, 15:56) bhambya2★

i don't think that is what square root decomposition means...

(15 Jun '16, 16:00) atulshanbhag4★

Umm.. I am sorry, I did not quite get what you mean to say. Can you please give me some link to solution which is the implementation of what you are trying to convey?

(15 Jun '16, 16:04) lohit_974★

@adkroxx Thanks, I will check that out for sure!

(15 Jun '16, 16:50) lohit_974★

Exactly same logic as described in the editorial, still it was WA. If any body could figure out. link:https://www.codechef.com/viewsolution/10494476

link

answered 15 Jun '16, 15:55

gagan86nagpal's gravatar image

5★gagan86nagpal
11116
accept rate: 11%

You are missing out for test where you query with R = 1 as in:

3 2 8 5 1 2 1

Setting a[n+1]=1 fixes that though

(15 Jun '16, 16:50) vsp46★

Can anyone tell me why am i getting WA? Here is my code link https://www.codechef.com/viewsolution/10512326

link

answered 15 Jun '16, 18:10

coolreshab's gravatar image

6★coolreshab
112
accept rate: 0%

We can do this question using sqrt decomposition also.Divide the array into sqrt n blocks and for each block maintain an array of sqrt n size in which ith element contains information required about the product of the elements in this block due to r=i.For r>=sqrt n just calculate the answer manually(it takes O(root n))and for r< sqrt n traverse the blocks to get the information.We can update in sqrt n time by checking divisors of that particular index and update in its block. So total complexity is O(n*root n).

link

answered 15 Jun '16, 20:00

contestid's gravatar image

2★contestid
1
accept rate: 0%

I'm getting WA for subtask 2. Can somebody explain why? (I know the approach is not ideal, still) https://www.codechef.com/viewsolution/10453146

link

answered 15 Jun '16, 20:00

ssarthak15's gravatar image

3★ssarthak15
1
accept rate: 0%

Can anyone help me to optimize my code??

https://www.codechef.com/viewsolution/10504174

link

answered 15 Jun '16, 21:00

sammy00747's gravatar image

2★sammy00747
1
accept rate: 0%

If N=50,say. and we update the 12th element. Then we have to change the value of product for r=1,2,3,4,6,12. How will we do that? Do we have to iterate through each value of r?

link

answered 15 Jun '16, 21:43

rishi_07's gravatar image

5★rishi_07
31617
accept rate: 20%

I got 95 points in the question since my solution did not pass the first subtask. Can anyone explain why? https://www.codechef.com/viewsolution/10511094

link

answered 15 Jun '16, 23:16

sdnr1's gravatar image

6★sdnr1
111
accept rate: 0%

Implemented as in editorial still getting WA. Can someone figure it why? https://www.codechef.com/viewsolution/10515781

link

answered 16 Jun '16, 10:36

ojha_vivek's gravatar image

4★ojha_vivek
1
accept rate: 0%

edited 16 Jun '16, 10:38

I dont understand why this additional EPS was needed in the power of 10. Please answer...

link

answered 16 Jun '16, 14:42

tick's gravatar image

3★tick
1
accept rate: 0%

This problem could be solved without the prior knowledge of square-root decomposition. https://www.codechef.com/viewsolution/10448317

link

answered 17 Jun '16, 12:17

gupta_paras's gravatar image

5★gupta_paras
1
accept rate: 0%

I did this problem without using sqrt-decomposition...I made an array which stores the new value of friendliness at pth index during update query...I never updated the array which stores enjoyment for different values of R. During query 2, I checked whether there is an any update of friendliness int the multiples of r. In this way i updated my Answer... See my solution here for more clarity.. https://www.codechef.com/viewsolution/10384547

link

answered 18 Jun '16, 09:27

nishant_coder's gravatar image

6★nishant_coder
795
accept rate: 20%

Editorialist solution giving TLE for last 3 testcases . Why ?

link

answered 18 Jun '16, 11:46

rajan_parmar's gravatar image

5★rajan_parmar
396
accept rate: 0%

can anyone explain me how to precompute the product array in O(nlogn) ?? I am getting it in O(n*sqrt(n)) .

link

answered 18 Jun '16, 17:49

hardest_noo's gravatar image

2★hardest_noo
1
accept rate: 0%

In the editorialist code, what is the purpose of computing modulo inverse and multiplying with existing product of r along with y?

if (type == 1) {
  scanf("%d", &y);
  int iv = inv(a[x - 1]);
  long double nv = log10l((long double)y);
  for (int j = 0; j < (int)d[x - 1].size(); ++j) {
    int r = d[x - 1][j];
    prod[r] = 1LL * prod[r] * iv % MOD * y % MOD;
    slg[r] += nv - lg[x - 1];
  }
  a[x - 1] = y;
  lg[x - 1] = nv;
}
link

answered 19 Jun '16, 22:44

shiva92's gravatar image

3★shiva92
111
accept rate: 0%

edited 19 Jun '16, 22:45

How do I get an idea of this type of solution?

link

answered 30 Jun '16, 07:58

suraj021's gravatar image

3★suraj021
91
accept rate: 0%

Can anyone explain me the setter's code: for (int i=1; i<=min(pos-1, sq); i++){ if ((pos-1)%i==0){ dig[i]-=log10(a[pos]+0.0); dig[i]+=log10(val+0.0); remain[i]=inv; remain[i]%=inf; remain[i]=val; remain[i]%=inf; Should'nt this be just min(pos,sq) as the setter had done 1 based indexing in his code?

link

answered 19 Jul '16, 23:43

akaashhazarika's gravatar image

2★akaashhazarika
1
accept rate: 0%

i am using the same algo as given in solution still i am getting only 95 points. plz help. solution link- https://www.codechef.com/viewsolution/10910270

link

answered 26 Jul '16, 13:53

ipg_2013's gravatar image

3★ipg_2013
115
accept rate: 0%

Problem is with precision.

(27 Jul '16, 09:36) apptica5★
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,629
×2,575
×289
×66
×24
×6

question asked: 12 Jun '16, 12:02

question was seen: 9,677 times

last updated: 27 Jul '16, 09:36