Hướng dẫn NTUCoder Round #12

admin - 22/08/2015

Bài A: ANTRA - Ăn trắng

      Quy các lá bài 3, 4, ..., K, A, 2 về các số nguyên 1, 2, ..., 11, 12, 13. Sau đó đếm số lần xuất hiện của từng lá bài. Từ đó suy ra kết quả. Chú ý trường hợp đặc biệt là 4 lá bài giống nhau có thể xem là 2 đôi, nếu có thêm 4 đôi khác thì thành 6 đôi.

Bài B: CHOSO - Chọn số

    - Sắp xếp 3 dãy số trên, sau đó sử dụng 3 con trỏ cho ba dãy số để lần lượt đếm số lượng phần tử bằng nhau ở từng chuỗi, nhân lại với nhau và cộng vào kết quả cuối cùng. Độ phức tạp O(nlogn).

Chú ý: với C++, dùng kiểu dữ liệu map giải cho lẹ.                        

Bài C: CHAIN - Nối chuỗi xích

     Nếu ta mở hết các mắc xích của một chuỗi xích thì chuỗi xích đó biến mất chỉ còn lại n-1 chuỗi để nối. Vậy giải theo phương pháp tham, chuỗi ít mắc xích nhất sẽ dễ biến mất nhất. Sắp xếp chuỗi xích theo số lượng mắt xích tăng dần. Sau đó lần lượt mở hết số mắc xích từng chuỗi một cho đến khi có kết quả. Độ phức tạp O(nlogn)

