Tasks Details
hard
1.
ABSwaps
Calculate the minimum required number of swaps of neighbouring letters in a string built from the letters 'a' and 'b', after which the string would contain both "aaa" and "bbb" as substrings.
Task Score
75%
Correctness
100%
Performance
60%
You are given a string S consisting of letters 'a' and 'b'. The task is to rearrange letters in S so that it contains three consecutive letters 'a' and three consecutive letters 'b'. What is the minimum necessary number of swaps of neighbouring letters to achieve this?
Write a function:
func Solution(S string) int
that, given a string S of length N, returns the number of swaps after which S would contain "aaa" and "bbb" as substrings. If it's not possible to rearrange the letters in such a way, the function should return −1.
Examples:
1. Given S = "ababab", the function should return 3. The sequence of swaps could be as follows: ababab → abaabb → aababb → aaabbb.
2. Given S = "abbbbaa", the function should return 4. The sequence of four swaps is: abbbbaa → babbbaa → bbabbaa → bbbabaa → bbbbaaa.
3. Given S = "bbbababaaab", the function should return 0. S already contains both "aaa" and "bbb" as substrings.
4. Given S = "abbabb", the function should return −1. It is not possible to obtain the required result from S as there are only two letters 'a'.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- string S is made only of the characters 'a' and/or 'b'.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Go
Time spent on task 1 minutes
Notes
not defined yet
Code: 23:06:40 UTC,
java,
autosave
Code: 23:06:47 UTC,
go,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334
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(S string) int {
h := []int{}
var vs rune
for i, v := range S {
if i == 0 {
vs = v
if v == 'a' {
h = append(h, 1)
} else {
h = append(h, -1)
}
continue
}
if v == 'a' {
if vs == v {
h[len(h)-1]++
} else {
h = append(h, 1)
}
vs = 'a'
}
if v == 'b' {
if vs == v {
h[len(h)-1]--
} else {
h = append(h, -1)
}
vs = 'b'
}
}
a, af, bf := bestMatch(h, true)
if a == nil {
return -1
}
if af || bf {
//aa, _, _ := bestMatch(h, false)
if af {
b := sideCheck(h, true)
return b
}
if bf {
b := sideCheck(h, false)
return b
}
return 0
}
bss := mv(a)
return bss
}
func bestMatch(h []int, border bool) ([]int, bool, bool) {
intervall := 0
intervalh := 0
yield := 1000000000
index := 0
a3 := 0
b3 := 0
fullNum := 0
locka, lockb := false, false
locki := false
valid := false
lockIndex := false
i := 0
for i < len(h) {
if lockIndex {
index++
lockIndex = false
}
if !locki {
if h[i] > 2 {
locka = true
}
if h[i] < -2 {
lockb = true
}
if h[i] > 0 {
a3 += h[i]
} else {
b3 += h[i]
}
}
if a3 > 2 && b3 < -2 {
locki = true
valid = true
a, b := checks(h[index : i+1])
if (yield > a+b) || (yield == a+b && a3-b3 > fullNum) {
yield = a + b
intervall = index
intervalh = i
fullNum = a3 - b3
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
lockIndex = true
} else {
locki = false
i++
}
}
for {
if a3 > 2 && b3 < -2 {
if lockIndex {
index++
lockIndex = false
}
valid = true
a, b := checks(h[index:len(h)])
if yield > a+b {
yield = a + b
intervall = index
intervalh = len(h) - 1
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
index++
} else {
break
}
}
if border {
if intervalh < len(h)-1 {
intervalh++
}
if intervall > 0 {
intervall--
}
}
if !valid {
return nil, false, false
}
return h[intervall : intervalh+1], locka, lockb
}
func checks(h []int) (int, int) {
if len(h) < 1 {
return -1, -1
}
var blocka, blockb bool
var dista, distb int
if h[0] < -2 || h[len(h)-1] < -2 {
blockb = true
}
if h[0] > 2 || h[len(h)-1] > 2 {
blocka = true
}
for i := 1; i < len(h)-1; i++ {
if h[i] < 0 {
if h[i] < -2 {
blockb = true
}
dista -= h[i]
} else {
if h[i] > 2 {
blocka = true
}
distb += h[i]
}
}
if blocka {
dista = 0
}
if blockb {
distb = 0
}
return dista, distb
}
func mv(h []int) int {
a, b := checks(h)
if a+b == 0 {
return 0
}
indexRef := 0
counter := 1000000
index := 0
dst := make([]int, len(h))
for i := 0; i < len(h); i++ {
copy(dst, h)
in, d := alter(dst, i)
inn, _, _ := bestMatch(in, false)
a, b := checks(inn)
c := a + b + d
if c < counter {
indexRef = d
counter = c
index = i
}
}
copy(dst, h)
in, _ := alter(dst, index)
inn, _, _ := bestMatch(in, false)
return mv(inn) + indexRef
}
func alter(h []int, index int) ([]int, int) {
num := 1
shift := 0
if h[index] > 0 {
num = -1
}
switch {
case index-1 < 0:
b := h[index]
h[index] = h[index+1]
h[index+1] = b
shift = h[index] * h[index+1]
case index+1 >= len(h):
b := h[index]
h[index] = h[index-1]
h[index-1] = b
shift = h[index] * h[index-1]
default:
h[index-1] += num
h[index+1] -= num
shift = h[index]
}
base := 0
ap := []int{}
for i, v := range h {
if i == 0 {
base = v
continue
}
if v < 0 {
if base < 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
if v > 0 {
if base > 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
}
ap = append(ap, base)
if shift < 0 {
shift = -1 * shift
}
return ap, shift
}
func sideCheck(h []int, sign bool) int {
res := 100000
cu := 0
neg := 0
begin := 0
if len(h) < 1 {
return -1
}
if sign {
if h[0] > 0 {
begin++
}
} else {
if h[0] < 0 {
begin++
}
}
for i := begin; i < len(h); i += 2 {
a := i
cu = 0
neg = 0
for ii := a; ii < len(h); ii += 2 {
cu += h[ii]
if cu > 2 || cu < -2 {
if neg < 0 {
neg = neg * -1
}
if res > neg {
res = neg
}
neg = 0
cu = 0
continue
}
if ii+1 < len(h) {
neg += h[ii+1]
}
}
}
if res < 0 {
res = res * -1
}
return res
}
Code: 23:06:55 UTC,
go,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334
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(S string) int {
h := []int{}
var vs rune
for i, v := range S {
if i == 0 {
vs = v
if v == 'a' {
h = append(h, 1)
} else {
h = append(h, -1)
}
continue
}
if v == 'a' {
if vs == v {
h[len(h)-1]++
} else {
h = append(h, 1)
}
vs = 'a'
}
if v == 'b' {
if vs == v {
h[len(h)-1]--
} else {
h = append(h, -1)
}
vs = 'b'
}
}
a, af, bf := bestMatch(h, true)
if a == nil {
return -1
}
if af || bf {
//aa, _, _ := bestMatch(h, false)
if af {
b := sideCheck(h, true)
return b
}
if bf {
b := sideCheck(h, false)
return b
}
return 0
}
bss := mv(a)
return bss
}
func bestMatch(h []int, border bool) ([]int, bool, bool) {
intervall := 0
intervalh := 0
yield := 1000000000
index := 0
a3 := 0
b3 := 0
fullNum := 0
locka, lockb := false, false
locki := false
valid := false
lockIndex := false
i := 0
for i < len(h) {
if lockIndex {
index++
lockIndex = false
}
if !locki {
if h[i] > 2 {
locka = true
}
if h[i] < -2 {
lockb = true
}
if h[i] > 0 {
a3 += h[i]
} else {
b3 += h[i]
}
}
if a3 > 2 && b3 < -2 {
locki = true
valid = true
a, b := checks(h[index : i+1])
if (yield > a+b) || (yield == a+b && a3-b3 > fullNum) {
yield = a + b
intervall = index
intervalh = i
fullNum = a3 - b3
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
lockIndex = true
} else {
locki = false
i++
}
}
for {
if a3 > 2 && b3 < -2 {
if lockIndex {
index++
lockIndex = false
}
valid = true
a, b := checks(h[index:len(h)])
if yield > a+b {
yield = a + b
intervall = index
intervalh = len(h) - 1
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
index++
} else {
break
}
}
if border {
if intervalh < len(h)-1 {
intervalh++
}
if intervall > 0 {
intervall--
}
}
if !valid {
return nil, false, false
}
return h[intervall : intervalh+1], locka, lockb
}
func checks(h []int) (int, int) {
if len(h) < 1 {
return -1, -1
}
var blocka, blockb bool
var dista, distb int
if h[0] < -2 || h[len(h)-1] < -2 {
blockb = true
}
if h[0] > 2 || h[len(h)-1] > 2 {
blocka = true
}
for i := 1; i < len(h)-1; i++ {
if h[i] < 0 {
if h[i] < -2 {
blockb = true
}
dista -= h[i]
} else {
if h[i] > 2 {
blocka = true
}
distb += h[i]
}
}
if blocka {
dista = 0
}
if blockb {
distb = 0
}
return dista, distb
}
func mv(h []int) int {
a, b := checks(h)
if a+b == 0 {
return 0
}
indexRef := 0
counter := 1000000
index := 0
dst := make([]int, len(h))
for i := 0; i < len(h); i++ {
copy(dst, h)
in, d := alter(dst, i)
inn, _, _ := bestMatch(in, false)
a, b := checks(inn)
c := a + b + d
if c < counter {
indexRef = d
counter = c
index = i
}
}
copy(dst, h)
in, _ := alter(dst, index)
inn, _, _ := bestMatch(in, false)
return mv(inn) + indexRef
}
func alter(h []int, index int) ([]int, int) {
num := 1
shift := 0
if h[index] > 0 {
num = -1
}
switch {
case index-1 < 0:
b := h[index]
h[index] = h[index+1]
h[index+1] = b
shift = h[index] * h[index+1]
case index+1 >= len(h):
b := h[index]
h[index] = h[index-1]
h[index-1] = b
shift = h[index] * h[index-1]
default:
h[index-1] += num
h[index+1] -= num
shift = h[index]
}
base := 0
ap := []int{}
for i, v := range h {
if i == 0 {
base = v
continue
}
if v < 0 {
if base < 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
if v > 0 {
if base > 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
}
ap = append(ap, base)
if shift < 0 {
shift = -1 * shift
}
return ap, shift
}
func sideCheck(h []int, sign bool) int {
res := 100000
cu := 0
neg := 0
begin := 0
if len(h) < 1 {
return -1
}
if sign {
if h[0] > 0 {
begin++
}
} else {
if h[0] < 0 {
begin++
}
}
for i := begin; i < len(h); i += 2 {
a := i
cu = 0
neg = 0
for ii := a; ii < len(h); ii += 2 {
cu += h[ii]
if cu > 2 || cu < -2 {
if neg < 0 {
neg = neg * -1
}
if res > neg {
res = neg
}
neg = 0
cu = 0
continue
}
if ii+1 < len(h) {
neg += h[ii+1]
}
}
}
if res < 0 {
res = res * -1
}
return res
}
Analysis
Code: 23:06:59 UTC,
go,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334
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(S string) int {
h := []int{}
var vs rune
for i, v := range S {
if i == 0 {
vs = v
if v == 'a' {
h = append(h, 1)
} else {
h = append(h, -1)
}
continue
}
if v == 'a' {
if vs == v {
h[len(h)-1]++
} else {
h = append(h, 1)
}
vs = 'a'
}
if v == 'b' {
if vs == v {
h[len(h)-1]--
} else {
h = append(h, -1)
}
vs = 'b'
}
}
a, af, bf := bestMatch(h, true)
if a == nil {
return -1
}
if af || bf {
//aa, _, _ := bestMatch(h, false)
if af {
b := sideCheck(h, true)
return b
}
if bf {
b := sideCheck(h, false)
return b
}
return 0
}
bss := mv(a)
return bss
}
func bestMatch(h []int, border bool) ([]int, bool, bool) {
intervall := 0
intervalh := 0
yield := 1000000000
index := 0
a3 := 0
b3 := 0
fullNum := 0
locka, lockb := false, false
locki := false
valid := false
lockIndex := false
i := 0
for i < len(h) {
if lockIndex {
index++
lockIndex = false
}
if !locki {
if h[i] > 2 {
locka = true
}
if h[i] < -2 {
lockb = true
}
if h[i] > 0 {
a3 += h[i]
} else {
b3 += h[i]
}
}
if a3 > 2 && b3 < -2 {
locki = true
valid = true
a, b := checks(h[index : i+1])
if (yield > a+b) || (yield == a+b && a3-b3 > fullNum) {
yield = a + b
intervall = index
intervalh = i
fullNum = a3 - b3
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
lockIndex = true
} else {
locki = false
i++
}
}
for {
if a3 > 2 && b3 < -2 {
if lockIndex {
index++
lockIndex = false
}
valid = true
a, b := checks(h[index:len(h)])
if yield > a+b {
yield = a + b
intervall = index
intervalh = len(h) - 1
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
index++
} else {
break
}
}
if border {
if intervalh < len(h)-1 {
intervalh++
}
if intervall > 0 {
intervall--
}
}
if !valid {
return nil, false, false
}
return h[intervall : intervalh+1], locka, lockb
}
func checks(h []int) (int, int) {
if len(h) < 1 {
return -1, -1
}
var blocka, blockb bool
var dista, distb int
if h[0] < -2 || h[len(h)-1] < -2 {
blockb = true
}
if h[0] > 2 || h[len(h)-1] > 2 {
blocka = true
}
for i := 1; i < len(h)-1; i++ {
if h[i] < 0 {
if h[i] < -2 {
blockb = true
}
dista -= h[i]
} else {
if h[i] > 2 {
blocka = true
}
distb += h[i]
}
}
if blocka {
dista = 0
}
if blockb {
distb = 0
}
return dista, distb
}
func mv(h []int) int {
a, b := checks(h)
if a+b == 0 {
return 0
}
indexRef := 0
counter := 1000000
index := 0
dst := make([]int, len(h))
for i := 0; i < len(h); i++ {
copy(dst, h)
in, d := alter(dst, i)
inn, _, _ := bestMatch(in, false)
a, b := checks(inn)
c := a + b + d
if c < counter {
indexRef = d
counter = c
index = i
}
}
copy(dst, h)
in, _ := alter(dst, index)
inn, _, _ := bestMatch(in, false)
return mv(inn) + indexRef
}
func alter(h []int, index int) ([]int, int) {
num := 1
shift := 0
if h[index] > 0 {
num = -1
}
switch {
case index-1 < 0:
b := h[index]
h[index] = h[index+1]
h[index+1] = b
shift = h[index] * h[index+1]
case index+1 >= len(h):
b := h[index]
h[index] = h[index-1]
h[index-1] = b
shift = h[index] * h[index-1]
default:
h[index-1] += num
h[index+1] -= num
shift = h[index]
}
base := 0
ap := []int{}
for i, v := range h {
if i == 0 {
base = v
continue
}
if v < 0 {
if base < 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
if v > 0 {
if base > 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
}
ap = append(ap, base)
if shift < 0 {
shift = -1 * shift
}
return ap, shift
}
func sideCheck(h []int, sign bool) int {
res := 100000
cu := 0
neg := 0
begin := 0
if len(h) < 1 {
return -1
}
if sign {
if h[0] > 0 {
begin++
}
} else {
if h[0] < 0 {
begin++
}
}
for i := begin; i < len(h); i += 2 {
a := i
cu = 0
neg = 0
for ii := a; ii < len(h); ii += 2 {
cu += h[ii]
if cu > 2 || cu < -2 {
if neg < 0 {
neg = neg * -1
}
if res > neg {
res = neg
}
neg = 0
cu = 0
continue
}
if ii+1 < len(h) {
neg += h[ii+1]
}
}
}
if res < 0 {
res = res * -1
}
return res
}
Analysis
Code: 23:07:02 UTC,
go,
final,
score:
75
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334
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(S string) int {
h := []int{}
var vs rune
for i, v := range S {
if i == 0 {
vs = v
if v == 'a' {
h = append(h, 1)
} else {
h = append(h, -1)
}
continue
}
if v == 'a' {
if vs == v {
h[len(h)-1]++
} else {
h = append(h, 1)
}
vs = 'a'
}
if v == 'b' {
if vs == v {
h[len(h)-1]--
} else {
h = append(h, -1)
}
vs = 'b'
}
}
a, af, bf := bestMatch(h, true)
if a == nil {
return -1
}
if af || bf {
//aa, _, _ := bestMatch(h, false)
if af {
b := sideCheck(h, true)
return b
}
if bf {
b := sideCheck(h, false)
return b
}
return 0
}
bss := mv(a)
return bss
}
func bestMatch(h []int, border bool) ([]int, bool, bool) {
intervall := 0
intervalh := 0
yield := 1000000000
index := 0
a3 := 0
b3 := 0
fullNum := 0
locka, lockb := false, false
locki := false
valid := false
lockIndex := false
i := 0
for i < len(h) {
if lockIndex {
index++
lockIndex = false
}
if !locki {
if h[i] > 2 {
locka = true
}
if h[i] < -2 {
lockb = true
}
if h[i] > 0 {
a3 += h[i]
} else {
b3 += h[i]
}
}
if a3 > 2 && b3 < -2 {
locki = true
valid = true
a, b := checks(h[index : i+1])
if (yield > a+b) || (yield == a+b && a3-b3 > fullNum) {
yield = a + b
intervall = index
intervalh = i
fullNum = a3 - b3
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
lockIndex = true
} else {
locki = false
i++
}
}
for {
if a3 > 2 && b3 < -2 {
if lockIndex {
index++
lockIndex = false
}
valid = true
a, b := checks(h[index:len(h)])
if yield > a+b {
yield = a + b
intervall = index
intervalh = len(h) - 1
}
if h[index] > 0 {
a3 -= h[index]
} else {
b3 -= h[index]
}
index++
} else {
break
}
}
if border {
if intervalh < len(h)-1 {
intervalh++
}
if intervall > 0 {
intervall--
}
}
if !valid {
return nil, false, false
}
return h[intervall : intervalh+1], locka, lockb
}
func checks(h []int) (int, int) {
if len(h) < 1 {
return -1, -1
}
var blocka, blockb bool
var dista, distb int
if h[0] < -2 || h[len(h)-1] < -2 {
blockb = true
}
if h[0] > 2 || h[len(h)-1] > 2 {
blocka = true
}
for i := 1; i < len(h)-1; i++ {
if h[i] < 0 {
if h[i] < -2 {
blockb = true
}
dista -= h[i]
} else {
if h[i] > 2 {
blocka = true
}
distb += h[i]
}
}
if blocka {
dista = 0
}
if blockb {
distb = 0
}
return dista, distb
}
func mv(h []int) int {
a, b := checks(h)
if a+b == 0 {
return 0
}
indexRef := 0
counter := 1000000
index := 0
dst := make([]int, len(h))
for i := 0; i < len(h); i++ {
copy(dst, h)
in, d := alter(dst, i)
inn, _, _ := bestMatch(in, false)
a, b := checks(inn)
c := a + b + d
if c < counter {
indexRef = d
counter = c
index = i
}
}
copy(dst, h)
in, _ := alter(dst, index)
inn, _, _ := bestMatch(in, false)
return mv(inn) + indexRef
}
func alter(h []int, index int) ([]int, int) {
num := 1
shift := 0
if h[index] > 0 {
num = -1
}
switch {
case index-1 < 0:
b := h[index]
h[index] = h[index+1]
h[index+1] = b
shift = h[index] * h[index+1]
case index+1 >= len(h):
b := h[index]
h[index] = h[index-1]
h[index-1] = b
shift = h[index] * h[index-1]
default:
h[index-1] += num
h[index+1] -= num
shift = h[index]
}
base := 0
ap := []int{}
for i, v := range h {
if i == 0 {
base = v
continue
}
if v < 0 {
if base < 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
if v > 0 {
if base > 0 {
base += v
} else {
ap = append(ap, base)
base = v
}
}
}
ap = append(ap, base)
if shift < 0 {
shift = -1 * shift
}
return ap, shift
}
func sideCheck(h []int, sign bool) int {
res := 100000
cu := 0
neg := 0
begin := 0
if len(h) < 1 {
return -1
}
if sign {
if h[0] > 0 {
begin++
}
} else {
if h[0] < 0 {
begin++
}
}
for i := begin; i < len(h); i += 2 {
a := i
cu = 0
neg = 0
for ii := a; ii < len(h); ii += 2 {
cu += h[ii]
if cu > 2 || cu < -2 {
if neg < 0 {
neg = neg * -1
}
if res > neg {
res = neg
}
neg = 0
cu = 0
continue
}
if ii+1 < len(h) {
neg += h[ii+1]
}
}
}
if res < 0 {
res = res * -1
}
return res
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N) or O(N**4)
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
7.
0.001 s
OK
8.
0.001 s
OK
9.
0.001 s
OK
10.
0.001 s
OK
11.
0.001 s
OK
12.
0.001 s
OK
13.
0.001 s
OK
14.
0.001 s
OK
15.
0.001 s
OK
16.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
7.
0.001 s
OK
8.
0.001 s
OK
9.
0.001 s
OK
10.
0.001 s
OK
11.
0.001 s
OK
12.
0.001 s
OK
13.
0.001 s
OK
14.
0.001 s
OK
15.
0.001 s
OK
16.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
7.
0.001 s
OK
8.
0.001 s
OK
9.
0.001 s
OK
10.
0.001 s
OK
11.
0.001 s
OK
12.
0.001 s
OK
13.
0.001 s
OK
14.
0.001 s
OK
15.
0.001 s
OK
16.
0.001 s
OK
17.
0.001 s
OK
18.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
expand all
Performance tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
7.
0.001 s
OK
8.
0.001 s
OK
9.
0.001 s
OK
10.
0.001 s
OK
11.
0.001 s
OK
12.
0.001 s
OK
large_big_answer
Answer is bigger than 4. Score x 2.
Answer is bigger than 4. Score x 2.
✘
TIMEOUT ERROR
running time: 0.140 sec., time limit: 0.100 sec.
running time: 0.140 sec., time limit: 0.100 sec.
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.140 s
TIMEOUT ERROR,
running time: 0.140 sec., time limit: 0.100 sec.
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.001 s
OK
5.
0.008 s
OK
6.
0.001 s
OK
large_perf
Big performance package. Score x 2.
Big performance package. Score x 2.
✘
TIMEOUT ERROR
running time: 2.684 sec., time limit: 0.100 sec.
running time: 2.684 sec., time limit: 0.100 sec.
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
7.
0.001 s
OK
8.
2.684 s
TIMEOUT ERROR,
running time: 2.684 sec., time limit: 0.100 sec.
9.
2.716 s
TIMEOUT ERROR,
running time: 2.716 sec., time limit: 0.100 sec.
10.
2.644 s
TIMEOUT ERROR,
running time: 2.644 sec., time limit: 0.100 sec.
11.
2.676 s
TIMEOUT ERROR,
running time: 2.676 sec., time limit: 0.100 sec.