1 năm, 4 tháng trước

Xin chào các bạn. Hôm nay là Chủ nhật ngày 15/5, ngày đầu tiên của vòng chung kết thế giới ACM-ICPC. World Finals năm nay được tổ chức ở Phú Kẹt (Thái Lan), từ hôm nay các đội tuyển đã bắt đầu hạ cánh xuống Phú Kẹt. Ngày thi chính thức sẽ được diễn ra vào Thứ năm ngày 19/5, cuộc thi kéo dài 5 tiếng, gồm ít nhất 10 bài.

Các đội tuyển tham dự là những đội xuất sắc nhất, vượt qua vô số đội mạnh khác (ví dụ như đội của mình) tại các cuộc thi Regional trước đó. Năm nay Việt Nam có đến hai đội tham dự World Finals, đó là:

  1. Đội BYTE đến từ Đại học UET, gồm 3 thành viên:
    + Đỗ Ngọc Khánh
    + Nguyễn Tiến Trung Kiên
    + Phạm Văn Hạnh
  2. Đội HCMUS - Shine đến từ Đại học HCMUS, gồm 3 thành viên:
    + Lê Yên Thanh
    + Phạm Việt Khôi
    + Trương Minh Bảo
  3. Ngoài ra còn một đội người Việt đến từ đại học NUS ở Singapore. Đó là đội RRwatameda, gồm 3 thành viên:
    + Nguyễn Thành Trung
    + Nguyễn Tấn Sỹ Nguyên
    + Nguyễn Hùng Tâm

Mong các bạn hãy cổ vũ nhiệt tình cho các đội tuyển Việt Nam dành kết quả cao nhất ở World Finals lần này.

Ngoài ra, để hưởng ứng phong trào đỏ đen cùng với mùa Euro đang đến gần, ban tổ chức VNOI cũng xin tổ chức một Gameshow cá độ nho nhỏ. Các thành viên VNOI đều có thể tham gia, thể lệ của chương trình là đặt cược cho đội Việt Nam trong số 3 đội trên dành thứ hạng cao nhất. Các bạn có thể đặt cược một số tiền bất kỳ, và sẽ thắng lớn nếu như may mắn đoán đúng, làm giàu quả thật không khó. Sau đây là tỷ lệ cược của nhà cái:

  • Đội BYTE: Đặt 3 ăn 0.
  • Đội HCMUS - Shine: Đặt 69 ăn 0.
  • Đội RRwatameda: Đặt 109 + 7 ăn 0.

Thủ tục đặt tiền sẽ được cho biết sau. Xin cảm ơn :))

1 năm, 4 tháng trước

Sao BYTE của anh được đánh giá thấp thế :))

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

BYTE của anh là sao anh :))

1 năm, 4 tháng trước

RRwatameda với BYTE ngang ngửa nhau :)) hi vọng là lần này sẽ có medal mặc dù biết là khá khó :)) mục tiêu năm nay của vn chắc vẫn là vào top 30 cơ mà mục tiêu này chắc là BYTE thừa khả năng đạt được :v (Ý kiến chủ quan)

1 năm, 4 tháng trước

Hôm 19 thi vào mấy giờ, giờ Việt Nam ấy mọi người nhỉ :D

1 năm, 4 tháng trước

Link bảng rank (hiện tại đang là rank practice. Sau frozen bọn mình AC thêm 2 bài :v) 

Thời gian thi: 10h giờ VN.

1 năm, 4 tháng trước
Trả lời RR
  Hiện bài gốc

Scoreboard này đẹp hơn anh ei :v

https://icpc.baylor.edu/scoreboard/

Livestream WF cho ngày mai :v

https://www.youtube.com/channel/UCDBXshZdICEHr0HSVsLrydA

1 năm, 4 tháng trước

Để nhắn tin bình chọn cho Đội BYTE, các bạn hãy vào twitter.com hoặc instagram.com và soạn tin #ICPC2016 #UETVNU

Để nhắn tin bình chọn cho Đội HCMUS - Shine, các bạn hãy soạn tin #ICPC2016 #HCMUS

Để nhắn tin bình chọn cho Đội RRwatameda, các bạn hãy soạn tin #ICPC2016 #NUSingapore

Đội càng nhận được nhiều tin nhắn bình chọn thì càng có nhiều cơ hội được livestream :3.

 

1 năm, 4 tháng trước

Tường thuật:

