CodeForces - Maximum Value (484B, #276)

general
,
1

Hi guys,

I’m trying to understand the approach for Maximum Value.

Even when I read the editorial, it’s not clear to me.

We have two (not necessarily distinct) number a and b from an array, such that a >= b and we want to maximize the value a % b by smartly choosing a and b.

In editorial, multiplies of b are used and I do not understand how those helps.

I’m not able to understand it also reading this neat implementation.

Of course, brute force approach is easy (so good for testing), but too slow for centest.

max = 0
for a in A
    for b in A
        if ( a > b ) max = max( max, a % b )
return max

Thanks

edit:

I found this comment, so I have think about what’s said there…

2 Likes
2

We know that for a number M maximum value we can get is M-1 as (M-1)%M is (M-1), similarly 2*M-1,3*M-1 … will also give the same result.Now what is next greater value, obviously (M-2) then (M-3) and so on. So why check all numbers, we will just find 2*M,3*M,4*M… and then for each value a number just smaller than it(Why?). Becuase of above property.

Overall we sort the array and for every number we first find the multiples of the number and then the number just smaller than it’s corresponding multiple present in the array using binary search.
(In editorial it says this can be done in O(1) instead of binary search. I can’t figure that out.)

For example let sorted array be [5,6,7,11,12,13,16,17,18,19]
Let’s take 5’s multiples [10,15,20]

Number just less than 10–> 7 —>(7%5=2)
Number just less than 15–> 13 —>(13%5=3)
Number just less than 20–> 19 —>(19%5=4)
Maximum of 2,3,4 is 4.

See how we didn’t check for 6,11,12,16,17 and 18,now we will do it for every number in the array.
Accepted solution

2 Likes
3

Thanks @xpertcoder,

your description helped me a lot, even when I had to read it several times.

If I have to describe it with my own words - for fixed b, we have to find max a in intervals ( k*b; (k+1) * b ) where k = 1, 2, 3 … (we end when interval starts after array max element)

To find the max we can use binary search or O(1) approach, where you can precompute for all values (max is a million) first lower number, so for array let say 2, 4, 5 your precomputed array p will be 0 0 0 2 2 4 - p[3] is 2 ~ first number lower than 3 is 2 and so on…

edit:

I tried to use TreeSet.lower() instead of binary search in Java, but this is too slow, which is kind of surprising…

1 Like
4

Even I was having trouble to convert my thoughts to words :stuck_out_tongue: .Happy to see you got an AC :slight_smile: