Sheng – Page 29 – Code Says

Solution to nu2011 (Double-Median) by codility

5 Mar

Question: https://codility.com/demo/take-sample-test/double_median Question Name: nu2011 or DoubleMedian For the given queries, we need to find the median in two sorted arrays of different lengths. Then we need to find out the median of the query results. That is, we need … Read More »

Solution to oxygenium2014 (Count-Bounded-Slices) by codility

27 Feb

Question: https://codility.com/programmers/challenges/oxygenium2014 Question Name: oxygenium2014 or CountBoundedSlices For this question, I was unable to solve it with a golden answer. Instead, I tried to get two silver solutions. Both of them cheated the grading system to have the detected time … Read More »

Generate a subset in a uniformly random manner

21 Feb

Question: To generate a K-subset in a uniformly random manner from N elements. We have two slightly different solutions. The first one is quite straightforward: shuffle the elements, and then return the first K elements. In such solution, the space … Read More »

Solution to Common-Prime-Divisors by codility

18 Feb

Question: https://codility.com/demo/take-sample-test/common_prime_divisors Question Name: CommonPrimeDivisors

def gcd(x, y):

''' Compute the greatest common divisor.

'''

if x%y == 0:

return y;

else:

return gcd(y, x%y)

def removeCommonPrimeDivisors(x, y):

''' Remove all prime divisors of x, which also exist in y. And

return the remaining part of x.

'''

while x != 1:

gcd_value = gcd(x, y)

if gcd_value == 1:

# x does not contain any more

# common prime divisors

break

x /= gcd_value

return x

def hasSamePrimeDivisors(x, y):

gcd_value = gcd(x, y) # The gcd contains all

# the common prime divisors

x = removeCommonPrimeDivisors(x, gcd_value)

if x != 1:

# If x and y have exactly the same common

# prime divisors, x must be composed by

# the prime divisors in gcd_value. So

# after previous loop, x must be one.

return False

y = removeCommonPrimeDivisors(y, gcd_value)

return y == 1

def solution(A, B):

count = 0

for x,y in zip(A,B):

if hasSamePrimeDivisors(x,y):

count += 1

return count

Solution to Chocolates-By-Numbers by codility

17 Feb

Question: https://codility.com/demo/take-sample-test/chocolates_by_numbers Question Name: Chocolates-By-Numbers or ChocolatesByNumbers When we met with an empty wrapper, we must have been this position for twice. We use i for the first time and j for the second time. Due to the modulo feature, … Read More »

Solution to upsilon2012 (Cartesian-Sequence) by codility

17 Feb

Question: https://codility.com/demo/take-sample-test/cartesian_sequence Question Name: upsilon2012 or CartesianSequence A straightforward solution would be construct the Cartesian tree, compute its height, and return the height plus one. But any left sub-tree would never be accessed or changed after its construction. And so … Read More »

A guide to deploying a cache system to WordPress on AppFog

17 Feb

AppFog is a cloud platform, supporting PHP, Ruby, Java, and so on. It is a good and free solution for small website, like personal blogs. My blog (codesays.com) is currently hosted on AppFog. But AppFog does not support persistent file … Read More »

Solution to chi2012 (Cannonballs) by codility

7 Feb

Question: https://codility.com/demo/take-sample-test/chi2012/ Question Name: chi2012 or Cannonballs

def solution(A, B):

to_fall = [-1] * (max(B) + 1) # Store where the ball should

# fall. to_fall[i] = j means,

# the cannonball, which is shot

# from heigth of i, will fall

# at position j.

# Scan and find the initial falling position for cannonballs

# from each different shooting height.

current_pos = 0 # Index for the landscape array A.

# For all shooting heigthes <= A[0], the cannonballs do not

# change the landscape. Keep the content being -1 and no need

# to try them.

for height in xrange( A[0]+1, max(B)+1 ):

while current_pos < len(A) and height > A[current_pos]:

current_pos += 1

if current_pos == len(A):

# No position could prevent the cannonball from flying

# beyond the bound. These cannonballs do not change

# the landscape. Keep the content being -1.

break

else:

# The cannonball meets with a high enought position,

# and falls at the previous position.

to_fall[height] = current_pos - 1

for cannonball in B:

if to_fall[cannonball] == -1:

# This cannonball would not change the landscape.

continue

else:

fall_pos = to_fall[cannonball]

A[ fall_pos ] += 1 # increases the ground by 1

# For shooting height > A[fall_pos], the increase

# is NOT enought to block/change their flying

# path.

# For shooting height < A[fall_pos] <= old A[fall_pos]

# they cannot fly beyond this position both

# before and after increase. NO change is

# made for them.

# ONLY for shooting height = A[fall_pos], its

# flying path might be changed due to the

# increase.

to_fall[ A[ fall_pos ] ] = min(

to_fall[ A[ fall_pos ] ], fall_pos-1)

return A

Solution to Min-Avg-Two-Slice by codility

6 Feb

Question: https://codility.com/demo/take-sample-test/min_avg_two_slice Question Name: MinAvgTwoSlice The key to solve this task is these two patterns: (1) There must be some slices, with length of two or three, having the minimal average value among all the slices. (2) And all … Read More »

Solution to gamma2011 (Count-Palindromic-Slices) by codility

5 Feb

Question: https://codility.com/demo/take-sample-test/count_palindromic_slices Question Name: CountPalindromicSlices This task is based on the longest palindromic substring question, which has a good solution naming Manacher’s algorithm. Some explanation about the algorithm could be found here (English) and here (Chinese).

def palindrome_substring(str):

''' Input: string

Attention: the input string will be extended. For example,

original string abc would be converted into #a#b#c#.

Output: array, to say palindrome_len.

palindrome_len[i] records the half width (include

the element in position i) of palindrome substring,

which centers in position i.

Method: Manacher's algorithm

Time complexity: O(n)

'''

str = "#" + "#".join(str) + "#" # Convert the original string so

# that, every palindrome substring

# in the new string has odd number

# of elements.

palindrome_len = [0] * len(str) # Store the half width (include the

# center point) of the longest

# palindrome substring with index

# being the substring's center.

# palindrome_len[i]-1 means the full

# length of palindrome substring in

# the original string.

bound = 0 # Record the first positin, that the previous computed

# palindrome substrings chould NOT achieve.

center = 0 # Record the center position of the substring, which

# is corresponding to "bound".

for index in xrange(len(str)):

if bound > index:

# Part of current substring has already been compared.

# For point "index", 2*center-index is the point

# symmetrical to the points "center".

palindrome_len[index] =

min( palindrome_len[2*center-index], bound-index )

else:

# None of current substring has been compared.

palindrome_len[index] = 1

# Compare the uncompared elements one by one.

while index-palindrome_len[index] >= 0 and

index+palindrome_len[index] < len(str) and

str[index-palindrome_len[index]] ==

str[index+palindrome_len[index]]:

palindrome_len[index] += 1

if bound < palindrome_len[index] + index:

# The bound has been extended.

center = index

bound = palindrome_len[index] + index

return palindrome_len

def solution(S):

# With center point i, if the longest palindrome substring

# has length of j, the number of palindrome substrings,

# with the same center, is j//2.

count = sum([

(length-1)/2 for length in palindrome_substring(S) if length>2

])

if count > 100000000:

return -1

else:

return count

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...