VNOI Marathon 2015 Final round - Thảo luận

Forum VNOI đã tạm ngừng hoạt động. Các bạn có thể hỏi bài trên Group Facebook của bọn mình.

iamquang95

8 năm, 7 tháng trước

Kỳ thi VM15 đã kết thúc, các bạn vào đây cùng bàn luận về đề bài cũng như hướng giải các bài trong final round nhé <3

▲

▼

silver_rayleigh

8 năm, 7 tháng trước

Ai Ac bài VMPACKAGE rồi chỉ giúp mình vài gợi ý với :'(

▲

▼

theguiler

8 năm, 7 tháng trước

Sau này là hướng tiếp cận các bài của mình:

VMCIRCLE:

Bài này chỉ cần vẽ tay rồi nháp một lúc sẽ ra

N = 3, dùng 1 màu.
4 <= N <= 6, dùng 2 màu.
7 <= N, dùng 3 màu.

Cách tô các bạn nên tự nghĩ.

VMCUT2:

Đầu tiên mình chưa nghĩ ra thuật nên mình code Simulated Annealing (50 điểm final tests). Mình nghĩ với N <= 50, SA sẽ luôn đưa ra lời giải đúng.

Sau đó mình sinh test và code một lời giả tham lam: Chặt nhị phân kết quả trong [trọng số lớn nhất ... tổng trọng số].

Với mỗi số X, tính số phép cắt cây ít nhất để được tất cả các cây đều có trọng số <= X.

Giả sử đang dfs đến nút u:

sumWeight[u] = tổng trọng số các nhánh con của u (các nhánh đã được tỉa để trọng số các cây con được duyệt trước đo <= X)

numTree[u] = số lần cắt các cây con nhận u là tổ tiên ít nhất để tất cả các cây được cắt ra có trọng số <= X.

curWeight = trọng số nút u + tổng các sumWeight[v] với v là con của u.

Trừ dần curWeight cho các sumWeight[v] lớn nhất cho đến khi curWeight <= X.

numTree[u] = Số lần trừ bỏ = số lần cut
sumWeight[u] = curWeight sau khi đã trừ bỏ

numTree[1] chính là số lần cắt tối thiểu
numTree[1] <= K thì tồn tại cách cắt không quá K lần để được các cây con có trọng số <= v.

Vì mình thấy code này và SA giống nhau với mọi N <= 40 nên chấp nhận là lời giải này đúng mà không cần chứng minh.

VMPACKAGE:

Đầu tiên mình cũng code một lời giải bitmask để tạo test.

Sau đó mình nghĩ ra lời giải

dp[src][len] là xác suất đi từ src được đường đi dài nhất <= len.

Ban đầu dp[i][j] = 1.0

Xét các v là con của src và prob_v là xác suất đường đi src - v không bị ngập

