thảo luận Leetcode contest, đường tới Guardian

freedom.9 · 4/8/24

nahnahinin đã nói:
q4 dễ, re-root dfs sở trường. Thằng leet nó cho q3 oái oăm thật

Fence rảnh cho mình cái list hay hướng dẫn về re-root để mình luyện tập phát, mình đang luyện mấy bài hard về Graph :love:

xem mấy cái clip của tụi Ấn nghe tụi nó nói khó chịu quá.
Mà rating fence chắc cao nhỉ

nahnahinin · 4/8/24

chiyeuemthoi đã nói:
Q3 Q4 đọc mãi chả ra bỏ vậy k nhìn ra dc gì

+, q3 thì thím xét 2 for lồng nhau 0->n/2 rồi 0->m/2
+, với 1 điểm (i,j) sẽ tạo thành 1 hình chữ nhật 4 điểm đối xứng (i,j) (n-i-1,j), (i,m-j-1), (n-i-1,m-j-1)
vì toàn bộ 4 điểm bắt buộc phải bằng nhau tức toàn bộ là 0 hoặc toàn bộ là 1, tức là với mỗi 4 điểm này, thì fen phải + 4-max(c0,c1) với c0,c1 là số lượng=0 và số lượng=1 vào res. Đồng thời vì cái chi tiết này mà cái này sau khi tạo thành palindrome thì tổng 1 luôn luôn %4==0.
+, tiếp theo là cần xét 2 trường hợp n lẻ và m lẻ. Thì phải xét cái row/column ở giữa, vì case trên chưa cover được. Gọi a1 là số lượng 2 thằng đối xứng và có giá trị =1, a2 là số thằng đối xứng và có 1 thằng =1, 1 thằng =0. Với các cặp đối xứng và đều bằng 1 thì a1+=2, ngược lại đối xứng và khác nhau thì a2+=1.
nếu a2==0 thì + a1%4 vào res (vì cái tổng khi xét 4 điểm bên trên kia luôn %4==0 rồi)
ngược lại, a2!=0 thì + a2 luôn vào res
+, cuối cùng là trường hợp n%2==1&&m%2==1 thì phải xét cái điểm ở giữa grid[n/2][m/2] nếu nó ==1 thì bắt buộc biến nó về 0 và res+=1

Thế là xong, lắm cái cần cover khs gần 3k thằng giải đc

nahnahinin · 4/8/24

freedom.9 đã nói:
Fence rảnh cho mình cái list hay hướng dẫn về re-root để mình luyện tập phát, mình đang luyện mấy bài hard về Graph xem mấy cái clip của tụi Ấn nghe tụi nó nói khó chịu quá.
Mà rating fence chắc cao nhỉ

Thím đọc các loại dp thì đọc ở đây này:

DP on Trees - Solving For All Roots

Tree DP problems involving rerooting.

usaco.guide

Bọn top coder nó code theo 1 format hết, thím nhìn cái usaco này rồi check với mấy tay code c++ mấy page đầu là thấy na ná cái này ngay. 1 cái dfs cho dp, 1 cái dfs cho re-root.
Cái re-root nó cũng chỉ là dp on tree rồi dùng kết quả dp để tính toán trong lúc re-root thôi chứ cũng chẳng phải cái gì mới. trước em cũng luyện cái này mà cũng ko lưu lại mấy bài đã làm.

thím leo guardian thì trang bị luôn dp digit với dp bitmask trong cái link trên cho đủ combo phá đảo 99% dp leet.

billy_don · 4/8/24

nahnahinin đã nói:
Thím đọc các loại dp thì đọc ở đây này:

DP on Trees - Solving For All Roots

Tree DP problems involving rerooting.

usaco.guide

Bọn top coder nó code theo 1 format hết, thím nhìn cái usaco này rồi check với mấy tay code c++ mấy page đầu là thấy na ná cái này ngay. 1 cái dfs cho dp, 1 cái dfs cho re-root.
Cái re-root nó cũng chỉ là dp on tree rồi dùng kết quả dp để tính toán trong lúc re-root thôi chứ cũng chẳng phải cái gì mới. trước em cũng luyện cái này mà cũng ko lưu lại mấy bài đã làm.

thím leo guardian thì trang bị luôn dp digit với dp bitmask trong cái link trên cho đủ combo phá đảo 99% dp leet.

trang trên hay quá thím ơi, đội ơn thím

freedom.9 · 4/8/24

nahnahinin đã nói:
Thím đọc các loại dp thì đọc ở đây này:

DP on Trees - Solving For All Roots

Tree DP problems involving rerooting.

usaco.guide

Bọn top coder nó code theo 1 format hết, thím nhìn cái usaco này rồi check với mấy tay code c++ mấy page đầu là thấy na ná cái này ngay. 1 cái dfs cho dp, 1 cái dfs cho re-root.
Cái re-root nó cũng chỉ là dp on tree rồi dùng kết quả dp để tính toán trong lúc re-root thôi chứ cũng chẳng phải cái gì mới. trước em cũng luyện cái này mà cũng ko lưu lại mấy bài đã làm.

thím leo guardian thì trang bị luôn dp digit với dp bitmask trong cái link trên cho đủ combo phá đảo 99% dp leet.

Bookmarked, xịn quá. Thanks my fence :ah:

