Hướng dẫn NTUCoder Round #14

admin - 21/11/2015

Bài A: Đường 1 chiều:

       Xét 4 đường ngoài cùng, nếu 4 đường này xoay vòng (theo chiều kim đồng hồ hay ngược chiều kim đồng hồ đều được) thì với 2 giao lộ bất kỳ trên 4 đường này có đường đi. Do đó bất kỳ 2 giao lộ nào cũng có đường đi bằng cách đi ra vòng ngoài, chạy đến một chỗ nào đó rồi đi vô lại.

       Nếu 4 đường ngoài cùng không xoay vòng, tồn tại ngã hai mà tại đó chỉ có đi đến hoặc chi có đi ra. Nếu chỉ có đi đến => từ ngã hai này không thể đi đến giao lộ nào khác. Nếu chỉ có đi ra => không có giao lộ nào khác mà đi đến được ngã hai này.  Độ phức tạp O(1)

Bài B: Arga.io

       Bài này có 1 bẫy nhỏ: nếu kích thước --Ares-- nhỏ hơn kích thước bạn thì khi va chạm sẽ bị bạn ăn chứ không phải --Ares-- ăn bạn. Dùng giải thuật tham + stack: sắp xếp mảng kích thước bạn tăng dần và duyệt từ đầu đến cuối. Nếu --Ares--  > bạn: push stack. Nếu --Ares--  <= bạn: pop stack để ăn cho đến khi --Ares-- lớn lên và có thể ăn được bạn hiện tại (nhưng chưa ăn). Và tiếp tục duyệt mảng đến cuối. Độ phức tạp O(nlogn) do sắp xếp.

Bài C: Dãy số

       Bài này có đặc tính là số thứ 83 có giá trị là 3 => tuần hoàn về lại số thứ 2 (chịu khó liệt kê 100 số đầu mới biết được :-)). Độ phức tạp O(1)

Bài D: Vượt sông

      Đầu tiên với mỗi đèn, ta tính đoạn thời gian mà đèn đó bắt đầu quét qua điểm x và kết thúc quét qua điểm x (công thức vật lý). Sắp xếp các đoạn thời gian này theo thời gian bắt đầu. Sau đó trộn các đoạn đè lên nhau thành 1 đoạn. Kết quả có được các đoạn không đè lên nhau. Độ phức tạp O(nlogn).

      Ứng với mỗi người vượt sông tại thời gian tj, áp dụng tìm nhị phân để tìm đoạn có thời điểm bắt đầu quét nhỏ hơn tj. Từ đó suy ra kết quả. Độ phức tạp O(mlogn)

Bài E: Xe khách.

       Áp dụng thuật toán Dijisktra kết hợp Heap để tìm thời gian ngắn nhất đến các giao lộ. Khi pop, nếu xe gặp đèn đỏ thì dừng lại chờ, thời gian sẽ cộng thêm 1 và push lại. Nếu gặp đèn xanh thì đi qua các đỉnh khác. Độ phức tạp O(mnlog(mn)). 

Bài F: Hai dãy con

      Quy hoạch động: Độ phức tạp O(n2)

Bài G: Đổi tiền

* Gọi c[x][y] và way[x][y] lần lượt là số bước ít nhất và số cách để đến trạng thái (x,y). Nếu trạng thái hiện tại đang là (u,v) (có u tiền Singapore và v tiền Korea) thì duyệt hết K chức năng để xét đến các trạng thái mới.
* Trong quá trình BFS, khi xét đến một trạng thái mới (x,y) từ trạng thái hiện tại (u,v):
* Nếu way[x][y]=0 (trước đó chưa xét tới) thì gán way[x][y]=way[u][v] , c[x][y]=c[u][v]+1, đồng thời thêm trạng thái (x,y) vào queue.
* Nếu way[x][y]>0 (trước đó đã xét tới) và c[x][y]=c[u][v]+1 thì cập nhật thêm way[x][y]= way[x][y] + way[u][v].
* Những trạng thái đã vượt qua t thời gian thì không cần phải BFS nữa.

CÁC PHẢN HỒI

  • AresGod - 21/11/15 22:48
    bài C để O(1) bựa quá =)))) for 83 mà =)))
  • admin - 21/11/15 22:50
    O(1) cũng như O(83) mà
  • CSP_9 - 21/11/15 23:00
    bài B push stack với pop stack là gì ạ
  • petrpan - 21/11/15 23:01
    dùng stack để tìm th lớn nhất mà bé hơn nó chưa xài nha bạn )
  • AresGod - 21/11/15 23:01
    @admin: dạ biết mà ý là nghe nó hài hài ạ
  • abcdef6199 - 21/11/15 23:02
    bài E chỉ cần BFS thôi
  • mrtan_lovelife - 21/11/15 23:21
    @AresGod: Bài B mảng hằng trong O(1) mà anh
  • mrtan_lovelife - 21/11/15 23:24
    *Bài C
  • Khoidaik - 22/11/15 08:00
    Bài B sort rồi tìm kiếm nhị phân thì có vẻ dễ hiểu và cài đặt hơn
  • Neymar_FCB9x - 22/11/15 10:41
    bài B tìm kiếm nhị phân kiểu gì vậy? Khoidaik... mk cũng thử tìm kiếm rồi nhưng sai..
  • nxphuc - 22/11/15 11:31
    @Khoidaik: ukm, nhưng speed không nhanh bằng, rồi chưa kể BS ở đâu? mảng cũ hay mảng mới, nếu mảng cũ thì có những vị trí xài rồi, phairbor qua, tốn công duyệt lại
  • mrtan_lovelife - 22/11/15 12:07
    Bài E dùng cũng được
  • mrtan_lovelife - 22/11/15 12:07
    Bài E dùng BFS cũng được
  • romqn1999 - 22/11/15 15:46
Back to Top