FRJUMP - Editorial

editorial
, , , , ,
21

Can anyone help me to optimize my code??

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

22

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?

23

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

24

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

25

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

26

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

27

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

28

Editorialist solution giving TLE for last 3 testcases . Why ?

29

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

30

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

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: https://www.codechef.com/viewsolution/10561636

1 Like
32

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

33

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?

34

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

35

Problem is with precision.