LovesProgramming's blog

By LovesProgramming, history, 4 years ago, In English

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 ?

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

Actual solution:

Let $$$K$$$ denote the maximal value of $$$k$$$. We consider only $$$0\leq t<k$$$ as that's how modular arithmetic works. Let's analyse the function

$$$F(t)=(A+t)\%k + (B+t)\%k + (C+t)\%k$$$

for constant $$$A, B, C, k$$$. If we consider $$$F(t)$$$ as $$$t$$$ increases from $$$0$$$ to $$$N-1$$$, we notice that for the majority of the values we have $$$F(t+1)=F(t)+3$$$. The only time this isn't true is when one of the three values in the sum drops to 0. We can call these points drops and it is easy to find their place. The drops are precisely at $$$t=k-A$$$, $$$t=k-B$$$ and $$$t=k-C$$$ (with possibly some of these being the same).

It follows that $$$F(t)$$$ on the interval $$$[0, k)$$$ can be defined as a piecewise function of at most 4 intervals each being a simple linear function increasing with 3 for every next element.

Consider now a binary-search-for-the-answer approach on the original problem. The minimal value we're looking for is certainly less than $$$3k$$$ (you can give a tighter bound but it's not really necessary). Suppose we fix the answer to be less than or equal to $$$V$$$ and try to find a suitable value $$$t$$$ that achieves that. Now for each $$$1\leq i\leq N$$$ we can create a function of the kind described above. Since it consists of at most 4 linear intervals, then the values of $$$t$$$ which produce a function value at most $$$V$$$ can also be described by at most 4 intervals (prefixes of the linear intervals of the function).

Finally, once we have at most 4 suitable intervals for each $$$i$$$, we want to find a value of $$$t$$$ that is in at least one suitable interval for each $$$i$$$. We can do this by intersecting the sets of intervals one by one for each consecutive $$$i$$$. This will work fast because intersecting the union of 4 disjoint intervals with the union of another 4 disjoint intervals cannot produce more than 4 disjoint intervals. The combination of all intervals is thus O(N). If at the end there is any non-empty interval left, then we know a valid $$$t$$$ value exists. This guides the direction of the binary search.

Total complexity is $$$O(N log K)$$$. I don't know if a linear solution exists. It seems possible.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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