The problem is the following:

A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N − 1. There is a number written on each square. A non-empty array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game.

At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N − 1.

During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K.

After the game finishes (when the pebble is standing on square number N − 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.

For example, given the following array:

A[0] = 1

A[1] = -2

A[2] = 0

A[3] = 9

A[4] = -1

A[5] = -2

one possible game could be as follows:the pebble is on square number 0, which is marked;

we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3;

we throw 5; the pebble does not move, since there is no square number 8 on the board;

we throw 2; the pebble moves to square number 5; we mark this square and the game ends.

The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.Write a function:

func Solution(A []int) int

that, given a non-empty array A of N integers, returns the maximal result that can be achieved on the board represented by array A.

For example, given the array

A[0] = 1

A[1] = -2

A[2] = 0

A[3] = 9

A[4] = -1

A[5] = -2

the function should return 8, as explained above.Assume that:

N is an integer within the range [2..100,000];

each element of array A is an integer within the range [−10,000..10,000].

Complexity:expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

**Solution: **

Algo: We use Dynamic programming. Here’s a good blog to learn it.

Basically, we start from the destination position, and consider moves to that from 6 places behind. And then move back, and check for the best way to move to the target with max val. We come back this way to position ‘0’ and then simply return dp_arr[0].

Below’s the code :

package solution

// you can also use imports, for example:

// import “fmt”

// import “os”// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)func Solution(A []int) int {

// write your code in Go 1.4N := len(A)

dp_arr := make([]int, N)

dp_arr[N-1] = A[N-1]for i := N – 2; i >= 0; i– {

var max int

for j := 1; j = N {

break

}

if j == 1 || dp_arr[i+j] > max {

max = dp_arr[i+j]

}

}

dp_arr[i] = A[i] + max

}return dp_arr[0]

}

A rather short piece of code, for a problem, which may look daunting in the first go. And this scores 100% on codility. Works in O(N) time.

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,

max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),

if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:A[0] = 3

A[1] = 4

A[2] = 4

A[3] = 6

A[4] = 1

A[5] = 4

A[6] = 4

the values of the counters after each consecutive operation will be:(0, 0, 1, 0, 0)

(0, 0, 1, 1, 0)

(0, 0, 1, 2, 0)

(2, 2, 2, 2, 2)

(3, 2, 2, 2, 2)

(3, 2, 2, 3, 2)

(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.Write a function:

func Solution(N int, A []int) []int

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

a structure Results (in C), or

a vector of integers (in C++), or

a record Results (in Pascal), or

an array of integers (in any other programming language).

For example, given:A[0] = 3

A[1] = 4

A[2] = 4

A[3] = 6

A[4] = 1

A[5] = 4

A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.Assume that:

N and M are integers within the range [1..100,000];

each element of array A is an integer within the range [1..N + 1].

Complexity:expected worst-case time complexity is O(N+M);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution: If we do it without thinking of time complexity, we will get a O(N*M) solution. But the problem wants a O(N+M) solution. So first we loop for M, to find all the max ops, and the max value of the last max_op. Taking into account the inc() operations on a same position, to compute thread max (local max)

After that, we loop for the remaining of N, after having initialized the counters to max vals. And just do the counter ops

Code:

package solution

// you can also use imports, for example:

// import “fmt”

// import “os”// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)func Solution(N int, A []int) []int {

// write your code in Go 1.4global_max := 0

global_max_pos := -1

thread_max := 0

my_map := make(map[int]int)

for i, v := range A {

if v <= N {

count, ok := my_map[v]

if !ok {

my_map[v] = 1

if thread_max < 1 {

thread_max = 1

}

} else {

tmp := count + 1

my_map[v] = tmp

if thread_max < tmp {

thread_max = tmp

}

}

} else {

global_max += thread_max

global_max_pos = i

// reset

my_map = make(map[int]int)

thread_max = 0

}

}ret := make([]int, N)

for i := 0; i < N; i++ {

ret[i] = global_max

}for i := global_max_pos + 1; i < len(A); i++ {

ret[A[i]-1]++

}

return ret

}

It works in O(N+M) and scores 100% on codilty.

The problem:

You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:

with your first step you can stand on rung 1 or 2,

if you are on rung K, you can move to rungs K + 1 or K + 2,

finally you have to stand on rung N.