Mấy nay tranh thủ cày ráng tới cuối năm lên Guardian. 200 điểm nữa mà gian nan quá =((

NudeDuck · 4/8/24

Nay em comeback contest. Dạo này đỡ cheating chưa các bác

freedom.9 · 4/8/24

2 bài hard còn 7 điểm 8 điểm =((

freedom.9 · 4/8/24

Q4 1 accepted, Q3 ko nghĩ ra cái hướng nào cả. Rip contest :ah:

chiyeuemthoi · 4/8/24

Q2 ae dùng gì vậy dùng bfs TLE kbt tối ưu kiểu gì

TLE_WA · 4/8/24

Q3 chú ý cái constraint các shortcut chỉ có ôm trọn shortcut khác hoặc không giao nhau. Không có kiểu overlap nửa vời.

lilleboybk · 4/8/24

Q3 em dùng ý tưởng của Linked List , mỗi điểm lưu điểm kế tiếp chưa bị "che" bởi các đoạn. Dường đi ngắn nhất là số điểm chưa bị che. Q4 em đoán vẫn ý tưởng ấy. Mỗi điểm i lưu điểm kế tiếp j mà từ i -> j-1 là chuỗi "01....". Query đổi màu thì cập nhật mảng next, query đếm thì tính từ mảng next ra.

nahnahinin · 4/8/24

chiyeuemthoi đã nói:
Q2 ae dùng gì vậy dùng bfs TLE kbt tối ưu kiểu gì

t dùng sẵn template dijkstra tốn có 3,4ph code, mà nhìn chắc là dp o(n^2)

NudeDuck · 4/8/24

móa giải ra câu 3 mà fail câu 2, mấy bác cho e hỏi test case này n=14, queries=[[0,6],[4,12]] sao ra [8,6] được ta, phải [8,5] chứ

nahnahinin · 4/8/24

làm đc 3q đủ bù rating cho hôm qua thọt

lilleboybk · 4/8/24

nahnahinin đã nói:
+, q3 thì thím xét 2 for lồng nhau 0->n/2 rồi 0->m/2
+, với 1 điểm (i,j) sẽ tạo thành 1 hình chữ nhật 4 điểm đối xứng (i,j) (n-i-1,j), (i,m-j-1), (n-i-1,m-j-1)
vì toàn bộ 4 điểm bắt buộc phải bằng nhau tức toàn bộ là 0 hoặc toàn bộ là 1, tức là với mỗi 4 điểm này, thì fen phải + 4-max(c0,c1) với c0,c1 là số lượng=0 và số lượng=1 vào res. Đồng thời vì cái chi tiết này mà cái này sau khi tạo thành palindrome thì tổng 1 luôn luôn %4==0.
+, tiếp theo là cần xét 2 trường hợp n lẻ và m lẻ. Thì phải xét cái row/column ở giữa, vì case trên chưa cover được. Gọi a1 là số lượng 2 thằng đối xứng và có giá trị =1, a2 là số thằng đối xứng và có 1 thằng =1, 1 thằng =0. Với các cặp đối xứng và đều bằng 1 thì a1+=2, ngược lại đối xứng và khác nhau thì a2+=1.
nếu a2==0 thì + a1%4 vào res (vì cái tổng khi xét 4 điểm bên trên kia luôn %4==0 rồi)
ngược lại, a2!=0 thì + a2 luôn vào res
+, cuối cùng là trường hợp n%2==1&&m%2==1 thì phải xét cái điểm ở giữa grid[n/2][m/2] nếu nó ==1 thì bắt buộc biến nó về 0 và res+=1

Thế là xong, lắm cái cần cover khs gần 3k thằng giải đc

Q3 em dùng dp, dp là chi phí để cho num_1 % 4 === i. Đếm num_1 ban đầu rồi khởi tạo dp[num_1 % 4] = 0. Rồi duyệt từng ô trong 1/4 bảng, thử chuyển nó và các ô đối xứng cùng về 0 / 1 rồi cập nhật mảng dp mới. Xong in ra dp[0].

freedom.9 · 4/8/24

Ngồi nghĩ cách xóa edge mà ko làm do ko chứng minh được :too_sad:

via theNEXTvoz for iPhone

lilleboybk · 4/8/24

NudeDuck đã nói:
móa giải ra câu 3 mà fail câu 2, mấy bác cho e hỏi test case này n=14, queries=[[0,6],[4,12]] sao ra [8,6] được ta, phải [8,5] chứ

Query 2 là 0 -> 1 -> 2 -> 3 -> 4 -> 12 -> 13 ấy bác.

freedom.9 · 4/8/24

NudeDuck đã nói:
móa giải ra câu 3 mà fail câu 2, mấy bác cho e hỏi test case này n=14, queries=[[0,6],[4,12]] sao ra [8,6] được ta, phải [8,5] chứ

TLE_WA đã nói:
Q3 chú ý cái constraint các shortcut chỉ có ôm trọn shortcut khác hoặc không giao nhau. Không có kiểu overlap nửa vời.

Á đù các shortcut ko giao nhau hả fence, thế này thì việc xóa node mới đúng nhỉ.
Mình nghĩ cách xóa node rồi mà nghĩ trường hợp giao nhau nên ko làm ra :too_sad:

via theNEXTvoz for iPhone

freedom.9 · 4/8/24

chiyeuemthoi đã nói:
Q2 ae dùng gì vậy dùng bfs TLE kbt tối ưu kiểu gì

Q2 cứ Bfs rồi thêm edge vô graph rồi Bfs lại thôi có timeout gì đâu nhỉ

via theNEXTvoz for iPhone

NudeDuck · 4/8/24

lilleboybk đã nói:
Query 2 là 0 -> 1 -> 2 -> 3 -> 4 -> 12 -> 13 ấy bác.

Ủa e tưởng đường đi ngắn nhất là 0 -> 6 -> 5 -> 4 -> 12 -> 13 chứ bác nhỉ

thảo luận Leetcode contest, đường tới Guardian

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này