code: https://ide.codingblocks.com/s/401284
problem : https://codeforces.com/contest/1165/problem/E
In the solution Im not able to understand how modulo is being used. More specifically I don’t understand why it is used multiple times and still the solution is correct.
Hey @raghav007
There are 2 properties of modulo
(A+B)%C== (A%C +B%C)%C
(A*B)%C ==(A%C*B%C)%C
can be extended to multiple vars
these 2 are clubbed there in this solution
oh alright, the second thing I’m not able to understand is that how are the we able to get away with sorting the elements of array a even though the question says we have to rearrange elements of b.
Hey @raghav007
basically u have to map elements between a and b
it doesnot matter whether u reorder A or B
okay thanks, why did we multiply a[i] and (i+1)(n-1) separately
Please elaborate on this
Like u are asking why there is 1ll in between
Actually u can keep them in any order it doesnot matter
Its multiplication
1ll is multiplied to avoid overflow on RHS
yeah that too but I was wondering that why didn’t we just do a[i]*b[i] *(i+1)(n-1) and then take the mod
In solution they sorted the vector after calculating v[i].first and v[i].second
Please read the editorial
" Okay, now we can see that for each position ii we have the value a[i]b[i](i-1)(n-1). The only non-constant value there is b[i] "
how is b[i] the only non constant value.
why not use the formula a[i] b[i] (i-1)(n-1) directly
Because we can reorder b[i]
How will u make sure that the value that needs to be minimized is minimizing
See there are 4 terms involved a[i] i (n-i+1) and b[i] to calculate that value
So we can reorder b[i]
so what we are doing is multiplying the rest 3 and sorting them
Now they are in inc/dec manner
and we also sorted b in revrse of this so
and then we multiply this ensures we get min value
DO A DRY RUN
I got it now, but wouldn’t it still work if sort a and b accordingly and then take sum of a[i] b[i] (i-1) (n-1)
No it will not because other terms will also affect the final value
so we need to sort the product of those three terms first
and then multiply b in it
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.