A min abs slice is a slice whose absolute sum is minimal

#1

Trước hết cảm ơn các anh chị / bạn đã tham gia giải đáp các vấn đê cho em thời gian qua. Em ko có đủ năng lực để giải đáp vấn đề của người khác toàn đi hỏi, thật ngại, xin thư lỗi ạ.

Đề này bảo mình tìm tổng nhỏ nhất đúng ko ạ? em thắc mắc vì sao có (1, 3) mà ko có cặp (0,4) , (1,2) …vậy ạ. Em đọc tiếng anh còn kém lắm mong mọi người giải đáp giúp
A non-empty array A of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + … + A[Q].

A min abs slice is a slice whose absolute sum is minimal.

For example, array A such that:

A[0] = 2
A[1] = -4
A[2] = 6
A[3] = -3
A[4] = 9
contains the following slices, among others:

(0, 1), whose absolute sum = |2 + (−4)| = 2
(0, 2), whose absolute sum = |2 + (−4) + 6| = 4
(0, 3), whose absolute sum = |2 + (−4) + 6 + (−3)| = 1
(1, 3), whose absolute sum = |(−4) + 6 + (−3)| = 1
(1, 4), whose absolute sum = |(−4) + 6 + (−3) + 9| = 8
(4, 4), whose absolute sum = |9| = 9
Both slices (0, 3) and (1, 3) are min abs slices and their absolute sum equals 1.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the absolute sum of min abs slice.

For example, given:

A[0] = 2
A[1] = -4
A[2] = 6
A[3] = -3
A[4] = 9
the function should return 1, as explained above.

Assume that:

N is an integer within the range [1…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*log(N));
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

#2

Họ chỉ đưa ra một số slice thôi, chứ không đưa ra tất cả ở VD :slight_smile: Dịch đơn giản đề ra thì là tìm Giá trị tuyệt đối là bé nhất của tổng các số liên tiếp thôi :slight_smile:

3 Likes
#3

“Giá trị tuyệt đối là bé nhất” chứ :slight_smile:

2 Likes
#4

Thảm nào cứ thắc mắc abs là gì, giờ mới nhớ ra là trị tuyệt đối :slight_smile:

3 Likes
#5

làm 2 vòng lặp thì độ phức tạp bao nhiêu vậy ạ, trong trường mình ko dạy kĩ cái này nên giờ cũng ko biết tính

#6

Chạy hết mảng mà 2 vòng lồng nhau thì nhiều khi là O(N^2).

2 Likes
#7

vậy là ko đáp ứng được performance bài này rồi :joy:

3 Likes
#8

Đây là cách giải của mình:

  1. Xây dựng mảng cộng dồn s[i] = sum(a[0:i])
  2. sum(a[p]+a[p+1]+…+a[q]) = s[q+1] - s[p]
  3. Từ bước 2 ta thấy là tất cả các đoạn đều có thể tính từ mảng s, mặt khác nếu abs(sum(a[p]+a[p+1]+…+a[q]) ) nhỏ nhất tức là abs(s[q+1] - s[p]) nhỏ nhất hay s[q+1] - s[p] gần 0 nhất
  4. Ta chỉ cần sort mảng s để tìm s[q+1] - s[p] gần nhau nhất
  5. kết quả = min(sorted_s[i+1] - sorted_s[i]) 

a = [2,-4,6,-3,9]
s = [0]

for w in a:
    s.append(s[-1]+w)

s.sort()
ans = float("inf")
for i in range(len(s)-1):
    ans = min(s[i+1]-s[i],ans)
print(ans)
3 Likes
#9

anh gió giải thích em chỗ này với ạ, các phần tử cộng dồn âm dương đâu biết chính xác sao anh xác định chỗ đó gần 0 nhất v. em chưa biết python, trường em dạy mỗi java thôi

#10

Chuyển sang Java nè, nhưng có vẻ không đúng convention lắm.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] numbers = { 2, -4, 6, -3, 9 };

        int[] sum = new int[numbers.length];
        sum[0] = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            sum[i] = sum[i - 1] + numbers[i];
        }

        Arrays.sort(sum);

        int minDiff = Math.abs(sum[0]);
        for (int i = 1; i < sum.length; i++) {
            minDiff = Math.min(minDiff, sum[i] - sum[i - 1]);
            minDiff = Math.min(minDiff, Math.abs(sum[i]));
        }

        System.out.println("Min: " + minDiff);
    }
}
2 Likes
#11

Để giải thích cho bước 3: abs(s[q+1] - s[p]) nhỏ nhất
biểu diễn trên trục tọa độ Ox, abs(a-b) = khoảng cách trên trục tọa độ của 2 điểm a,b
Cố định điểm a, khoảng cách từ a đến các điểm khác nhỏ nhất khi điểm đó gần a nhất

-----------------a----b-----x—y---z------------>

Như vậy đáp số bài toán là khoảng cách nhỏ nhất của 2 điểm liền kề

Giải thích bước 4: sắp xếp lại thứ tự các điểm của mảng s để được các cặp điểm gần nhau

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?