---
# System prepended metadata

title: Aiken Tournament Solution

---

# Aiken Tournament Solution
Nguồn: Thầy Toanh (anh.nt1@teko.vn)
### Problem: AbsoluteValuesSumMinimization
Không mất nhiều thời gian để ta nhận ra rằng đáp án là phần tử ở giữa do mảng đầu vào đã được sắp xếp. Dưới đây là một impl:
```
use aiken/list
fn absoluteValuesSumMinimization(items: List<Int>) -> Int {
  let n = list.length(items)
  expect Some(v) = list.at(items, ( n - 1 ) / 2)
  v
}
```

Tuy nhiên, team muốn đem đến một thử thách và treo thưởng cho những người cống hiến nhất, thí sinh phải nghiên cứu thêm để tối ưu đoạn code trên.
Ý tưởng: Nếu bạn đã tìm hiểu về Aiken thì cost model sẽ không giống với các ngôn ngữ off-chain thông thường.  Ví dụ đối với list.length trong stdlib thì chi phí là linear thay vì constant cho cả mem và cpu, đây là impl (tương tự với list.at):
```
pub fn length(self: List<a>) -> Int {
  when self is {
    [] -> 0
    [_, ..xs] -> 1 + length(xs)
  }
}
```
Vì vậy, sẽ mất (n + n/2) lần đệ quy cho impl trên, mỗi lần đệ quy sẽ kèm với chi phí clone args. Để có thể vượt qua được test cuối cùng, thí sinh cần phải giảm số lần đệ quy tối đa có thể. Sau đây là lời giải tham khảo của btc: Ta coi mảng đầu vào là 1 singly linked list, đáp án sẽ là node ở giữa. Sử dụng 2 pointer với step lần lượt là 1 và 2, khi fast pointer đạt cuối list, ta trả về pointer slow:
```
use aiken/list

pub fn absoluteValuesSumMinimization(items: List<Int>) -> Int {
  expect [_, ..tail] = items
  expect Some(v) = do_search(items, tail)
  v
}

fn do_search(slow, fast) {
  when fast is {
    [] -> list.head(slow)
    [_] -> list.head(slow)
    [_, _, ..fast] -> {
      expect [_, ..slow] = slow
      do_search(slow, fast)
    }
  }
}
```