Your task is to count the number of different ways of climbing to the top of the ladder.For example, given N = 4, you have five different ways of climbing, ascending by:

1, 1, 1 and 1 rung,

1, 1 and 2 rungs,

1, 2 and 1 rung,

2, 1 and 1 rungs, and

2 and 2 rungs.

Given N = 5, you have eight different ways of climbing, ascending by:1, 1, 1, 1 and 1 rung,

1, 1, 1 and 2 rungs,

1, 1, 2 and 1 rung,

1, 2, 1 and 1 rung,

1, 2 and 2 rungs,

2, 1, 1 and 1 rungs,

2, 1 and 2 rungs, and

2, 2 and 1 rung.

The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.Write a function:

func Solution(A []int, B []int) []int

that, given two non-empty arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].

For example, given L = 5 and:

A[0] = 4 B[0] = 3

A[1] = 4 B[1] = 2

A[2] = 5 B[2] = 4

A[3] = 5 B[3] = 3

A[4] = 1 B[4] = 1

the function should return the sequence [5, 1, 8, 0, 1], as explained above.Assume that:

L is an integer within the range [1..50,000];

each element of array A is an integer within the range [1..L];

each element of array B is an integer within the range [1..30].

Complexity:expected worst-case time complexity is O(L);

expected worst-case space complexity is O(L) (not counting the storage required for input arguments).

Solution: Screen cap of sublime text, below. Has all the code. It uses fibonacci series. It is so because no. of unique ways of climbing upto a step N, is sum of no. of unique ways of upto its two previous rungs. The code comment (in the screen grab, explains the reason.

Also, the above solution, worked (100%, Yay!) in the first try. Results below.

Algorithm:

For each pair of numbers in the list:

1) First find the GCD of the given pair of numbers

2) Do some boundary checks like at least one number greater than 1 and also GCD greater than 1 (Note GCD of 1 denotes, that there are no common prime divisors)

3) Now take the remainder of each number by dividing by GCD.

4) Take the GCD of the remainder with the GCD got in step 1. If the new GCD is 1 then discard this pair, as it shows no common divisors.

Logic: The GCD is of the form p1^x1*p2^x2…pn^xn, for prime numbers p1 through pn, and x1..xn are in the set [1…Z], Z is greater than 1. So if we get a remainder, which does not share a single prime number with the GCD1 then, it means the prime divisors are not the same of the two numbers.

5) If all stages pass increment the result count, as by now we are sure that the two given numbers have the same prime divisors.

package main

// you can also use imports, for example:

import “fmt”// import “os”

import “math”// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)func Solution(A []int, B []int) int {

// write your code in Go 1.4N := len(A)

ret := 0

for_label:

for i := 0; i min_ab {

continue

}if gcd1 == 1 && min_ab > 1 {

continue

}arem := a / gcd1

for arem > 1 {

gcd2 := gcd(arem, gcd1)

if gcd2 == 1 {

continue for_label

}

arem /= gcd2

}

brem := b / gcd1

for brem > 1 {

gcd2 := gcd(brem, gcd1)

if gcd2 == 1 {

continue for_label

}

brem /= gcd2

}

fmt.Printf(“a: %v, b: %v\n”, a, b)

ret++

}return ret

}// Greatest common divisor

func gcd(a, b int) int {

if a == b {

return a

} else if a > b {

if a%b == 0 {

return b

}

return gcd(a%b, b)

} else {

if b%a == 0 {

return a

}

return gcd(a, b%a)

}

}func main() {

var A []int

var B []int

for i := 1; i < 71; i++ {

for j := 1; j < 71; j++ {

A = append(A, i)

B = append(B, j)

}

}fmt.Printf("No. of pairs: %v\n", len(A))

ret := Solution(A, B)

fmt.Printf("Result: %v\n", ret)

}

I like this solution, as it came out simple and elegant. The solution is based on Sieve of Eratosthenes. A variation actually, as had to build only based on numbers available.

package solution

// you can also use imports, for example:

//import “fmt”

// import “os”

//import “sort”

// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)