Phút 11: Chulalongkorn University đến từ Băng Cốc - Thái Lan là đội đầu tiên AC bài C, tạm thời vươn lên dẫn đầu.

Phút 12: Kim Il Sung University đến từ Triều Tiên AC bài C

Phút 13: Nizhny Novgorod State University đến từ Nga AC bài C

Phút 15: Harvard University đến từ Mỹ là đội đầu tiên AC bài E sau 2 lượt sub

Phút 17:  Moscow State University đến từ Nga AC bài E, vượt lên vị trí thứ tư

Phút 18: Comenius University đến từ Slovakia AC bài C. Massachusetts Institute of Technology là đội đầu tiên AC bài L sau 3 lượt sub

Phút 19: Universidade de São Paulo - Campus de São Carlos và University of Zagreb AC bài C

Phút 20: Nizhny Novgorod State University là đội tiếp theo AC bài L, vươn lên vị trí dẫn đầu.

Phút 23: RRwatameda đã AC bài E, tiếp bước là đội BYTE đã AC bài C. Đội HCMUS - Shine WA ở bài C

Phút 29: Massachusetts Institute of Technology AC bài C, vươn lên vị trí thứ 3.

Phút 32: RRwatameda AC bài C, vươn lên vị trí thứ 3

Phút 34: HCMUS - Shine tiếp tục WA ở bài C.

Phút 41: Sau 3 lượt sub, cuối cùng HCMUS - Shine cũng AC bài C.

Phút 42: St. Petersburg ITMO University là đội đầu tiên AC bài B

Phút 43: Shanghai Jiao Tong University AC bài C và L, vươn lên vị trí dẫn đầu

Phút 44: St. Petersburg State University là đội đầu tiên AC bài K.

Phút 57: HCMUS - Shine AC bài L

Phút 64: RRwatameda AC bài L

Phút 75: BYTE AC bài K

Phút 79: RRwatameda WA bài G, University of Wroclaw là đội đầu tiên giải bài D

Phút 83: RRwatameda tiếp tục WA bài G. Bài này là một bài hình, yêu cầu độ chính xác cực cao, đặc biệt trong việc tính góc

Phút 86: HCMUS - Shine WA bài E lần thứ hai

Phút 87: University of Wroclaw AC bài E, vươn lên vị trí thứ 6

Phút 89: HCMUS - Shine bỏ bài E, chuyển bài G và tiếp tục WA

Phút 90: Shanghai Jiao Tong University AC bài B sau 2 lượt sub, vươn lên vị trí thứ 3

Phút 91: Kim Il Sung University AC bài K, chiếm vị trí thứ 3.

Phút 102: RRwatameda đã AC bài G sau 3 lượt sub

Phút 114: RRwatameda đã AC bài B sau 2 lượt sub và hiện đang ở vị trí 12.

Phút 134: HCMUS - Shine đã AC bài G.

1 năm, 4 tháng trước

mọi người có ai có link đề chưa?

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

Có ảnh thôi anh, https://twitter.com/petrmitrichev.

EDIT: Đã có: https://icpc.baylor.edu/worldfinals/problems/icpc2016.pdf

1 năm, 4 tháng trước
Trả lời d3antran
  Hiện bài gốc

Bắt đầu dịch đề :)

Bài C

Xưởng chế tạo Advanced Ceiling Manufacturers (ACM) đang phân tích các thuộc tính của các sản phẩm trần chống sập Incredibly Collapse-Proof Ceilings (ICPCs) của hãng. Một sản phẩm ICPC gồm n lớp chất liệu, mỗi lớp lại có một độ chống sập nguyên dương khác nhau. Hãng ACM muốn lấy độ chống sập của các lớp chất liệu, lưu trữ các giá trị đó vào một cây nhị phân tìm kiếm, và kiểm tra sự tương quan giữa hình dạng của cây với chất lượng của sản phẩm.

Nói theo cách rõ hơn, hãng ACM sẽ tìm độ chống sập của mỗi lớp chất liệu, sắp xếp lại theo thứ tự lớp ở trên đến lớp ở dưới, và lần lượt chèn từng giá trị vào cây nhị phân. Để chèn giá trị v vào cây, ta làm như sau:

Nếu cây đang rỗng, v sẽ trở thành gốc của cây

Nếu cây không rỗng, so sánh v với gốc của cây. Nếu v nhỏ hơn gốc của cây, chèn v vào cây con bên trái gốc cây , nếu v lớn hơn gốc của cây, chèn v vào cây con bên phải của cây.

