Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
VO13 - day_1 - Thảo luận thuật toán (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 1
CHỦ ĐỀ - VO13 - day_1 - Thảo luận thuật toán
#69065
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
fire_from_hell viết:
QUOTE:
Bạn thử test này xem:
6 6 1 6
1 2 1
2 3 1
3 4 1
4 5 1
3 5 1
3 6 1

ra -1

-1 >D
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69066
blackstart (Thành viên)
blackstart+40
Không code nữa rồi
Bài viết: 362
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
fire_from_hell viết:
QUOTE:
Bạn thử test này xem:
6 6 1 6
1 2 1
2 3 1
3 4 1
4 5 1
3 5 1
3 6 1

ra -1

test này tối qua anh đưa cho nó chạy rồi
 
Đã lưu IP Đã lưu IP  
 
"Nothing is impossible; impossible itself says "I m possible"..."


Là Nam Nhi gõ phím bình thiên hạ...
Thân Anh Hùng click chuột định giang sơn...
  Đã khóa chức năng gửi bài.
#69067
vodanh9x (Thành viên)
vodanh9x+14
Nhắm mắt code không bug
Bài viết: 233
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
bài VOCARD: gọi sl[i] là số lượng số 1 trong dãy bit từ 1->i;
gọi f[i] là điểm số lớn nhất nhận được khi lấy các bit từ 1->i (lấy theo chiều từ i->1) và người lấy trước là người nhận được số điểm này.
thì f[i]=masum[i]-f[j]) vs j=i-1..i-k;
hay f[i]=sum[i]-min(f[j]) vs j=i-1..i-k;
ta có thể dùng stack để đpt còn O(N)
không biết có đúng không?
bài VOBOARD: gọi b[i] là số lượng lần nâng hàng i, c[i] là số lần nâng cột i
=> đk thỏa mãn là (b[i]+c[j]+a[i,j]) mod k = 0 vs mọi i=1..m,j=1..n;
lại thấy b[i],c[j]<K
từ đó for giá trị của b[1] (0->k-1) rồi tính các c[j],b[i] trong O(m+n) => đpt là K*(M+N) (70%)
bài VOCACTUS:
sub1: DFS bình thường tất cả các đường đi;
sub2: không có chu trình lẻ => có thể dijktra;
còn lại: vs mỗi đỉnh sẽ lưu lại các đỉnh kề vs nó trong các chu trình lẻ mà nó tham gia.
vì mỗi cạnh chỉ thuộc 1 chu trình => khi dijktra từ S mà đi vào 1 đỉnh thuộc 1 chu trình, thì đường đi tiếp theo sẽ từ đó đi các đỉnh còn lại của chu trình (Không thể từ đỉnh S đi đến 1 đỉnh khác thuộc chu trình đó mà không đi qua đỉnh kia);
gọi d[u,0] và d[u,1] tương ứng là đường đi ngắn nhất từ S->U vs số cạnh trên đường đi là số chẵn/lẻ;
khi lấy đỉnh u,t ra khỏi heap, xét các đỉnh v kề vs u;
nếu u và v cùng thuộc 1 chu trình lẻ thì ta phải kiểm tra xem có phải ta đang đi từ v->u->v hay không (dễ thấy nếu là đi từ v->u thì trạng thái chẵn lẻ của số cạnh của u,v là giống nhau)
=> ta cập nhật được u,t cho v,1-t khi mà d[v,t]>=d[u,t].
Từ đó ta dijktra + vs kiểm tra để xét cập nhật.
không biết có đúng không ạ???
 
Đã lưu IP Đã lưu IP  
 
Hahaha
  Đã khóa chức năng gửi bài.
#69068
blackstart (Thành viên)
blackstart+40
Không code nữa rồi
Bài viết: 362
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
vodanh9x viết:
QUOTE:

bài VOCACTUS:
sub1: DFS bình thường tất cả các đường đi;
sub2: không có chu trình lẻ => có thể dijktra;
còn lại: vs mỗi đỉnh sẽ lưu lại các đỉnh kề vs nó trong các chu trình lẻ mà nó tham gia.
vì mỗi cạnh chỉ thuộc 1 chu trình => khi dijktra từ S mà đi vào 1 đỉnh thuộc 1 chu trình, thì đường đi tiếp theo sẽ từ đó đi các đỉnh còn lại của chu trình (Không thể từ đỉnh S đi đến 1 đỉnh khác thuộc chu trình đó mà không đi qua đỉnh kia);
gọi d[u,0] và d[u,1] tương ứng là đường đi ngắn nhất từ S->U vs số cạnh trên đường đi là số chẵn/lẻ;
khi lấy đỉnh u,t ra khỏi heap, xét các đỉnh v kề vs u;
nếu u và v cùng thuộc 1 chu trình lẻ thì ta phải kiểm tra xem có phải ta đang đi từ v->u->v hay không (dễ thấy nếu là đi từ v->u thì trạng thái chẵn lẻ của số cạnh của u,v là giống nhau)
=> ta cập nhật được u,t cho v,1-t khi mà d[v,t]>=d[u,t].
Từ đó ta dijktra + vs kiểm tra để xét cập nhật. :)
không biết có đúng không ạ??? :S

mình cũng cài VOCACTUS với tư tưởng này
 
Đã lưu IP Đã lưu IP  
 
"Nothing is impossible; impossible itself says "I m possible"..."


Là Nam Nhi gõ phím bình thiên hạ...
Thân Anh Hùng click chuột định giang sơn...
  Đã khóa chức năng gửi bài.
#69069
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
alex_pythagore viết:
QUOTE:
R_R_ viết:
QUOTE:
Lời giải bài VOBOARD của rockman9x_94:
Mình copy nguyên từ đoạn chat của mình, nên nhiều chỗ hơi qua quýt :D

"Gọi a1, a2 .. là số bước biến đổi hàng i nhé
b1, b2 .. -> cột
bh xét a1
-> tính đc tất cả các a2, .., b1, b2..
và các giá trị này luôn thỏa mãn ?
-> update kết quả
bh giả sử a1++
-> b1--, b2--, b3--, ....
-> a2++, a3++, a4++, ..
Duyệt hết các giá trị có thể có của a1 (có O(MN) giá trị), mỗi giá trị của a1 thì tính kq trong O(1)."


Các giá trị cộng/trừ trong mod K.
Vấn đề ở đây là lấy giá trị trong O(1). :)


Hôm qua lúc ý đang mải thảo luận "những vấn đề quan trọng", nên anh cũng chẳng có thời gian nghĩ lắm

Cái đoạn + - chỉ cần quan tâm đến các event chuyển giữa K-1 với 0, anh đoán là nó có cách gì đấy để quản lý mấy cái event đấy
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69070
phamanhtu (Thành viên)
phamanhtu1996-
Biết code binary-indexed tree
Bài viết: 20
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
Bài VOBOARD mình làm như sau không biết đúng hay sai.
- Ta có thể biến đổi hàng xong sau mới biến đổi cột.
- Do đó nếu biến đổi hàng 1 về cùng một giá trị thì các hàng khác cũng sẽ về cùng 1 giá trị (do luôn có kết quả).
- Cho nên ta sẽ biến đổi hàng 1 về 1 trong các giá trị ở hàng 1 ban đầu. Gọi giá trị đó là ai.
- Gọi c[i] là số lần biến đổi cột i. r[i] là số lần biến đổi hàng i.
- Có c[1] thì ta sẽ biến đổi cột 1. Từ đó ta suy ra các r[i]. Cập nhật kết quả để tìm cái nhỏ nhất.
ĐPT O(MN).
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69072
yoh (Thành viên)
rockman9x_94+19
Đã code là AC
Bài viết: 95
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+2)
alex_pythagore viết:
QUOTE:
R_R_ viết:
QUOTE:
Lời giải bài VOBOARD của rockman9x_94:
Mình copy nguyên từ đoạn chat của mình, nên nhiều chỗ hơi qua quýt :D