func Solution(A []int) []int {

// write your code in Go 1.4

N := len(A)

mymap := make(map[int]int)

for i := 0; i < N; i++ {

_, ok := mymap[A[i]]

if !ok {

mymap[A[i]] = 1

} else {

mymap[A[i]] += 1

}

}

// construct a custom Eratosthenes sieve

// of factors

// Note we create a custom sieve based on numbers we have

// in the map created above

sieve := make([]int, 2*N+1)

for i := 1; i <= 2*N; i++ {

v, ok := mymap[i]

if ok {

for k := i; k <= 2*N; k += i {

sieve[k] += v

}

}

}

// Now we have every thing computed in the sieve,

// with the help of the sieve.

// We just loop again,

// and return the values from the sive

ret := make([]int, N)

for i := 0; i < N; i++ {

ret[i] = N – sieve[A[i]]

}

return ret

}

And yes, this too got 100% result. Yay!

This problem is under the learning lesson “Prime and Composite numbers” . I am trying to do all the problems marked as Respectable. Here’s my solution for this one:

package solution

// you can also use imports, for example:

//import “fmt”// import “os”

//import “math”// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)func Solution(A []int) int {

// write your code in Go 1.4

N := len(A)

var peaks []int

num_peaks := 0

for i := 1; i A[i-1] && A[i] > A[i+1] {

peaks = append(peaks, i)

num_peaks++

}

}if num_peaks == 0 {

return 0

}for parts := num_peaks; parts >= 1; parts– {

if N%parts != 0 {

continue

}

k := N / parts

//fmt.Printf(“k: %v\n”, k)

peak_ind := 0

cur_peak := peaks[peak_ind]

//fmt.Printf(“cur_peak: %v\n”, cur_peak)

peak_missing := false

for i := 0; i+k-1 = i && cur_peak < i+k && peak_ind < num_peaks {

// peak found in block

peak_found = true

peak_ind++

if peak_ind < num_peaks {

cur_peak = peaks[peak_ind]

//fmt.Printf("cur_peak: %v\n", cur_peak)

}

}//fmt.Printf("block %v, peak_found: %v\n", i, peak_found)

if !peak_found {

peak_missing = true

break

}

}if !peak_missing {

return parts

}

}return 0

}Was glad to get Another 100% result. Albeit, in my 2nd try.

This is a training problem. Advanced one in sorting. Their classification of advanced is Respectable, as against Painless (which I presume means Easy)

On my 3rd try, I got a perfect score. After applying the lesson learnt in prefix summation, an earlier lesson of Codility. Which brought down the time complexity to O(N) from O(N^2)

This is the link to my results.

https://app.codility.com/demo/results/trainingBGF5A3-KW5/

Also my program in Golang below

package solution

// you can also use imports, for example:

//import “fmt”

import “sort”// import “os”

// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)type CirclePoint struct {

X int

CircleId int

IsLeft bool

}// ByLeftX implements sort.Interface for []*CirclePoint based on

// the Left x value field.

type ByLeftX []*CirclePointfunc (a ByLeftX) Len() int { return len(a) }

func (a ByLeftX) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

func (a ByLeftX) Less(i, j int) bool {

// a crucial logic is that if there is a clash of left and right circle

// then we should return the left one first, as touching counts as intersection

ret := false

if a[i].X < a[j].X {

ret = true

} else if a[i].X == a[j].X {

if a[i].IsLeft {

ret = true

}

}

return ret

}func Solution(A []int) int {

// write your code in Go 1.4

var cparr []*CirclePoint

N := len(A)

for i := 0; i < N; i++ {

cpl := CirclePoint{i – A[i], i, true}

cpr := CirclePoint{i + A[i], i, false}

cparr = append(cparr, &cpl)

cparr = append(cparr, &cpr)

}// sort the left and right points on the cricle starting from left to right

sort.Sort(ByLeftX(cparr))

//fmt.Printf("cparr: %+v\n", cparr[0])// Now we do some prefix sum to avoid time complexity run to O(N^2)

// we just keep the sum of left edges of a circle enountered so far

pref_sum := make([]int, 2*N)

for i := 0; i 0 {

pref_sum[i] = pref_sum[i-1]

}

cp := cparr[i]

if cp.IsLeft {

pref_sum[i]++

} else {

pref_sum[i]–

}

}// Find the intersections of all left sides with the already encountered left sides,

// as we move from left to right

// we keep a track of the circles we are in

ret := 0

for i := 0; i 10000000 {

return -1

}

}

}return ret

}