ACM có các mẫu trần chống sập và họ muốn phân tích chúng bằng cách nhóm chúng lại với nhau. Các mẫu trần ở cùng một nhóm nếu hình dạng cây tương ứng với mẫu của chúng có hình dạng giống nhau.

Ví dụ như hãng ACM có 5 mẫu trần, mỗi mẫu có 3 lớp như trong ví dụ 1 hay như trong hình C.1. Ta thấy mẫu đầu tiên có độ chống sập của lớp trên cùng là 2, lớp ở giữa là 5 và lớp dưới cùng là 1. Mẫu đầu tiên có độ chống sập của lớp trên cùng, lớp giữa và lớp dưới cùng lần lượt là 3, 1 và 4. Hai mẫu này tạo ra hai cây có hình dạng giống nhau, nên chúng cùng một nhóm.

Bạn được cho thông tin về các mẫu trần nhà, nhiệm vụ của bạn là xác định số lượng cây có hình dạng khác nhau mà chúng tạo ra.

Dữ liệu

Dòng đầu là hai số nguyên n (1 <= n <= 50) là số lượng mẫu trần cần phân tích, và k (1 <= k <= 20) là số lớp của mỗi mẫu trần

n dòng tiếp theo miêu tả một mẫu trần, mỗi dòng gồm k số nguyên phân biệt có giá trị từ 1 đến 10^6, là độ chống sập của mỗi lớp chất liệu từ trên xuống dưới.

Output

In ra số lượng cây có hình dạng khác nhau

 

 

 

 

1 năm, 4 tháng trước
Trả lời bvd
  Hiện bài gốc

BYTE ngủ quên rồi à, dậy đi các em 

1 năm, 4 tháng trước

Lời giải của mình
- C: Bài này rất đơn giản chỉ cần so sánh cây thường
- E: Khá đơn giản, tăng hệ cơ số đến 10^4 và giảm dần giá trị 10^5 về 10
- L: Trung bình, dễ sai, sort tất cả các ổ mà tăng dữ liệu tăng lên sau khi format theo chiều tăng dần của dung lượng và sort tất cả các ổ mà dữ liệu giảm đi sau khi format theo chiều giảm dần của dung lượng "còn lại sau khi format" rồi chạy từ đầu về cuối.

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

- G: dễ, lời giải n^3: với mỗi đoạn nối 2 đầu muts tính trong O(n) kết quả.
lời giải n^2 log: Từ mỗi đầu mút nối đến tất cả các đoạn sẽ được n cặp 2 góc, sort lại tất cả các cặp, tịnh tiến để đếm giá trị đếm, mỗi lần đi qua một góc mở thì thêm cái độ dài cạnh vào, còn đi qua một góc đóng thì xoá độ dài cạnh đi

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

-K: dễ, dp 10^8 xét giá trị dp[i][j] với các giá trị dp[i + 2][j], dp[i][j - 2]. Nếu i và j là hai vị trí của một ngoặc thì có dp[i + 1][j - 1] <= dp[i][j]  <= dp[i + 1][j - 1] + 1.

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

2s mà 10^8 có hợp lý không anh? :v

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

-A: trung bình, với mỗi loại kẹo i sẽ thiết lập một mảng gồm a(i) giá trị là vị trí a(i) ngày cuối cùng tiếp theo mà loại kẹo thứ i cần có ví dụ với test 1 của đầu bài loại kẹo thứ 3 cần có kẹo ít nhất trước hoặc đúng ngày 7, 10, 14, 17.... từ đây sẽ thiết lập một priority_queue với mỗi ngày sẽ lấy ra loại kẹo có số ngày chờ là ít nhất, nếu loại kẹo nào có số ngày chờ âm thì break. Nếu đi hết tổng a(i) ngày thì sẽ đi được vô tận.

1 năm, 4 tháng trước
Trả lời hlnhvt
  Hiện bài gốc

2s máy WF chạy được ít nhất 5*10^8

1 năm, 4 tháng trước
Trả lời RRclone1
  Hiện bài gốc

-B: trung bình, bài này sau khi dijkstra tất cả các khoảng cách sort lại theo giá trị tổng khoảng cách đi và về của branch cho đến head. Sau khi sort lại sẽ dp[i][j] với i là vị trí và j là số lượng sub, vì dp[i][j] là hàm lồi (chứng minh một lúc là được :)) ) nên chỉ cần dùng tịnh tiến để tính giá trị. Độ phức tạp r * log + n^2