dp[src][len] *= (1 - prob_v + prob_v * dp[src][len - 1]

Hiểu là có 2 cách: hoặc là đường đi này không đi được hoặc nếu đi được, chỉ chọn các đường có đường đi dài nhất <= len - 1.

Từ đây suy ra xác suất để đi được đường đi đúng len từ src là dp[src][len] - dp[src][len - 1].

Kết quả bằng bào nhiêu thì mình nghĩ bạn nên tự nghĩ.

ĐPT O(N * N).

Để ăn được sub cuối thì ta để ý là chỉ cần sai số không quá 6 chữ số. Cách làm thì bạn nên tự nghĩ.

VMROPES:

1. Lời giải trâu bò và một số cài tiến

Giả sử ta có danh sách các số đẹp là S[1..len]

Gọi dp[N] là số cách nối để được dây có độ dài N.

Suy ra dp[N] = tổng các dp[N - S[i] | i = 1..len]

ĐPT (N - A) * số lần duyệt S[i]

Có một cải tiến dễ dàng là đổi cách tính

F[S[l]] +F[S[l + 1]] + ... + F[S[r]] = sumF[S[r]] - sumF[S[l] - 1]

với sumF[i] = F[0] + ... + F[i].

Tức là ta sẽ chuyển các đoạn liên tiếp về cặp [l - 1, r]

Thấy rằng K = 6, A = 1, B = 95000 sẽ có 4637 là số cặp lớn nhất và duyệt một số lần có break nên không phải luôn duyệt hết.

Thì thấy rằng tổng số lần duyệt sẽ không quá 2.4e8. Nếu cài quy hoạch động không mod và cài khéo sẽ lên 94 điểm.

Mình nghĩ nếu cải tiến dùng asm có thể sẽ ăn full.

2. Lời giải ăn full

Đây là lời giải mình nghĩ ra sau khi thi và chạy bị RE local tests nhưng lại AC trên voj nên mình không chắc về lời giải. Để ý là ta có số x1..xt đẹp thì các số đẹp sinh ra sẽ là x1..xt(0..9) tức là ta chỉ cần quan tâm 2 chữ số cuối. Lập hàm dp[N][lastDig][curPos][greaterA][smallerB][positive] là số cách nối số N mà số đẹp đang được duyệt có chữ số cuối là lastDig, là chữ số thứ curPos, số đẹp hiện tại đã lớn hơn hẳn A và nhỏ hơn hẳn B chưa, số đẹp khác 0 chưa.

3. Bài toán tổng quát:

Phần này là ngoài lề nhưng là phần mình đang tìm hiểu nên tiện chia sẻ và hỏi luôn.

Cho các số S[1..len] với 1 <= S[i] <= K. Ta xét hàm

F[x] = tổng các F[x - S[i]]

Tính F[N] % MOD

Hoặc tổng quát hơn nữa là bài này: https://www.codechef.com/MARCH15/problems/RNG

Với FFT và Cayley-Hamilton theorem, bài toán trên có thể giải được trong O(C * K * logK * logN) với C là một số khá lớn (tầm 10) do ảnh hưởng của phép mod và FFT.

Mình dùng lời giải trên cho bài toán này nhưng TLE ngay khi K = 5e4, có lẽ do FFT code chưa tối ưu.

Mình nghĩ đến một lời giải nhân đa thức cho bài này. Tức là số cách nối là hệ số của một đa thức hoặc tích các đa thức nào đó nhưng chưa nghĩ ra. Không biết đa thức này có tồn tại hay không?

Nếu tồn tại đa thức này thì lời giải sẽ dễ dàng và tối ưu hơn dù ĐPT vẫn là O(K log K log N).

▲

▼

theguiler

8 năm, 7 tháng trước

Trả lời theguiler
Hiện bài gốc

Sau này là hướng tiếp cận các bài của mình:

VMCIRCLE:

Bài này chỉ cần vẽ tay rồi nháp một lúc sẽ ra

N = 3, dùng 1 màu.
4 <= N <= 6, dùng 2 màu.
7 <= N, dùng 3 màu.

Cách tô các bạn nên tự nghĩ.

VMCUT2:

Đầu tiên mình chưa nghĩ ra thuật nên mình code Simulated Annealing (50 điểm final tests). Mình nghĩ với N <= 50, SA sẽ luôn đưa ra lời giải đúng.

Sau đó mình sinh test và code một lời giả tham lam: Chặt nhị phân kết quả trong [trọng số lớn nhất ... tổng trọng số].

Với mỗi số X, tính số phép cắt cây ít nhất để được tất cả các cây đều có trọng số <= X.

Giả sử đang dfs đến nút u:

sumWeight[u] = tổng trọng số các nhánh con của u (các nhánh đã được tỉa để trọng số các cây con được duyệt trước đo <= X)

numTree[u] = số lần cắt các cây con nhận u là tổ tiên ít nhất để tất cả các cây được cắt ra có trọng số <= X.

curWeight = trọng số nút u + tổng các sumWeight[v] với v là con của u.

Trừ dần curWeight cho các sumWeight[v] lớn nhất cho đến khi curWeight <= X.

numTree[u] = Số lần trừ bỏ = số lần cut
sumWeight[u] = curWeight sau khi đã trừ bỏ

numTree[1] chính là số lần cắt tối thiểu
numTree[1] <= K thì tồn tại cách cắt không quá K lần để được các cây con có trọng số <= v.

Vì mình thấy code này và SA giống nhau với mọi N <= 40 nên chấp nhận là lời giải này đúng mà không cần chứng minh.

VMPACKAGE:

Đầu tiên mình cũng code một lời giải bitmask để tạo test.

Sau đó mình nghĩ ra lời giải

dp[src][len] là xác suất đi từ src được đường đi dài nhất <= len.

Ban đầu dp[i][j] = 1.0

Xét các v là con của src và prob_v là xác suất đường đi src - v không bị ngập

dp[src][len] *= (1 - prob_v + prob_v * dp[src][len - 1]

Hiểu là có 2 cách: hoặc là đường đi này không đi được hoặc nếu đi được, chỉ chọn các đường có đường đi dài nhất <= len - 1.

Từ đây suy ra xác suất để đi được đường đi đúng len từ src là dp[src][len] - dp[src][len - 1].

Kết quả bằng bào nhiêu thì mình nghĩ bạn nên tự nghĩ.

ĐPT O(N * N).

Để ăn được sub cuối thì ta để ý là chỉ cần sai số không quá 6 chữ số. Cách làm thì bạn nên tự nghĩ.

VMROPES:

1. Lời giải trâu bò và một số cài tiến

Giả sử ta có danh sách các số đẹp là S[1..len]

Gọi dp[N] là số cách nối để được dây có độ dài N.

Suy ra dp[N] = tổng các dp[N - S[i] | i = 1..len]

ĐPT (N - A) * số lần duyệt S[i]

Có một cải tiến dễ dàng là đổi cách tính

F[S[l]] +F[S[l + 1]] + ... + F[S[r]] = sumF[S[r]] - sumF[S[l] - 1]

với sumF[i] = F[0] + ... + F[i].

Tức là ta sẽ chuyển các đoạn liên tiếp về cặp [l - 1, r]

Thấy rằng K = 6, A = 1, B = 95000 sẽ có 4637 là số cặp lớn nhất và duyệt một số lần có break nên không phải luôn duyệt hết.

Thì thấy rằng tổng số lần duyệt sẽ không quá 2.4e8. Nếu cài quy hoạch động không mod và cài khéo sẽ lên 94 điểm.

Mình nghĩ nếu cải tiến dùng asm có thể sẽ ăn full.

2. Lời giải ăn full

3. Bài toán tổng quát:

Phần này là ngoài lề nhưng là phần mình đang tìm hiểu nên tiện chia sẻ và hỏi luôn.

Cho các số S[1..len] với 1 <= S[i] <= K. Ta xét hàm

F[x] = tổng các F[x - S[i]]

Tính F[N] % MOD

Hoặc tổng quát hơn nữa là bài này: https://www.codechef.com/MARCH15/problems/RNG

Mình dùng lời giải trên cho bài toán này nhưng TLE ngay khi K = 5e4, có lẽ do FFT code chưa tối ưu.

Nếu tồn tại đa thức này thì lời giải sẽ dễ dàng và tối ưu hơn dù ĐPT vẫn là O(K log K log N).

Chính xác là mình đang cần tìm một "phép nhân" thỏa mãn tính chất kết hợp (A * B) * C = A * (B * C), điểu kiện cần để có thể lũy thừa trong O(logN). Đối với bài toán trên mình có đa thức A = \(x^{S_1} + x^{S_2} + ... + x^{S_K}\). Ta nhân đa thức này với \((F_l; F_{l + 1}; ...;F(l + K - 1))\)thì sẽ ra \((F_l; G_{l + 1}; ....; G_{l + K - 1}; F_{l + K};...)\)trong đó \(F_x\)là số cách nối để đạt độ dài \(x\)chính xác tuyệt đối còn \(G_x\)là số cách nối có thể bị tính thừa. Để đạt trạng thái đúng ta chỉ cần copy lại đa thức cũ thành \((F_{l + 1}; F_{l + 2}; ...; F_{l + K})\). Tuy nhiên "phép nhân" này không đảm bảo (P * A) * A = P * (A * A) và ta không thể lũy thừa theo bit được. Nếu phép tính này tồn tại thì ta sẽ không cần Cayley - Hamilton nữa, bài toán sẽ trở nên dễ dàng hơn nhiều. Mình không học sâu về toán, ai làm qua dạng này rồi có thể cho mình biết phép tính này có tồn tại hay không?

Về cách nhân FFT % MD. Nếu dùng NTT thì sẽ bị ảnh hưởng do phép % và việc khai căn, lũy thừa phải tính trong O(log MOD). Thêm nữa là chỉ có thể dùng NTT cho các số có primitive root nên ta phải tính 3 số mod có primitive root sau đó dùng CRT để tính theo mod MD. Cách này cực kỳ lằng nhằng và chậm.

Trên Codeforces có một bài post hỏi về việc này. Mình tìm thấy một trick trong Petr's blog. Mọi người có thể tham khảo thêm.

▲

▼

theguiler

8 năm, 7 tháng trước

Trả lời theguiler
Hiện bài gốc

Sau này là hướng tiếp cận các bài của mình:

VMCIRCLE:

Bài này chỉ cần vẽ tay rồi nháp một lúc sẽ ra

N = 3, dùng 1 màu.
4 <= N <= 6, dùng 2 màu.
7 <= N, dùng 3 màu.

Cách tô các bạn nên tự nghĩ.

VMCUT2:

Đầu tiên mình chưa nghĩ ra thuật nên mình code Simulated Annealing (50 điểm final tests). Mình nghĩ với N <= 50, SA sẽ luôn đưa ra lời giải đúng.

Sau đó mình sinh test và code một lời giả tham lam: Chặt nhị phân kết quả trong [trọng số lớn nhất ... tổng trọng số].

Với mỗi số X, tính số phép cắt cây ít nhất để được tất cả các cây đều có trọng số <= X.

Giả sử đang dfs đến nút u:

sumWeight[u] = tổng trọng số các nhánh con của u (các nhánh đã được tỉa để trọng số các cây con được duyệt trước đo <= X)

numTree[u] = số lần cắt các cây con nhận u là tổ tiên ít nhất để tất cả các cây được cắt ra có trọng số <= X.

curWeight = trọng số nút u + tổng các sumWeight[v] với v là con của u.

Trừ dần curWeight cho các sumWeight[v] lớn nhất cho đến khi curWeight <= X.

numTree[u] = Số lần trừ bỏ = số lần cut
sumWeight[u] = curWeight sau khi đã trừ bỏ

numTree[1] chính là số lần cắt tối thiểu
numTree[1] <= K thì tồn tại cách cắt không quá K lần để được các cây con có trọng số <= v.

Vì mình thấy code này và SA giống nhau với mọi N <= 40 nên chấp nhận là lời giải này đúng mà không cần chứng minh.

VMPACKAGE:

Đầu tiên mình cũng code một lời giải bitmask để tạo test.

Sau đó mình nghĩ ra lời giải

dp[src][len] là xác suất đi từ src được đường đi dài nhất <= len.

Ban đầu dp[i][j] = 1.0

Xét các v là con của src và prob_v là xác suất đường đi src - v không bị ngập

dp[src][len] *= (1 - prob_v + prob_v * dp[src][len - 1]

Hiểu là có 2 cách: hoặc là đường đi này không đi được hoặc nếu đi được, chỉ chọn các đường có đường đi dài nhất <= len - 1.

Từ đây suy ra xác suất để đi được đường đi đúng len từ src là dp[src][len] - dp[src][len - 1].

Kết quả bằng bào nhiêu thì mình nghĩ bạn nên tự nghĩ.

ĐPT O(N * N).

Để ăn được sub cuối thì ta để ý là chỉ cần sai số không quá 6 chữ số. Cách làm thì bạn nên tự nghĩ.

VMROPES:

1. Lời giải trâu bò và một số cài tiến

Giả sử ta có danh sách các số đẹp là S[1..len]

Gọi dp[N] là số cách nối để được dây có độ dài N.

Suy ra dp[N] = tổng các dp[N - S[i] | i = 1..len]

ĐPT (N - A) * số lần duyệt S[i]

Có một cải tiến dễ dàng là đổi cách tính

F[S[l]] +F[S[l + 1]] + ... + F[S[r]] = sumF[S[r]] - sumF[S[l] - 1]

với sumF[i] = F[0] + ... + F[i].

Tức là ta sẽ chuyển các đoạn liên tiếp về cặp [l - 1, r]

Thấy rằng K = 6, A = 1, B = 95000 sẽ có 4637 là số cặp lớn nhất và duyệt một số lần có break nên không phải luôn duyệt hết.

Thì thấy rằng tổng số lần duyệt sẽ không quá 2.4e8. Nếu cài quy hoạch động không mod và cài khéo sẽ lên 94 điểm.

Mình nghĩ nếu cải tiến dùng asm có thể sẽ ăn full.

2. Lời giải ăn full

3. Bài toán tổng quát:

Phần này là ngoài lề nhưng là phần mình đang tìm hiểu nên tiện chia sẻ và hỏi luôn.

Cho các số S[1..len] với 1 <= S[i] <= K. Ta xét hàm

F[x] = tổng các F[x - S[i]]

Tính F[N] % MOD

Hoặc tổng quát hơn nữa là bài này: https://www.codechef.com/MARCH15/problems/RNG

Mình dùng lời giải trên cho bài toán này nhưng TLE ngay khi K = 5e4, có lẽ do FFT code chưa tối ưu.

Nếu tồn tại đa thức này thì lời giải sẽ dễ dàng và tối ưu hơn dù ĐPT vẫn là O(K log K log N).

Mình thấy tests bài VMROPES nên được update lại. Mình chỉ duyệt trâu, thậm chí chưa dùng asm hay SSE để tăng tốc mà đã ăn full điểm. Hơn nữa bài này, theo ý kiến của mình, chỉ có ý nghĩa về mặt ý tưởng chứ thực sự thì không có ý nghĩa lắm về thực tiễn. Lời giải duyệt trâu với SSE buff chạy nhanh hơn code quy hoạch động chuẩn của mình tới 3 lần (so sánh max run time ở local tests, còn spoj là tổng thời gian chạy nên mình không so sánh được) và lời giải quy hoạch động mình không tìm được cách nào để tăng tốc dù đã chuyển sang botttom-up (nhanh hơn đệ quy có nhớ xấp xỉ 2.5 lần).

▲

▼

8 năm, 7 tháng trước

Trả lời theguiler
Hiện bài gốc

Mình thấy không đồng ý về câu "chỉ có ý nghĩa về mặt ý tưởng chứ thực sự thì không có ý nghĩa lắm về thực tiễn". Thế nào gọi là ý nghĩa về thực tiễn? Mình thấy ở đây bạn đã rút ra đc bài học là trong nhiều tình huống thực tế, duyệt và các kỹ thuật tối ưu tốt nhiều lúc còn đạt kết quả tốt hơn những thuật toán cao siêu. Cái này theo mình quan trọng hơn nhiều so với việc biết những thuật toán phức tạp kiểu Link cut tree hay suffix tree..

Ngoài ra thì mình thấy chỉ có mình bạn là "duyệt" mà ăn đc full bài này.

▲

▼

NhaDinhCao

8 năm, 7 tháng trước

Trả lời RR
Hiện bài gốc

▲

▼

laughing296

8 năm, 6 tháng trước

Trả lời theguiler
Hiện bài gốc

Cho em hỏi asm và SSE là những kĩ thuật gì vậy ạ

▲

▼