"Gọi a1, a2 .. là số bước biến đổi hàng i nhé
b1, b2 .. -> cột
bh xét a1
-> tính đc tất cả các a2, .., b1, b2..
và các giá trị này luôn thỏa mãn ?
-> update kết quả
bh giả sử a1++
-> b1--, b2--, b3--, ....
-> a2++, a3++, a4++, ..
Duyệt hết các giá trị có thể có của a1 (có O(MN) giá trị), mỗi giá trị của a1 thì tính kq trong O(1)."


Các giá trị cộng/trừ trong mod K.
Vấn đề ở đây là lấy giá trị trong O(1). :)


chỉ quan tâm đến các thời điểm khi các b1, b2, .. bị giảm về -1 -> cho nó lên k-1 và khi các a2, a3, .. tăng lên k -> cho nó về 0. Đó, tính trc các thời điểm này, đi lần lượt theo thứ tự và cập nhật kết quả ?
 
Đã lưu IP Đã lưu IP  
 
Sống chậm lại, nghĩ khác đi và yêu thương nhiều hơn
We r friend!
  Đã khóa chức năng gửi bài.
#69074
alex_pythagore (Thành viên)
alex_pythagore+38
Super fast coder
Bài viết: 51
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
phamanhtu viết:
QUOTE:
Bài VOBOARD mình làm như sau không biết đúng hay sai.
- Ta có thể biến đổi hàng xong sau mới biến đổi cột.
- Do đó nếu biến đổi hàng 1 về cùng một giá trị thì các hàng khác cũng sẽ về cùng 1 giá trị (do luôn có kết quả).
- Cho nên ta sẽ biến đổi hàng 1 về 1 trong các giá trị ở hàng 1 ban đầu. Gọi giá trị đó là ai.
- Gọi c[i] là số lần biến đổi cột i. r[i] là số lần biến đổi hàng i.
- Có c[1] thì ta sẽ biến đổi cột 1. Từ đó ta suy ra các r[i]. Cập nhật kết quả để tìm cái nhỏ nhất.
ĐPT O(MN).


Bạn mặc định sẽ có ít nhất một biến đổi cột bằng 0.
Thuật tóan trên ra sai khi trong lời giải tối ưu, tất cả các biến đổi cột đều lớn hơn 0.

@rockman: uh, vậy thì trung bình là ra O(1). Lúc đầu cứ tửong tính thẳng ra dc .
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69075
khanhsuphu12 (Thành viên)
ngockhanh+1
Biết code binary-indexed tree
Bài viết: 23
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
Bài VOCACTUS mình dùng dijkstra để tìm đường đi vs time ngắn nhất từ s -> t. Nếu số đỉnh là lẻ -> exit và writefile. Nếu ko có đường đi thì exit -> -1. Nếu số đỉnh là chẵn thì loại bỏ từng đường đi trong đường đi ấy và tìm đường đi ngắn nhất từ s->t (lại kiểm tra nhưng những bước đã nói ở trên)
Và nếu không tìm được bằng các biện pháp trên thì exit -1
input
6 6 1 6
1 2 1
2 3 1
3 4 1
4 5 1
3 5 1
3 6 1

output
-1
 
Đã lưu IP Đã lưu IP  
 
Code For FOOD
  Đã khóa chức năng gửi bài.
#69129
LNTF (Thành viên)
lntf
Đang tập code
Bài viết: 4
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
-f[i]=min(sum[j-1]-f[j-1]+sum[i]-sum[j-1]);j=i-k+1..i-1;
công thức sao + rồi - sum[j-1] thế
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS