FRJUMP - Editorial

editorial
, , , , ,
15

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

16

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… CodeChef: Practical coding for everyone

17

Editorialist solution giving TLE for last 3 testcases . Why ?

18

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

19

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;
}
20

Another much easier method is to pre-compute answer for 1<= R<= min( N, 300). For R> 300 compute by iterating over 0 to N- 1, which takes O( N/ 300) since we make a jump of >300 during iteration. To update just alter the pre-computed values which takes O( min( 300, N)). So overall complexity becomes O( Q*N/300).

AC sol: CodeChef: Practical coding for everyone

1 Like
21

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

22

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?

23

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

24

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.

1 Like
25

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.

26

i don’t think that is what square root decomposition means…

27

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.

28

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?

29

So,precision handling technique changes with language version ?

30

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

31

@lohit_97 check this out KOL15C - Editorial - editorial - CodeChef Discuss

32

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

33

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

34

probably… updated versions might use updated pow functions right