Codility - Peaks

This is the first solution of the peaks task form Codility platform:

Idea is to determine min and max size of possible block, then go through peaks and increase minimum size of the block if some peak is "out of the division". Additionally there is a list of forbidden value of sizes to avoid situation that increasing minimum size on one peak would negatively interfere with any of previous peaks.

It's very long in implementation, but intuitive, very fast && maybe original. Faster than widely published version with checking all the peaks in a loop of consecutive size of the block, if one don't use prefix sum for counting blocks. Of course 100% in Codility test.

Here is a code:


public int solution(int[] A) {
    int r;
    final int N = A.length;
    int[] B = new int[N]; // space between peaks +1
    int[] P = new int[N]; // peaks idxs
    int iP;               // max index of values in table P
    int max_bl, min_bl;
    List<Integer> list_impossible_min = new ArrayList<>();
    int[] min_max_ip = new int[3]; // temporary storage for variables

    // detemine B, P, iP, max_bl, min_bl
    getMinMaxBl(A, B, P, min_max_ip);
    min_bl = min_max_ip[0];
    max_bl = min_max_ip[1];
    iP     = min_max_ip[2];
   
    if(iP == -1){       // no peaks
      return 0;
    } else if(iP == 0){ // one peak
      return 1;
    }

    // applaying last block size
    int last_bl = N-1 -P[iP] + 1;
   
    if( last_bl > min_bl){
      min_bl = last_bl;}
    if(last_bl > B[P[iP]]){
      B[P[iP]] = last_bl;}

    // applying condition of possible divide
    while ((N % min_bl) != 0) {
      min_bl++;}
    while ((N % max_bl) != 0) {
      max_bl++;}


    for (int i = 1; i <= iP; i++) {
      int idx_peak = P[i];
      if (B[idx_peak] > min_bl) {   
        int pp = P[i-1]; // previous peak
       
        int a = (idx_peak + 1) / min_bl;
        int b = a * min_bl;
        if (b != (idx_peak + 1)) { // border of division is in between peaks
          if (b - pp > min_bl) {   // border of division is too far from pp

            // seraching for first possible new min_bl
            for (int j = min_bl + 1; j <= max_bl; j++) {
              a = (idx_peak + 1) / j;
              b = a * j;

              if (list_impossible_min.isEmpty() || !list_impossible_min.contains(j)) {
                if (N % j == 0 && (b - pp <= j)) {
                  min_bl = j;
                  break;
                }
              }
            }
          }
        }
        for (int j = min_bl + 1; j <= B[idx_peak]; j++) {
          a = (idx_peak + 1) / j;
          b = a * j;

          if (N % j != 0 || ((pp + j < idx_peak) && ( b*a-pp > j))) {
            if (pp + j < idx_peak) {
              if (list_impossible_min.isEmpty() || !list_impossible_min.contains(j)) {
                list_impossible_min.add(j);
              }
            }
          }
        }
      }
    }
    r = N / min_bl;

    return r;
  }

  private void getMinMaxBl(int[] A, int[] B, int[] P, int[] min_max_ip) {
    int N = A.length;
    int f_peak = -1, l_peak = -1;
    int iP = -1, min_bl = 0, max_bl = 0;

    // detemine max_bl, min_bl
    // first min_bl & max_bl
    for (int i = 1; i < N - 1; i++) {
      if (peak(A, i)) {
        max_bl = i+1;
        min_bl = i+1;
        f_peak = i;
        l_peak = i;
        B[i]   = i+1;
        P[++iP] = i;
        break;
      }
    }
    if(f_peak > 0){
      for(int i = f_peak+2; i < N-1; i++){
        int t_max_block;
        int t_min_block;
        if (peak(A, i)) {
          t_max_block = i - l_peak; // covers cells max empty space + 1 for peak
          t_min_block = (t_max_block + 1)/2; // covers two peaks + space between
          if((t_max_block+1)%2 != 0){
            t_min_block++;
          }
          min_bl = max(min_bl, t_min_block);
          max_bl = max(max_bl, t_max_block);
          B[i]   = t_max_block;
          l_peak = i;
          P[++iP] = i;
        }
      }
    }
    min_max_ip[0] = min_bl;
    min_max_ip[1] = max_bl;
    min_max_ip[2] = iP;
  }

  boolean peak(int[] A, int i) {
    return A[i] > A[i - 1] && A[i] > A[i + 1];
  }

Codility - NumberOfDiscIntersections

O(N) Time complexity.

Main idea: For every next circle, the number of possible pairs is equal difference between all open to this "moment" cicrcles and all that have been processed.

