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

[BkavCR]

Đề 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

 

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

Bài này thì thôi khỏi phải writeup )

NP khó nên bỏ qua :v

 

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.

 

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.

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.

 

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.

 

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.

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

 

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.

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ó) .

 

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.

Có lẻ là đúng thật ) khi đấy có mỗi team babyrobots làm được bài này

 

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

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ế.

 

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ế.

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ơ

 

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.

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 đó.

 

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 đó.

Bạn ý troll vui thôi mà =))

 

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 .

 

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,...

 

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 .

E sub thử bài đó chưa ) đc bn điểm )