Bài D: BANK - Xếp hàng gửi tiền

     Sử dụng quy hoạch động. Lần lượt xét từ giây thứ 0 đến giây cuối cùng. Mỗi lần sẽ chọn ra đáp án của giây đó (là danh sách các khách hàng có thể gửi được sắp theo thứ tự giảm dần của số tiền). Giả sử ở giây t đã chọn ra được t + 1 khách hàng c1, c2, c3,...., ct+1, gọi b1, b2, ..., bk là số khách hàng chỉ chờ được t+1 giây (sắp giảm dần theo thứ tự số tiền). Ta trộn hay dãy B và C lại để có 1 dãy giảm dần và lấy t+2 khách hàng đầu tiên. Đây là kết quả ở giây t+1. Độ phức tạp max(O(t2), O(nlogn)

Bài E: STRAGAIN - Lại là chuỗi

      - Vì chỉ có tối đa 20 kí tự và 2 loại kí tự 'A', 'B' nên ta có thể quy thành 0, 1 (giả sử 'A' = 0 và 'B' = 1).  Như vậy sẽ có tối đa 220 trạng thái tương ứng với 20 giá trị từ 0 đến 220-1.  Nếu ta quy định các đỉnh có giá trị tương ứng từ 0 đến 2N-1 (N là số kí tự của chuỗi ban đầu), thì nhiệm vụ của ta lúc này là từ đỉnh trạng thái ban đầu, đi đến đỉnh 0 hoặc 2N-1 (0 tương ứng với dãy toàn 'A' và 2N-1 tương ứng với dãy toàn 'B').

     - 2 đỉnh được xem là có cạnh nối nếu thỏa mãn ràng buộc đề bài.

Độ phức tạp: O(2*N*(2N))

Bài F: CARDS - Thẻ bài

Giải bằng cấu trúc heap:

  - Với mỗi lá bài "A" thì thực hiện thao tác push W vào heap.

  - Với mỗi lá bài "P" thì lưu giá trị tmp = heap[1] rồi thực hiện thao tác xóa heap[1] và đếm số lượng cho đến khi tmp ≠ heap[1] hoặc nheap=0 .

Dòng cuối cùng in ra heap[1] và xóa heap[1] cho đến khi nheap=0.

Độ phức tạp: O(2*N log N)

Bài G: MEETING - Lễ Meeting

Cách làm khá đơn giản, duyệt hết theo từng bước. Có thể các bạn sẽ cảm thấy không đúng, không phù hợp, không đủ nhanh để giải quyết vì trường hợp xấu nhất là duyệt đủ N*L bước cho mỗi test case và T*N*L cho toàn bộ test, tức độ phức tạp O(T*N*L) = O(10^9). Tuy nhiên có một số nhận xét và tính chất có thể làm căn cứ cho ta thực hiện điều đó:

 - Để người thứ i có thể ngồi xuống thì 2 người i-1 và i+1 sẽ phải đang ngồi (hoặc 1 người nếu i=1 hoặc i=N), như vậy để người này ngồi xuống thì phải có ít nhất 1 người khác đứng lên như vậy gần như sẽ không lợi (có 1 trường hợp, nó sẽ được nói ở phía dưới).

 - Nếu có nhiều hơn 1 người đang đứng liên tiếp nhau, thì chắn chắn họ sẽ đứng suốt buổi lễ và số người đứng lên sẽ được mở rộng dần ra 2 phía (vì những người đang kề với đoạn này trong giờ tiếp theo sẽ đứng lên), như vậy trong trường hợp này sẽ chỉ sau tối đa N giờ thì toàn bộ số người sẽ đứng và từ lúc này sẽ không thay đổi trạng thái cho đến hết buổi lễ.

 - Trong trường hợp trạng thái của N người hiện tại là luân phiên đứng ngồi và người đầu tiên hoặc người cuối cùng đang đứng ("SsS...sS" hoặc "sSs...sS" hoặc "SsS...Ss") thì chắc chắn trạng thái của N người này sẽ luân phiên thay đổi và tạo thành 1 chu trình độ dài là 2.

 - Trong trường hợp trạng thái người là luân phiên đứng ngồi và 2 người ở 2 đầu đang đứng (trường hợp đặc biệt của nhận xét 1) thì lúc này, mặc dù sau 1h thì số người đang ngồi sẽ tăng lên, nhưng nó lại trở thành 1 trạng thái trong trường hợp 3, và nó cùng sẽ thành 1 chu trình độ dài 2.

 - Các trạng thái còn lại, sau một số lượng bước nào đó, thì nó cũng sẽ trở thành một trong các trạng thái đã nêu (có 1 đoạn liên tiếp mà có từ 2 người trở lên đang đứng, hoặc N người luân phiên đứng ngồi).

Từ các nhận xét trên, ta thực hiện duyệt "trâu", sử dụng 3 chuỗi tạm để lưu lại 3 trạng thái pre (trước đó), cur (hiện tại) và nxt (tiếp theo). Trạng thái ta đang có là cur, sau 1h ta sẽ sinh ra được trạng thái là nxt, lúc này ta có:

 - Nếu nxt = cur tức là tất cả N người này đang đứng hoặc đang ngồi, thì cũng đồng nghĩa đây là trạng thái hằng, sẽ không thay đổi dù có trải qua bao nhiêu giờ sau đi nữa nên ta có thể kết luận đây là trạng thái sau khi kết thúc buổi meeting, không cần duyệt thêm.

 - Nếu nxt = pre (trạng thái luân phiên đứng ngồi) thì ta đã biết nó có chu trình 2, lúc này dựa vào tính chẵn lẻ so với thời gian kết thúc mà ta xác định trạng thái khi kết thúc buổi meeting là cur hoặc nxt.

 - Nếu không nằm trong 2 trường hợp trên, thì ta gán pre = cur và cur = nxt, tiếp tục duyệt.
Từ các nhận xét ở trên thì ta có thể thấy rằng số lần duyệt sẽ không chênh lệch nhiều so với N, độ phức tạp chỉ khoảng O(T*N*max(N,L)), xấp xỉ O(10^7)

CÁC PHẢN HỒI

  • ngmq - 22/08/15 22:48
    Bài E làm QHD dpt chỉ là O(8 * N) thôi.
  • Guizebb - 23/08/15 00:08
    ad bài 2 e làm như v sao k acc v ad
  • mrtan_lovelife - 23/08/15 11:35
    @guizebb 1 ≤ ai, bj, ck ≤ 10^9 nha bạn, dùng mảng đếm phân phối không được đâu
  • mrtan_lovelife - 23/08/15 11:39
    xin lỗi mình nhầm, bạn dùng map chứ không phải đếm phân phối
  • admin - 23/08/15 14:31
    Guizebb: Ví dụ mảng a là: 2 2 3 3. cách làm của bạn đếm trùng số 2 hai lần (d[a[1]] = d[a[2]] = 2). Đếm trùng số 3 hai lần.
  • pqhieu - 23/08/15 14:57
    bài 2, chỗ nhân lại với nhau là nhan cái gì?
  • AresGod - 23/08/15 15:08
    @pqhieu: nhân số lượng phần tử = a[i] trong mảng B với số lượng phần tử = a[i] trong mảng C
  • nxphuc - 23/08/15 15:33
    @pqhieu: có hỏi hay gì thì cũng làm ơn có chủ ngữ vị ngữ cái nhá, trong này không phải ai cũng nhỏ hơn đâu, đừng nói trổng kiểu đó
  • lecong - 30/08/15 20:54
    bài D có cách khác QHĐ hay tham lam ko mn? nếu có thì chỉ cụ thể giúp mình nhé
  • lilom13 - 18/01/16 19:49
    Sắp xếp 3 dãy số trên, sau đó sử dụng 3 con trỏ cho ba dãy số để lần lượt đếm số lượng phần tử bằng nhau ở từng chuỗi, nhân lại với nhau và cộng vào kết quả cuối cùng.

    Dữ liệu bài này kiểu mảng mà, sao đếm số lượng bằng nhau ở từng chuổi là sao. Mà đếm số lượng phần tử bằng nhau phải dùng 3 vòng lặp, sử dụng 1 vòng lặp sao đếm đc
Back to Top