### LovesProgramming's blog

By LovesProgramming, history, 2 months ago, ,

Given three arrays a,b,c all of same length N. You want to minimize the value of :

max( (a(i)+t)%k + (b(i)+t)%k + (c(i)+t)%k ) , for all 1<=i<=n .

where 't' can be any non-negative integer.

Input : Three arrays of size 'N' and an integer 'k'. How to find a 't' which can minimize this value ?

• +2

 » 2 months ago, # |   0 Auto comment: topic has been updated by LovesProgramming (previous revision, new revision, compare).
 » 2 months ago, # |   +20 Please give proper statements with constraints.For example I can tell you an $O(kN)$ solution — just try all values for $t$.If this is a problem you've encountered somewhere give the constraints, as otherwise "to solve" the problem doesn't mean much.If you came up with this problem yourself and just want the fastest solution, then state that along with what's the fastest you've come up so far.
 » 2 months ago, # | ← Rev. 7 →   0 Actual solution:Let $K$ denote the maximal value of $k$. We consider only $0\leq t •  » » 2 months ago, # ^ | 0 I didn't get the last paragraph where you talked about intersecting the sets of intervals. Can you please elaborate. And also, what do you meant by suitable interval ? •  » » 2 months ago, # ^ | 0 I was thinking about it this way, let's fix a index of the array, now only those values of$t$matter which take$A$or$B$or$C$to$k-1$, because otherwise you can increase$t$. So can't you use$3$possible values of$t\$ at each index and update something? I couldn't think ahead