Thuật toán bài chuyến đi

Nobita004 · May 30, 2019, 2:16pm

Cho em hỏi thuật toán tối ưu của bài bên dưới được không ạ! Em nghĩ sẽ chặt nhị phân phần delta để tìm ra đáp án nhưng chưa được. Em mong mọi người giúp đỡ ạ. Em cảm ơn!

Le_Van_Hoang · May 31, 2019, 9:33am

HS1%4=1
HS2%4=3
HS3%4=3
HS4%4=2
HS5%4=3

tổng HS%4= 3 là 3
tổng HS%4= 2 là 1
tổng HS%4= 1 là 1
tổng HS%4= 0 là 1
=> chuyến tàu đầu bắt đầu từ vị trí 3
ví dụ nếu ( HS%4= 3) = ( HS%4= 2) thì cậu xét đến số chuyến tàu cần chạy để đưa hết số học sinh đi .
nếu chuyến tàu chạy mà bằng nhau thì chọn thời điểm bắt đầu là số bé hơn (là 2).
Cậu thử kiểm tra lại . Mình k có thời gian nên cũng chưa test kĩ thuật toán đâu .

hungaya · June 1, 2019, 4:36pm

Bước 1:
Chia tập số tự nhiên N thành các đoạn có độ dài bằng delta. Số cách chia đoạn có độ dài delta là delta. Trường hợp delta = 4 thì có 4 cách chia.

Bước 2:
Đưa danh sách thời điểm đến của các học sinh vào những dãy trên.

Bước 3:
Với mỗi thời điểm, tính khoảng cách từ điểm đó đến biên bên phải của đoạn chứa thời điểm.

Trong dãy (1), điểm 7 thuộc đoạn [4,8], khoảng cách là 8 - 7 = 1

Nếu thời điểm là biên của một đoạn bất kì thì khoảng cách bằng 0.

Trong dãy (2), điểm 9 thuộc 2 đoạn [5,9] và [9,13], nên khoảng cách của 9 đối với 2 đoạn [5,9], [9,13] bằng 0.

Bước 4:
Tỉnh tổng tất cả khoảng cách trong mỗi dãy

Bước 5:
Chọn tổng nhỏ nhất đưa ra ouput, kết quả là 3

Mảng count gồm có delta phần tử tương ứng với tổng các dãy từ (1) đến (delta).
Độ phức tạp O(m.n), với m là số học sinh, n là khoảng cách giữa 2 chuyến đi.

hungaya · June 2, 2019, 2:39pm

Viết bài giải thì thấy cách thứ hai :v
Để ý chỗ cái tính tổng.

Nếu đọc từ trên xuống dưới thì các số tăng dần trong Z/∆Z.

Cột (3) là 1, 2, 3, 0
Cột (6) là 2, 3, 0, 1
…
Cột (11) là 1, 2, 3, 0

Bài tập được chuyển sang dạng khác, cho dãy (a_n) thuộc Z/∆Z và số nguyên dương ∆. Tìm giá trị nhỏ nhất của u_∆, biết (u_∆) là dãy trong Z được cho bởi công thức tổng quát:

u₀ = a₁ + a₂ + … + a_n
u_k = [(a₁ + k) mod ∆] + [(a₂ + k) mod ∆] + … + [(a_n + k) mod ∆], 1 ≤ k ≤ ∆-1

Do tập Z/∆Z là tập hữu hạn gồm các phần tử { 0, 1, 2, … , ∆ - 1 }, nên công thức có thể viết lại như sau, với c_i là số lần số i xuất hiện trong (a_i)

u₀ = 0.c₀ + 1.c₁ + 2.c₂ + … (∆-1)c_∆-1
u_k = [(0 + k) mod ∆].c₀ + [(1 + k) mod ∆].c₁ + [(2 + k) mod ∆].c₂ + … + [(∆ - 1 + k) mod ∆].c_∆-1, 1 ≤ k ≤ ∆-1

Xét 2 trường hợp k và k-1:
u_k =

[(0 + k) mod ∆].c₀ + [(1 + k) mod ∆].c₁ + … + [(∆ - k - 1 + k) mod ∆].c_∆-k-1 + [(∆ - k + k) mod ∆].c_∆-k + [(∆ - k + 1 + k) mod ∆].c_∆-k+1 + … + [(∆ - 1 + k) mod ∆].c_∆-1
k.c₀ + (k+1).c₁ + … + (∆-1).c_∆-k-1 + 0 + c_∆-k+1… + (k-1).c_∆-1

u_k-1 =

[(0 + k - 1) mod ∆].c₀ + [(1 + k - 1) mod ∆].c₁ + … + [(∆ - k - 1 + k - 1) mod ∆].c_∆-k-1 + [(∆ - k + k -1) mod ∆].c_∆-k + [(∆ - k + 1 + k - 1) mod ∆].c_∆-k+1 + … + [(∆ - 1 + k -1) mod ∆].c_∆-1
(k-1).c₀ + k.c₁ + … + (∆-2).c_∆-k-1 + (∆-1).c_∆-k + 0 + … +(k-2).c_∆-1

Lấy u_k - u_k-1:

c₀ + c₁ + … c_∆-k-1 - (∆ -1).c_∆-k + c_∆-k+1 + … + c_∆-1
c₀ + c₁ + … + c_∆-1 - ∆.c_∆-k

Độ phức tạp O(max(n, ∆))

int solution(int arr[], int len, int d) {
    int c[d] = {0};
    for (int i = 0; i < len; i++)
        c[(d - arr[i]%d) % d]++;
    
    int sc = 0, u = 0;
    for (int i = 0; i < d; i++) {
        sc += c[i];
        u += i*c[i];
    }
    
    int uk = u;
    for (int k = 1; k < d; k++) {
        uk += sc - d*c[d-k];
        if (uk < u) u = uk;
    }
    
    return u;
}

