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
[VM08] 9th round - Solution (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - [VM08] 9th round - Solution
#4704
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
[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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4718
gerrob (Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4732
supo (Thành viên)
Đã biết code đệ quy
Bài viết: 11
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4765
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4815
supo (Thành viên)
Đã biết code đệ quy
Bài viết: 11
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4936
TripleM (Thành viên)
Đã biết code đệ quy
Bài viết: 8
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4937
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4938
TripleM (Thành viên)
Đã biết code đệ quy
Bài viết: 8
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4939
TripleM (Thành viên)
Đã biết code đệ quy
Bài viết: 8
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#4940
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] 9th round - Solution 12 năm, 5 tháng trước   (+0)
Our implementation O(N^3) got accepted within the time limit. I think maybe the constant of your algorithm is larger so it is slower.
Here is a link to our implementation:
https://vn.spoj.pl/status/LSFIGHT,voj/
Here is the code in Pascal:
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.
 
Đã 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
  • Trang:
  • << < 1 2 > >>
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