Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jul 14th, 2012  |  syntax: None  |  size: 2.96 KB  |  hits: 14  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. array median transformation minimum steps
  2. #include <cstdio>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. int bc[1<<15];
  7. const int M = (1<<15) - 1;
  8.  
  9. void setMin(int& ret, int c)
  10. {
  11.     if(c < ret) ret = c;
  12. }
  13.  
  14. void doit(int n, int mask, int currentSteps, int& currentBest)
  15. {
  16.     int numMax = bc[mask>>15] + bc[mask&M];
  17.     if(numMax == n) {
  18.         setMin(currentBest, currentSteps);
  19.         return;
  20.     }
  21.     if(currentSteps + 1 >= currentBest)
  22.         return;
  23.     if(currentSteps + 2 >= currentBest)
  24.     {
  25.         if(numMax * 2 >= n) {
  26.             setMin(currentBest, 1 + currentSteps);
  27.         }
  28.         return;    
  29.     }  
  30.  
  31.     if(numMax < (1<<currentSteps)) return;
  32.  
  33.     for(int i=0;i<n;i++)
  34.     {
  35.         int a = 0, b = 0;
  36.         int c = mask;
  37.         for(int j=i;j<n;j++)
  38.         {
  39.             c |= (1<<j);
  40.             if(mask&(1<<j)) b++;
  41.             else a++;
  42.             if(b >= a) {
  43.                 doit(n, c, currentSteps + 1, currentBest);
  44.             }
  45.         }
  46.     }
  47. }
  48.  
  49. int v[32];
  50. void solveCase() {
  51.     int n;
  52.     scanf(" %d", &n);
  53.     int maxElement = 0;
  54.     for(int i=0;i<n;i++) {
  55.         scanf(" %d", v+i);
  56.         if(v[i] > maxElement) maxElement = v[i];
  57.     }
  58.     int mask = 0;
  59.     for(int i=0;i<n;i++) if(v[i] == maxElement) mask |= (1<<i);
  60.     int ret = 0, p = 1;
  61.     while(p < n) {
  62.         ret++;
  63.         p *= 2;
  64.     }
  65.     doit(n, mask, 0, ret);
  66.     printf("%dn",ret);
  67. }
  68.  
  69. main() {
  70.     for(int i=0;i<(1<<15);i++) {
  71.         bc[i] = bc[i>>1] + (i&1);
  72.     }
  73.     int cases;
  74.     scanf(" %d",&cases);
  75.     while(cases--) solveCase();
  76. }
  77.        
  78. [6 1 5 9 3 2 0 7 4 8]
  79.        
  80. [6 1 5 9 9 2 0 7 4 8]
  81.        
  82. [6 9 9 9 9 2 0 7 4 8]
  83.        
  84. [9 9 9 9 9 9 9 9 4 8]
  85.        
  86. [9 9 9 9 9 9 9 9 9 9]
  87.        
  88. For each group of consecutive maximal elements in original array:
  89.   Mark corresponding element in the matrix and clear other elements
  90.   For each matrix diagonal, starting with one, containing this element:
  91.     For each marked element in this diagonal:
  92.       Retrieve current number of turns from this matrix element
  93.       (use indexes of this matrix element to initialize p1 and p2)
  94.       p2 = end of the group
  95.       p1 = start of the group
  96.       Decrease p1 while it is possible to keep median at maximum value
  97.       (now all values between p1 and p2 are assumed as maximal)
  98.       While p2 < N:
  99.         Check if number of maximal elements in the array is >= N/2
  100.           If this is true, compare current number of turns with the best result
  101.                and update it if necessary
  102.           (additional matrix with number of maximal values between each pair of
  103.             points may be used to count elements to the left of p1 and to the
  104.             right of p2)
  105.         Look at position [p1, p2] in the matrix. Mark it and if it contains
  106.             larger number of turns, update it
  107.         Repeat:
  108.           Increase p1 while it points to maximal value
  109.           Increment p1 (to skip one non-maximum value)
  110.           Increase p2 while it is possible to keep median at maximum value
  111.         while median is not at maximum value
create a new version of this paste RAW Paste Data