Geek asks and answers

Minimum Conversion Steps

Given an array A with n integers. In one move, you can apply after the operation to any sequential subarray A [l..r]: assign to all A I (l <= i <= r) the median of the subarray A [l..r]. Let max be the maximum integer A. We want to know the minimum number of operations needed to change A to an array of n integers, each with a value of Maximum. For example, let A = [1, 2, 3]. We want to change it to [3, 3, 3]. We can do this in two operations, first for subarray A [2..3] (after which A is [1, 3, 3]), then an operation with A [1..3]. In addition, the median is defined for some array A as follows. Let B be the same array A, but sorted in a non-decreasing order. Median A is equal to B m (based on 1 indexing), where m is (n div 2) +1. Here "div" is an integer division operation. So,for a sorted array with 5 elements, the median is the third element and for sorting an array with 6 elements, this is the 4th element.

Since the maximum value of N is 30. I was thinking about gross coercion to result could be the best solution.

+5
source share
3 answers

This is a problem from codechef Long Contest. Since the contest has already ended, it’s so inconvenient, I insert the approach with setting up the problem (Source: CC Contest Editorial Page).

" 1, , max 0. DP R [mask] O (n). ( ), statest , , DP. DP , max. , [l; r], 1- 0- [l; r], . , l r ( , O (n)). , ++ ."

C/++:

#include <cstdio>
#include <iostream>
using namespace std;

int bc[1<<15];
const int M = (1<<15) - 1;

void setMin(int& ret, int c)
{
    if(c < ret) ret = c;
}

void doit(int n, int mask, int currentSteps, int& currentBest)
{
    int numMax = bc[mask>>15] + bc[mask&M];
    if(numMax == n) {
        setMin(currentBest, currentSteps);
        return;
    }
    if(currentSteps + 1 >= currentBest)
        return;
    if(currentSteps + 2 >= currentBest)
    {
        if(numMax * 2 >= n) {
            setMin(currentBest, 1 + currentSteps);
        }
        return;    
    }  

    if(numMax < (1<<currentSteps)) return;

    for(int i=0;i<n;i++) 
    {
        int a = 0, b = 0;
        int c = mask;
        for(int j=i;j<n;j++)
        {
            c |= (1<<j);
            if(mask&(1<<j)) b++;
            else a++;
            if(b >= a) {
                doit(n, c, currentSteps + 1, currentBest);
            }
        }
    }
}

int v[32];
void solveCase() {
    int n;
    scanf(" %d", &n);
    int maxElement = 0;
    for(int i=0;i<n;i++) {
        scanf(" %d", v+i);
        if(v[i] > maxElement) maxElement = v[i];
    }
    int mask = 0;
    for(int i=0;i<n;i++) if(v[i] == maxElement) mask |= (1<<i);
    int ret = 0, p = 1;
    while(p < n) {
        ret++;
        p *= 2;
    }
    doit(n, mask, 0, ret);
    printf("%d\n",ret);
}

main() {
    for(int i=0;i<(1<<15);i++) {
        bc[i] = bc[i>>1] + (i&1);
    }
    int cases;
    scanf(" %d",&cases);
    while(cases--) solveCase();
}
+2

, . 2, . 4, 2 , 4, . 8 . log2 (N), . N 30, .

(.. ), .

1. , 4 8 . .

2: . 10, :

[6 1 5 9 3 2 0 7 4 8]

, op , . , A [4... 5] :

[6 1 5 9 9 2 0 7 4 8]

4- , 4... 5, , A [2... 5], :

[6 9 9 9 9 2 0 7 4 8]

8, A [1... 8], :

[9 9 9 9 9 9 9 9 4 8]

16 , 10 , A [1... 10] :

[9 9 9 9 9 9 9 9 9 9]

3: , , . , .

+5

. N = 30. . , . , O (N 4).

, , .

, , . , 1 , X- M, 2 , Y- M, X + Y + 1 . M * 4. Y 2 X + 1 1. M * 2 M/2 ( , Y). , X + Y + 1, M * 4 , . , ( Y > 1, ). (M), . ( ).

In order to work with one group of consecutive maximum elements, we need to track only two values: the start and end positions of the group. This means that you can use a triangular matrix to store all possible groups, which allows you to use a dynamic programming algorithm.

Pseudo Code:

For each group of consecutive maximal elements in original array:
  Mark corresponding element in the matrix and clear other elements
  For each matrix diagonal, starting with one, containing this element:
    For each marked element in this diagonal:
      Retrieve current number of turns from this matrix element
      (use indexes of this matrix element to initialize p1 and p2)
      p2 = end of the group
      p1 = start of the group
      Decrease p1 while it is possible to keep median at maximum value
      (now all values between p1 and p2 are assumed as maximal)
      While p2 < N:
        Check if number of maximal elements in the array is >= N/2
          If this is true, compare current number of turns with the best result \
               and update it if necessary
          (additional matrix with number of maximal values between each pair of
            points may be used to count elements to the left of p1 and to the
            right of p2)
        Look at position [p1, p2] in the matrix. Mark it and if it contains \
            larger number of turns, update it
        Repeat:
          Increase p1 while it points to maximal value
          Increment p1 (to skip one non-maximum value)
          Increase p2 while it is possible to keep median at maximum value
        while median is not at maximum value

To keep the algorithm simple, I did not mention special cases when a group starts at position 0 or ends at position N, skips initialization and does not make any optimizations.

+1
source

More articles:


All Articles