[Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

Thảo luận trong 'Writeup WhiteHat Grand Prix' bắt đầu bởi BkavCR, 20/09/14, 10:09 AM.

  1. BkavCR

    BkavCR Super Moderator

    Tham gia: 27/09/13, 11:09 AM
    Bài viết: 204
    Đã được thích: 94
    Điểm thành tích:
    48
    Đề thi:
    [FONT=&quot]Tít là một người rất thích hình học và đặc biệt là các hình vuông. Nhân tiện hôm sinh nhật Tít, mẹ Tít có mua một chiếc bánh hình chữ nhật với chiều dài M, và chiều rộng N. Biết Tít thích hình vuông, mẹ Tít đã đố Tít cắt miếng bánh ra thành các hình vuông, sao cho số hình vuông là ít nhất.[/FONT]
    [FONT=&quot]INPUT : M,N[/FONT]
    [FONT=&quot]OUTPUT: số ô vuông ít nhất.[/FONT]
    [FONT=&quot]
    [/FONT]

    [FONT=&quot]nc grandprix.whitehat.vn 7020
    M,N
     
    Last edited by a moderator: 20/09/14, 11:09 AM
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  2. hoank

    hoank W-------

    Tham gia: 11/05/14, 04:05 PM
    Bài viết: 25
    Đã được thích: 0
    Điểm thành tích:
    16
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Bài này thì thôi khỏi phải writeup :))
    :D
    NP khó nên bỏ qua :v
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  3. vhnvn

    vhnvn W-------

    Tham gia: 22/09/14, 02:09 PM
    Bài viết: 13
    Đã được thích: 0
    Điểm thành tích:
    16
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Bài này BTC ra đề sai từ đầu + viết đề ko rõ ràng.
    Bài này có 2 khả năng:
    1. Các nét cắt phải có thứ tự, mỗi lần cắt chỉ được dùng 1 nhát song song với 2 trục cắt 1 HCN có sẵn thành 2 HCN con.
    Trường hợp này độ phức tạo là O(M*N*(M+N)), dùng QHĐ F[m][n]:=số số hình vuông ít nhất phủ HCN mxn theo đk trg hợp này.
    2. Các nét cắt có thể dừng bất cứ đâu, có thể cắt kiểu U, Z gì cũng đc, trg hợp này NP Hard, dùng cây tìm kiếm có lưu vết trạng thái để giải.

    Mình thử hết các cách để gửi, nhưng cách nào cũng ko đúng, gửi cho BTC KQ dùng khả năng 1 thì xác suất giống output của BTC là khoảng 60%. Còn dùng cách 2 thì luôn fail ở stage 2-3. Cuối cùng mình cho chạy liên tục cách 1 cho đến khi đúng hết (xác suất 60%^10 = 0.6% - chạy 1000 lần sẽ có khả năng đúng 6 lần).

    Sau đó BTC mới sửa lại, nhưng lúc đó mình ko kiểm tra lại nữa.
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  4. ping

    ping Super Moderator

    Tham gia: 19/06/13, 09:06 AM
    Bài viết: 102
    Đã được thích: 34
    Điểm thành tích:
    48
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Cảm ơn bạn đã góp ý, vấn đề ở bài ACM 300 BTC đã phát hiện và tiến hành khắc phục trong tối 19/09. BTC cũng đã có thông báo trên trang chủ cuộc thi.
     
    Last edited by a moderator: 22/09/14, 05:09 PM
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  5. babyrobots

    babyrobots W-------

    Tham gia: 08/03/14, 12:03 PM
    Bài viết: 2
    Đã được thích: 0
    Điểm thành tích:
    1
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Mấu chốt của bài này không phải là độ phức tạp hay NP hard hay gì cả, mà là yếu tố thời điểm.
    Ông chú của mình làm ở Viettel tiết lộ rằng vào khoảng 15h chiều ngày 19/09, server của Whitehat sẽ bị hacker cài mã độc, mình chỉ cần nạp, à, chỉ cần submit số 1 lên là level nào cũng pass. Tỉ lệ 90%.
    Mình đã thử và đã thành công.
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  6. python

    python Administrator

    Tham gia: 20/06/13, 09:06 PM
    Bài viết: 91
    Đã được thích: 12
    Điểm thành tích:
    18
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014


    BTQ đã tiếp nhận phản hồi của bạn, chúng tôi sẽ kiểm tra và phản hồi lại trong thời gian sớm nhất. Cảm ơn bạn
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  7. HieuNT_Admin

    HieuNT_Admin Administrator

    Tham gia: 29/06/13, 10:06 AM
    Bài viết: 225
    Đã được thích: 14
    Điểm thành tích:
    38
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Cảm ơn bạn đã thông báo, BTC đã tiếp nhận để kiểm tra.

    Tuy nhiên theo nội dung thông báo này của bạn, ông chú Viettel và đội bạn có vẻ đang vi phạm quy chế thi là chia sẻ flag, vì chỉ có những thành viên trong các đội tham gia dự cuộc thi mới được phân quyền truy cập vào hệ thống server thi. BTC cũng sẽ kiểm tra trường hợp này và xử lý vi phạm theo quy chế (nếu có) :).
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  8. hoank

    hoank W-------

    Tham gia: 11/05/14, 04:05 PM
    Bài viết: 25
    Đã được thích: 0
    Điểm thành tích:
    16
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Có lẻ là đúng thật :)) khi đấy có mỗi team babyrobots làm được bài này ;)
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  9. sunny

    sunny Điều hành viên Thành viên BQT

    Tham gia: 30/06/14, 10:06 PM
    Bài viết: 1,888
    Đã được thích: 861
    Điểm thành tích:
    113
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Don't. Hi vọng đấy không phải sự thật, theo thống kê không chính thức của mình, babyrobots đã có 1 lượng fan khá đông trên diễn đàn và ngoài diễn đàn. Đừng làm các bạn ấy thất vọng thế.
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  10. yeuchimse

    yeuchimse W-------

    Tham gia: 21/10/13, 10:10 PM
    Bài viết: 133
    Đã được thích: 0
    Điểm thành tích:
    36
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Tài tình chi lắm cho trời đất ghen, ai bảo team toàn những người xinh xinh cơ :rolleyes:

    [​IMG] 8.png
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  11. python

    python Administrator

    Tham gia: 20/06/13, 09:06 PM
    Bài viết: 91
    Đã được thích: 12
    Điểm thành tích:
    18
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Cám ơn bạn babyrobots đã phản ánh. Mình xin trả lời vấn đề này như sau:
    1. Vấn đề mã độc, BTC đã kiểm trả và xác nhận thông tin này với bạn babyrobots, hệ thống chứa đề vẫn an toàn.
    2. Về đề thi, bài thi này sau khi BTC xử lý lỗi các đội đã giải bình thường, và BTC đã có thông báo ngay sau đó.
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  12. knight9

    knight9 W-------

    Tham gia: 12/03/14, 09:03 AM
    Bài viết: 55
    Đã được thích: 0
    Điểm thành tích:
    16
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Bạn ý troll vui thôi mà =))
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  13. HD67

    HD67 W-------

    Tham gia: 19/08/14, 06:08 PM
    Bài viết: 2
    Đã được thích: 0
    Điểm thành tích:
    1
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    Thấy chưa anh/chị nào viết chi tiết bài này ( dành cho các bạn mới tiếp cận tìm hiểu ) em mạo muội viết .
    Cá nhân em thấy đây là 1 bài toán quy hoạch động kiểu bottom-up khá hay.Em dùng công thức sau để giải:

    View attachment 2011

    Độ phức tập của thuật toán O(m*n*(m+n)) chạy được với dữ liệu m,n < 5000
    Đây là bài của em nó trên http://vn.spoj.com/problems/VNCUT/
    Source code em viết bằng C++ ,build trên Dev-C++ 5.6.3
    http://pastebin.com/96QcY92a

    P/s :BTC cho em hỏi ,sao chỉ có khiêm tốn 1 bài ACM vậy:( . Device_Square.jpg
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  14. trungpos

    trungpos W-------

    Tham gia: 07/07/14, 03:07 PM
    Bài viết: 9
    Đã được thích: 0
    Điểm thành tích:
    6
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    1 bài để kiểm tra khả năng thuật toán thôi vì làm ATTT cần kết hợp nhiều yếu tố, nếu muốn giải nhiều bài toán hơn nữa thì có thể tham gia Tin học QG, OLP SV, ACM/ICPC,...
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
  15. vhnvn

    vhnvn W-------

    Tham gia: 22/09/14, 02:09 PM
    Bài viết: 13
    Đã được thích: 0
    Điểm thành tích:
    16
    Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

    E sub thử bài đó chưa :)) đc bn điểm :))
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan