LEALCO - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

EASY

PREREQUISITES:

Bitmasks, Backtracking

PROBLEM:

You are given an array R[0], R[1], …, R[N-1] and two integers K and M such that 1 ≤ M ≤ K ≤ N. We call array bad if there exists i from 0 to N-K, inclusive, such that for at least M different values of j from i to i+K-1, inclusive, we have R[j] = max{R[i], R[i+1], …, R[i+K-1]}. You can choose some subset of elements of this array and increase each element of this subset by 1 (it is the simplest and the most clear reformulation of the part where we can apply several operations, but at most one operation for each element). You need to find the smallest size of such subset which leads to not bad array.

EXPLANATION:

After figuring out subset reformulation the solution is straightforward. We just need to iterate over all subsets of the set of indexes {0, 1, …, N-1}, increase by 1 elements of the array corresponding to this subset, and check the new array for badness strictly by definition.

But let’s consider implementation of this in detail. At first let’s see how we could check that the array is bad. For this we need to loop over i from 0 to N-k according to definition. For each such i we at first find maximum among numbers R[i], R[i+1], …, R[i+K-1] and then in one additional pass we calculate how many of them equal to this maximum. See tester’s first solution as a reference of clear and commented implementation of isBad() routine.

Now when we have such check with us we only need to iterate over all subsets as mentioned above. The usual and convenient way to do this is represent subset as a binary integer which is usually called mask. Namely, the element R[i] is included to the subset if and only if the i-th bit in binary is set in mask (i-th bit corresponds to 2i). Now to iterate over all subsets we just need to loop over all numbers from 0 to 2N − 1, inclusive. To check that R[i] belongs to the subset we need to check whether (mask & 1 << i) is non-zero (using C/C++/Java notation). Here & is bitwise “and” operation and << is a left bitwise shift, so 1 << i equals to 2i. Now the pseudo code for this could be like this:

for mask = 0 to 2N − 1 do
    for i = 0 to N − 1 do
        if (bitwise "and" of mask and 2i is non-zero) then
            newR[i] = R[i] + 1
        else
            newR[i] = R[i]
    if (not isBad(newR, K, M)) then
        update the answer

To update the answer we need to count the number of ones in binary form of mask (which is the size of the subset), compare it with existing answer and update the answer if it is larger. To find the number of ones in binary we could use the similar loop over i as above. Alternatively we could use some advanced bitwise magic to calculate this number faster in general. See tester’s first solution as a reference. See also the heuristic there that helps to skip some subsets in general.

The complexity of the above solution is O(2N * (N − K + 1) * K). Here multiplier 2N corresponds to the loop over subsets, N − K + 1 corresponds to the loop over values of i in the badness check and K corresponds to the loop over j for the fixed i in the badness check.

WHEN IS THE ANSWER EQUAL TO -1?

Note that when M = 1 the answer is always -1 as mentioned in the explanation of the example case 4 in the problem statement. But in this solution we don’t use this check in order to keep it clear. We have received many comments during the contest asking whether answer -1 could be for other values of M. As you see, our solution doesn’t care about this fact, hence we did not answer on this question during the contest. But for curious minds I will answer on it finally:

The answer could be -1 for M > 1.

Probably the simplest test with this effect has the form

8 4 2
0 0 1 1 1 1 0 0

The explanation could be like that. In order to satisfy the segment [0 0 1 1] 1 1 0 0 we need to increase one of the ones on it. The same is true for the segment 0 0 1 1 [1 1 0 0]. But then on the segment 0 0 [1 1 1 1] 0 0 we will have at least two twos and we can’t fix this since we can apply operation to each element at most once.

Actually when M = 2 the answer -1 happens more or less often on the tests having R[i] equals to 0 or 1. But we did not find any such test for M = 3. So it is an open question whether such test exists.

ALTERNATIVE SOLUTION:

The problem can be solved using recursive backtracking instead of iteration over all subsets. In this way we will obtain much more efficient solution that solves the problem (with the current test data) in no time. See tester’s second solution as a reference. It contains explanatory comments to the approach.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s first solution can be found here.
Tester’s second solution can be found here.

RELATED PROBLEMS:

Codechef March 2009 Challenge – MARCHA1

8 Likes

can anybody plz tell why i’m getting wrong answer…
my submission id:1724590…
thnx in advnce…

You should define int cnt[19] instead of int cnt[18].

the backtracking solution is gr8!

2 Likes

I know it’s not needed in order to get AC, but the isBad() routine can be implemented in O(N+RMAX) time (N<=17 and RMAX can get up to 18) using a deque for finding the maximum element and a count array for maintaining the number of times each element occurs within the “current” interval of length K.

5 Likes

Thanks for pointing it out.
Actually I’ve wanted to add this but forget at some point :slight_smile:
But note that backtracking solution has complexity O(2^N * K) which is slightly better.

thanx… that was such a silly mistake…

I have mailed a query related to this question at [email protected] from id [email protected] answer it.

Related Problem is BestBats :slight_smile:

1 Like

Nice. So, let’s say we generate the 2^N masks by recursive backtracking. After every decision we make for a bit i (i.e. set it to 0 or 1) we compute the number of max. values in the interval [i-K+1,i] in O(K) time (assuming 0-based indexing and i>=K-1). We also maintain a counter with the number of 1 bits in the current mask. The total number of “decisions” (setting a bit to 0 or 1) and counter updates (+/- 1) during the backtracking is at most 2^1+2^2+…+2^N=2^(N+1)-2=O(2^N). Since we spend O(K) time per decision we get the O(2^N * K) complexity. Pretty easy.

1 Like

My understanding of (2^N * K) complexity coincide with your explanation word-by-word. You explained all very clearly.

@mugurelionut I will have to look at your O(N+RMAX) solution for isBad(). I made some optimizations to avoid the full O(N*K) penalty, but I still had pretty easy-to-hit cornercases where I had to recalculate a maximum over a K subsequence. None of this got in the way of AC, but I need to see your solution here.

@anton one tact I took was in doing a BFS and only considering altering increasing element ‘i’ if element ‘i’ was indeed a local maximum in one or more of the K-subsets which satisfied the M-drunk criteria. I think this (and some bad coding) slowed down my isBad() routine (since I also had to calculate this new mask of “M-drunk contributors”), but the upshot is that the algorithm almost alwyas terminated with fewer iterations because all of the relevant 1-edits were considered before all of the relevant 2-edits, etc. I need to think on whether this is better or worse than the backtracking solution.

1 Like

@vagrawal13
I have no access to this mailbox.
I have contacted admins.
Do you still need a reply?
You can actually post it here as an answer.

http://www.codechef.com/viewsolution/1712075
is there any chance not to get TLE in this solution? without using bitmasks

I think MARCHA1 can be considered a related problem… I easily solved LEALCO thanks to that problem

1 Like

Thanks. I have added it.

Why do you use sorting?
It slows down your solution a lot.
Your way is equivalent to using bitmasks.
But cou() function is too slow.

You mean if I remove sorting and make it (cou func O(N^2) ) it will pass?

Probably.
But still your implementation is slow.
We don’t need this double vector.
I have feeling that because of this you still could have TLE.

Consider isBad() function in tester’s solution. It is clear and commented.

Are you kidding on me?
You have check() inside the loop of filling vector test.
So complexity is O(2^N * N * (N-K+1) * K) which of course is slow.
Simply moving one brace I get AC in 0.27 max time per test:
http://www.codechef.com/viewsolution/1727641
So don’t blame STL. Vector is the last thing you should blame.
Of course if you are using it wisely.