Tuan_Ha1 · June 2, 2019, 12:17pm

cho mình hỏi một tí là có n học sinh mà đề bài cho n = 6 mà chỉ cho có thời điểm đến của 5 bạn là sao vậy

rogp10 · June 2, 2019, 12:28pm

lỗi đánh máy thôi

Nobita004 · June 4, 2019, 11:29am

Thực ra bài toán ta quy a[i] = a[i] % delta chỉ cần xét số xuất hiện nhiều nhất hoặc số lớn nhất trong các số trên là đáp án của bài toán. Độ phức tạp của bài toán là O(n). Và chúng ta có thể tăng kích thước của bài toán với n<=10^6.

tntxtnt · June 2, 2019, 6:18pm

xài std::map trong C++ nó sắp xếp sẵn cho rồi truy ngược thì chỉ tốn O(n) mem và O(nlogn) time thôi :V Ko cần lập k từ 1 tới d đâu, lặp đúng n lần trong cái std::map đó là được rồi

hungaya · June 3, 2019, 3:19am

Trường hợp này mình cũng tính rồi, nhưng mình nghĩ nó thuộc heuristic hơn là solution của bài toán.

Counterexample:

6 4
0 0 0 0 1 1

Chuyến đầu từ 0: 3 + 3 = 6
Chuyến đầu từ 1: 1 + 1 + 1 + 1 = 4
Từ 2 trở đi thì lớn hơn hoặc bằng: 2 + 2 + 2 + 2 + 1 + 1 = 10
=> Đáp án là tàu đầu tiên đi từ thời điểm 1, tổng thời gian đợi là 4.

Nếu dựa vào heuristics ở trên: (0 và 1 đều giữ nguyên khi thực hiện % 4)

số xuất hiện nhiều nhất là 0 (4 lần số 0 > 2 lần số 1), chọn 0 là thời điểm bắt đầu. (sai)
số 0 bé nhất, chọn 0 là thời điểm bắt đầu. (sai)

Không hiểu ý bác lắm, bác có thể cho 1 đoạn code mẫu tham khảo được không.

tntxtnt · June 3, 2019, 12:26pm

đại khái thế này: https://wandbox.org/permlink/QyhXVl4zam2DK1zI :V

tính được công thức tổng quát cho w[k] chứ ko cần phải tính từ từ w1 rồi w2 rồi w3 v.v…

/*
Wait time m of each t if launch at time x:
    x\t  9  3  7  6 11  total
    0    3  1  1  2  1    8
    1    0  2  2  3  2    9
    2    1  3  3  0  3   10
    3    2  0  0  1  0    3
We see that if x increases by 1, all wait times will also increase by 1,
  but wrap around so they'll never be >= d (constant time between launches)
If we pre-calculate and group people with same wait time if launch at time 0:
    m0 0 1 2 3
    f  0 3 1 1
and also collect total wait time if launch at time 0:
    w[0] = 1*3 + 2*1 + 3*1 = 8
We can calculate total wait time if launch at time 1, which is total wait time
  if launch at time 0, plus n (n wait times increase by 1), and minus d
  times number of people at m0 = 3
    w[1] = w[0] + n - d*f[3]
The number 3 in f[3] can be deduce to be d - k: 3 = 4 - 1. Indeed if we
  jumps from k=1 to k=2, f[d - 2] is the one to be wrapped around (t=6 in
  the above example).
So we have the formula for w[2]:
    w[2] = w[1] + n - d*f[d - 2]
which we can substitue w[1] to get:
    w[2] = (w[0] + n - d*f[d - 1]) + n - d*f[d - 2]
         = w[0] + 2n - d*(f[d - 1] + f[d - 2])
Finally we have the general formula:
    w[k] = w[0] + k*n - d*(f[d-1] + f[d-2] + ... + f[d-k])
*/

#include <cstdint>
#include <iostream>
#include <map>

int main()
{
    int n, d;
    std::cin >> n >> d;

    //
    // Group ppl w/ same wait time if launch at time 0
    // Wait time (if launch at time 0) formula:
    //     m0 = d - (t % d), if m0 == t then m0 = 0
    //  or m0 = (d - (t % d)) % d
    //
    std::map<int, int, std::greater<int>> f;
    for (int t; std::cin >> t;)
        f[(d - t % d) % d]++;

    //
    // Calculate initial total wait time w[0]
    //
    int64_t w0 = 0;
    for (auto [m, fm] : f)
        w0 += (int64_t)m * fm;

    //
    // Find launch time x that minimize total wait time w
    // Total wait time w[k] if launch at time k formula:
    //     w[k] = w[0] + k*n - d*(f[d-1] + f[d-2] + ... + f[d-k])
    //   where f[m] is the # of ppl w/ wait time m if launch at time 0
    //
    int64_t w = w0;
    int64_t x = 0;
    int64_t sk = 0; // the sum (f[d-1] + f[d-2] + ... + f[d-k])
    for (auto [m, fm] : f)
    {
        sk += fm;
        int64_t k = d - m; // f[m] = f[d-k] so m = d - k or k = d - m
        int64_t wi = w0 + k * n - d * sk;
        if (wi < w)
            w = wi, x = k;
    }
    std::cout << x << "\n";
}

Nobita004 · June 4, 2019, 11:32am

Xin lỗi em viết lộn là số lớn nhất ạ ! ( Đã fix)
Em nộp và full rồi ạ!