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

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

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)

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

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.

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

Để 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.

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.

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

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

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

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

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

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.

- 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

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

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

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

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

-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