Mất mật khẩu? | Đăng ký Nhập các thuật ngữ tìm kiếm của bạn Web VNOI Nộp mẫu đơn tìm kiếm

### Đ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
[VM08] 9th round - Solution (1 đang xem) ,(1) Khách
 Được ưa thích: 0 Trang: << < 1 2 > >>
CHỦ ĐỀ - [VM08] 9th round - Solution
#4704
paulmcvn+71
Bài viết: 1288

 [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) RECT3 Dynamic programming O(N^3): Let s1[i][j][k] be the maximum area of a rectangle containing all 1s which has the column from j to k in row i as the bottom side. We can calculate s1[i][j][k] based on s1[i-1][j][k]. Let s2[i][j][k] be the maxmimum area of a shape consiting of the top rectangle and a part of the middle rectangle, so that the column from j to k in row i is the bottom side of the shape. We can calculate s2[i][j][k] based on s2[i-1][j][k] and s1[i-1][j'][k'] for j' > j and k' < k (we need to use dynamic programming again with complexity O(N^2) at this step). s1 and s2 should be calculated from top to bottom. Let s3, s4 have the same meanings with s1, s2 but now we consider reversely from the last row up to the first row. Our result is Max (s2[i][j][k]+s4[i][j][k]-(k-j+1)) (since k-j+1 is calculated twice in s2[i][j][k] and s4[i][j][k]). LSFIGHT Dynamic programming Let F(i, j)=true iff there exists a case so that the competitors between i and j are all eliminated (in clockwise order). F(i, j) = true iff there exists k between i and j (in a circle) so that F(i, k) = F(k, j) = true and k will lose over i or k will lose over j. Now we can easily obtain the answer. Complexity: O(n^3).

Đã lưu IP
Đã khóa chức năng gửi bài.
#4718
(Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) I've done LSFIGHT by simulation. By interval tree it is possible to simulate one whole tournament in O(N*log(N)) time. It can be speed up if we aren't restart the game after each tournament (say we simulate C tournaments using the last D people from one game, I've used C=2*sqrt(N), D=sqrt(N+1)). Obvoiusly I've exited from the simulation after 0.45 sec. to avoid TLE. This resulted 88 points for me. It seems that others also simulated the game, there are lots of 84-88-92 points on the list.

Đã lưu IP
Đã khóa chức năng gửi bài.
#4732
(Thành viên)
Đã biết code đệ quy
Bài viết: 11

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) I've got 92 for LSFIGHT and I did not simulate. I used the same O(n^3) solution but due to high constraints I suffered from TLE probably. Anyway I was disappointed after seeing the LSFIGHT problem, because it was not original. Check this: http://www.spoj.pl/problems/MUSKET/ I also think that judges solution for RECT3 is a bit overkill, I got away with O(N^4) time and O(N^2) memory for 100 points and also it seems much simpler. It is not even DP, just modification of "largest rectangle in histogram" problem, that is generally known. I think my algorithm can be pushed to O(N^3 log N) if someone would try really hard, but I do not think that it is necessary, as even O(N^4) runs quite quickly on every input I tried.

Đã lưu IP
Đã khóa chức năng gửi bài.
#4765
paulmcvn+71
Bài viết: 1288

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) supo viết: QUOTE: Anyway I was disappointed after seeing the LSFIGHT problem, because it was not original. Check this: http://www.spoj.pl/problems/MUSKET/ Sorry, it is an unintended mistake! The problem setter remembered the problem from his teacher and did not realize the problem is from Polish Olympiad. We've added the problem source. The test cases for RECT3 is a bit weak. Our intended solution is O(N^3).

Đã lưu IP
Đã khóa chức năng gửi bài.
#4815
(Thành viên)
Đã biết code đệ quy
Bài viết: 11

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) Now that you gave the credits to the original source, that thing is settled. About the RECT3,yeah it can be that, though I really tried hard to find a matrix where my solution really performs like N^4 one. I could not find such matrix, but of course that is no proof

Đã lưu IP
Đã khóa chức năng gửi bài.
#4936
(Thành viên)
Đã biết code đệ quy
Bài viết: 8

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) My code for LSFIGHT uses O(n^3), produces the correct output on all test cases and takes 1.094 seconds to run on my slow computer in the worst case.. what sort of crazy time limits did you set on this?

Đã lưu IP
Đã khóa chức năng gửi bài.
#4937
paulmcvn+71
Bài viết: 1288

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) Hey TripleM, on SPOJ you got TLE for 4 test cases, in which your program ran test 24 for more than 5s. Please note that SPOJ machine may be slow than your computer. I think if you ran 500^3 in 1.094s then your computer must be super fast.

Đã lưu IP
Đã khóa chức năng gửi bài.
#4938
(Thành viên)
Đã biết code đệ quy
Bài viết: 8

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) Hm, so 1s for 500x500 is considered superfast but solving it in less than 3 seconds is expected? If O(n^3) is too slow, why is the official solution O(n^3)?

Đã lưu IP
Đã khóa chức năng gửi bài.
#4939
(Thành viên)
Đã biết code đệ quy
Bài viết: 8

 Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước (+0) (I guess thats the reason why gerrob's simulation solution is much better than the real solution! The time limit in my opinion is far too strict for your official solution to be expected).

Đã lưu IP
Đã khóa chức năng gửi bài.
#4940
paulmcvn+71
 Code: ```  const f_inp = ''; f_out = ''; nmax = 500; var a, f: array[1..nmax+1, 1..nmax] of boolean; n, m: longint;   procedure ReadInput; var i, j, t: longint; begin assign(input, f_inp); reset(input); readln(n); for i := 1 to n do for j := 1 to n do begin read(t); a[i, j] := t = 1; end; close(input); end;   procedure Solve; var i, j, t, k, l: longint; begin fillchar(f, sizeof(f), 0); for i := 1 to n do begin f[1, i] := true; f[2, i] := true; end; for t := 3 to n+1 do for i := 1 to n do begin j := (i + t - 2) mod n + 1; for k := 1 to t - 2 do begin l := (i + k - 1) mod n + 1; if f[k + 1, i] and f[t - k, l] and (a[i, l] or a[j, l]) then begin f[t, i] := true; break; end; end; end;   m := 0; for i := 1 to n do if f[n + 1, i] then inc(m); end;   procedure WriteOutput; var i: longint; begin assign(output, f_out); rewrite(output); writeln(m); for i := 1 to n do if f[n + 1, i] then writeln(i); close(output); end;   BEGIN ReadInput; Solve; WriteOutput; END.```