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

BkavCR

VIP Members
27/09/2013
104
203 bài viết
[Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014
Đề 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
 
Chỉnh sửa lần cuối bởi người điều hành:
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
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
Comment
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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

vhnvn;15812 đã viết:
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.

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.
 
Chỉnh sửa lần cuối bởi người điều hành:
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
Comment
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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

babyrobots;15845 đã viết:
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.


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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

babyrobots;15845 đã viết:
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.

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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

babyrobots;15845 đã viết:
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.
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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

hoank;15852 đã viết:
Có lẻ là đúng thật :)) khi đấy có mỗi team babyrobots làm được bài này ;)
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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

sunny;15859 đã viết:
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ế.
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:

14908930808.png
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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

babyrobots;15845 đã viết:
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.

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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

python;15869 đã viết:
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 đó.

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
Comment
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
Comment
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
Comment
Re: [Writeup] Chủ đề ACM - Vòng loại WhiteHat Grand Prix 2014

HD67;15901 đã viết:
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:( .

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
Comment
Bên trên