public int solution04(int[] A) { 
    final int N = A.length;
    final int M = N + 2;
    int[] left  = new int[M]; // values of nb of "left"  edges of the circles in that point
    int[] sleft = new int[M]; // prefix sum of left[]
    int il, ir;               // index of the "left" and of the "right" edge of the circle

    for (int i = 0; i < N; i++) { // counting left edges
      il = tl(i, A);
      left[il]++;
    }

    sleft[0] = left[0];
    for (int i = 1; i < M; i++) {// counting prefix sums for future use
      sleft[i]=sleft[i-1]+left[i];
    }
    int o, pairs, total_p = 0, total_used=0;
    for (int i = 0; i < N; i++) { // counting pairs
      ir = tr(i, A, M);
      o  = sleft[ir];                // nb of open till right edge
      pairs  = o -1 - total_used;
      total_used++;
      total_p += pairs;
    }
    if(total_p > 10000000){
      total_p = -1;
    }
    return total_p;
  }

  int tl(int i, int[] A){
    int tl = i - A[i]; // index of "begin" of the circle
      if (tl < 0) {
        tl = 0;
      } else {
        tl = i - A[i] + 1;
      }
    return tl;
  }
  int tr(int i, int[] A, int M){
    int tr;           // index of "end" of the circle
      if (Integer.MAX_VALUE - i < A[i] || i + A[i] >= M - 1) {
        tr = M - 1;
      } else {
        tr = i + A[i] + 1;
      }
      return tr;
  }

Codility - MinAvgTwoSlice

  public int solution03(int[] A) {
    final int N = A.length;
    double minSlc = (A[0] + A[1]) / 2.0;
    int indMinSlc = 0;

    for (int i = 0; i < N - 2; i++) {
      double slc = (A[i] + A[i + 1]) / 2.0;
      if (A[i + 2] < slc) {
        slc = (A[i] + A[i + 1] + A[i + 2]) / 3.0;
      }
      if (slc < minSlc) {
        minSlc = slc;
        indMinSlc = i;
      }
    }
    if ((A[N - 2] + A[N - 1]) / 2.0 < minSlc) {
      indMinSlc = N - 2;
    }

    return indMinSlc;
  }

=============
Explanation:
1. First slice consist of two elements.
2. You can lover the value of original slice by adding some new elements.
3. In order to lover the value of original slice, added elements have to have "slice value" lesser than original slice.
4. If pt. 3 is fullfilled than value of new slice created that way is bigger than slice of added elements.
5. So it has no sense try to create a new slice with lesser value by adding more than ONE element, because added elements will create a slice of even lesser value than one we try to create.
6. You can omit using double and dividing, by using multiplying and type int. But solution will less clear.

How to compare folders

1. diff -rq folder1 folder2
-r - means recursive
-q - means give only differences

2. rsync -n -avrc /abc/home/sample1/* server2:/abc/home/sample2/
https://stackoverflow.com/a/19410791

rsync -n -avr --size-only --delete /abc/home/sample1/ server2:/abc/home/sample2/

3. using "meld".
It is slow, but graphical interface

4. using "find"

A good way to do this comparison is to use find with md5sum, then a diff. Example: Use find to list all the files in the directory then calculate the md5 hash for each file and pipe it to a file: find /dir1/ -type f -exec md5sum {} \; > dir1.txt Do the same procedure to the another directory: find /dir2/ -type f -exec md5sum {} \; > dir2.txt Then compare the result two files with "diff": diff dir1.txt dir2.txt This strategy is very useful when the two directories to be compared are not in the same machine and you need to make sure that the files are equal in both directories.

 https://stackoverflow.com/questions/16787916/difference-between-two-directories-in-linux

How to partialy enter a date in libreoffice calc 5

http://przepis-na-lo.pl/2013/03/automatyczne-rozpoznawanie-niepelnych-dat/

"Nowe problemy Wprowadzona zmiana spowodowała jeden dość istotny problem — w niektórych językach niemożliwe stało się szybkie wpisywanie dat za pomocą klawiatury numerycznej. We wspomnianym języku czeskim (ponownie: tak jak w polskim) separatorem liczb dziesiętnych jest przecinek, a nie kropka. W rezultacie użytkownicy prawą ręką mogą wpisać „13,02”, „13/02” oraz „13-02”, ale nie „13.02”; tymczasem tylko ten ostatni zapis pasuje do wzorca i zostanie potraktowany jako data. Tworzenie i modyfikowanie wzorców dat Aby rozwiązać ten problem, wprowadzono możliwość samodzielnego tworzenia wzorców dat. Odpowiednie pole zatytułowane jest Akceptowane wzorce dat i znajduje się w Narzędzia → Opcje... → Ustawienia językowe → Języki. Każdy wzorzec musi składać się z przynajmniej dwóch znaków — symbolu zastępczego fragmentu daty oraz separatora. Dostępne są trzy symbole zastępcze: D (dzień), M (miesiąc) oraz Y (rok)."

How to remove a plain text protecting single quote from all the selected cells in LibreOffice Calc?

http://superuser.com/questions/394092/how-to-remove-a-plain-text-protecting-single-quote-from-all-the-selected-cells-i You can remove the leading single quote (which actually isn't part of the string in the cell) using a regex-based search and replace: Search for all characters between the start and end of the string ^.*$ replace with match &

Language tool on libreoffice on ubuntu

Just this solution

On Ubuntu, install the libreoffice-java-common or openoffice.org-java-common package. One problem solved by this is getting a long error message with "NoClassDefFoundError" during installation (see screenshot). On Ubuntu, if you get a message similar to Exception in thread "Thread-402" java.awt.HeadlessException in LibreOffice/OpenOffice, see this stackoverflow answer. Note that the message might not appear in a dialog but only on the command line, so you might want to start LibreOffice/OpenOffice from a terminal window.