Command Line to Convert Images for Stickers

The following tutorial is for macOS

brew update && brew install imagemagick

to your folder for the candidate images for stickers

convert all jpg & jpeg to png

magick mogrify -format png *.jpg
magick mogrify -format png *.jpeg

for all the pngs, resize to be within 512x512

magick mogrify -resize 512x512 *.png

Afterwards, this folder of images meet the requirements for telegram stickers

Flags 100% Solution in Javascript

Question

Solution

function solution(A) {
    
    let peaks = new Array(A.length).fill(false);
    let peakCount = 0;
    for (let i = 1; i < A.length-1; i++) {
        if (A[i-1] < A[i] && A[i] > A[i+1]) {
            peaks[i] = true;
            peakCount++;
        }
    }
    
    if (peakCount === 0 || peakCount === 1) 
        return peakCount;
    
    let left = 2;
    let right = peakCount;
    let result;
    
    while (left <= right) {
        let middle = Math.floor((left+right)/2);
        let success = CheckFlags(peaks, middle);
        if (success) {
            result = middle;
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    
    return result;

}

function CheckFlags(peaks, flags) {
    
    let minGap = flags;
    let pos = 0;
    
    while (pos < peaks.length && flags > 0) {
        if (peaks[pos]) {
            flags--;
            pos += minGap;
        } else {
            pos++;
        }
    }
    
    return flags === 0;
}

Note

Binary Search! or you will get 66% result because of time out

while (left <= right) {
  let middle = Math.Floor((left + right)/2);
  let success = checkFlags();
  if (success) {
    result = middle;
    left = middle + 1;
  } else {
    right = middle -1;
  }
}

return middle;

StackOverFlow of my 80% solution

Official Answer https://codility.com/media/train/solution-flags.pdf

Peaks 100% Solution in Javascript

Question

Solution

function solution(A) {
    
    let prefixSumPeaks = new Array(A.length+1).fill(0);
    let peakArray = new Array(A.length).fill(0);
    let peakCount = 0;
    
    for (let i = 1; i < A.length-1; i++) {
        if (A[i-1] < A[i] && A[i] > A[i+1]) {
            peakArray[i] = 1;
            peakCount++;
        }
    }
    
    if (peakCount === 0 || peakCount === 1) 
        return peakCount;
    
    for (let i = 1; i < prefixSumPeaks.length; i++) {
        prefixSumPeaks[i] = prefixSumPeaks[i-1] + peakArray[i-1];
    }
    
    let blocks;
    
    for (blocks = peakCount; blocks >= 1; blocks--) {
        
        if (A.length % blocks !== 0)
            continue;
        
        let blockSize = A.length / blocks;
        let lackOfPeak = false;
        
        for (let i = 1; i <= blocks; i++) {
            if (prefixSumPeaks[blockSize*i] - prefixSumPeaks[blockSize*(i-1)] === 0) {
                lackOfPeak = true;
                break;
            }
        }
        
        if (!lackOfPeak) 
            break;
    }
    
    return blocks;
}

Note

Beware of the prefix sum calculation and all the upper bound of for-loop.

https://codility.com/media/train/3-PrefixSums.pdf

Why the complexity is O(n log(log(n)))?

MinPerimeterRectangle 100% Solution in Javascript

Question

Solution

function solution(N) {
    
    let min = Number.MAX_SAFE_INTEGER;
    
    for (let i = 1; i*i <= N; i++) {
        if (N%i === 0) {
            min = Math.min(min, i + N/i);
        }
    }

    return 2*min;
}

CountFactors 100% Solution in Javascript

Question

Solution

function solution(N) {
    
    let count = 0;
    let i = 1;
    
    while (i*i < N) {
        if (N % i === 0) {
            count += 2;
            // console.log(i);
        } 
        i += 1;
    }
    
    if (i*i === N) {
        count += 1;
    }
    
    return count;
    
}

MaxDoubleSliceSum 100% Solution in python

Question

app.codility.com

My Solution

app.codility.com

def solution(A):
    
    fromStartMaxEnding = [0] * len(A)

    for i in range(1, len(A)-1):
        fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i])
    
    fromEndMaxEnding = [0] * len(A)
    
    for i in range(len(A)-2, 0, -1):
        fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i])
    
    ans = -1 * 2**23
    for i in range(1, len(A)-1):
        ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1])
    
    return ans

Note

rafal.io It seems that this algorithm doesn't handle with the situation in which all the elements in A is negative? I think the trick is that the selection triplet can be (1, 2, 3), which actually selects nothing from the definition yielding the answer to be zero as calculated by this algorithm.

MaxSliceSum 100% Solution in python

Question

app.codility.com

My Solution

app.codility.com

def solution(A):
    
    allNegative = 1
    maxNegative = -1 * 2**31
    for i in range(len(A)):
        if A[i] > 0:
            allNegative = 0
            break
        elif A[i] > maxNegative:
            maxNegative = A[i]
    
    if allNegative == 1:
        return maxNegative
    
    maxEnding = 0
    maxSlice = 0
    
    for i in range(len(A)):
        maxEnding = max(0, maxEnding+A[i])
        maxSlice = max(maxEnding, maxSlice)
    
    return maxSlice

Note

Pay attention to the negatives!