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] 11th 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
CHỦ ĐỀ - [VM08] 11th round - Solution
#5637
HieuNM (Admin)
hard7771988+9
Admin
Bài viết: 137
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
[VM08] 11th round - Solution 12 năm, 4 tháng trước   (+0)
FLOWER
Number the blocks 1, 2, ..., N from top to bottom. Number the petals 1, 2, 3, ..., N in clockwise order. Petal N is beside petal 1.
Let:
Pos[i][j] = the index of the jth lowest block of color i.
D[i][j] = the minimum number of baskets need to arrange the petals i, i+1, i+2, ..., j.
(If i >j, the petals are i, i+1, i+2, ..., N, 1, .., j. However we only consider the case i <= j below. It is similar for i > j).
Suppose to arrange these petals we need X1 blocks of color 1, X2 blocks of color 2, ..., Xk blocks of color k.
Then it is easily to observe that we need to take down blocks 1, 2, .. max ( Pos[z][ Xz ] | 1 ≤ z ≤ k ) from the tower.
Let Need[i][j] = max ( Pos[z][ Xz ] | 1 ≤ z ≤ k ) .
We have the following formula:
D[i][j] = max ( Need[i][j] – (j-i+1), min( D[i+1][j], D[i][j-1] ) ) (*)
Our answer is min( D[1][N], D[2][1], D[3][2], ... D[N][N-1] ).
We can calculate Pos[i][j] in O(N^2). To calculate Need[i][j] we use Need[i][j-1] or Need[i+1][j], so we also need O(N^2) time. D[i][j] are also found in O(N^2). Thus our algorithm complexity is O(N^2).

Proof of formula (*):

We observe that after arranging the petals i, i+1, i+2, ..., j, the number of blocks in baskets is Need[i][j] - (j-i+1). It is because we've taken down Need[i][j] blocks but only used j - i +1 blocks. So the number of unused blocks (or blocks in baskets) is Need[i][j] - (j - i +1).
=> D[i][j] ≥ Need[i][j] – (j – i +1).
Case 1: We arrange petals i+1, i+2, ..., j before petal i
Suppose petal i is of color t.
a) If Need[i+1][j] > Pos[t][Xt] -> number of baskets needed is D[i+1][j]
It is because to arrange petals i+1 -> j we need to take down Need[i+1][j] top blocks. Among them there is enough Xt blocks of color t. So after arranging petals i+1 -> j, there exists a basket containing block of color t. We only need to put this block in to position i of the flower. Therefore the number of baskets needed is D[i+1][j].
b) If Need[i+1][j] < Pos[t][Xt] -> number of basket needed is max (D[i+1][j], Need[i][j] - (j-i+1)).

It is because after arranging petals i+1 -> j we do not have enough Xt blocks of color t but only Xt-1 blocks. So we need to continue to take down the blocks until there is enough Xt blocks of color t. The number of baskets now is the number of remaining baskets after arranging petals i+1 -> j plus the number of additionally taken down baskets. This is Need[i][j] - (j+i-1). Thus the number of baskets needed is max ( D[i+1][j], Need[i][j] – (j-i+1) ) .

Case 2: We arrange petals i, i+1, ..., j-1 before petal j.

Proof is similar to case 1.

Conclusion: D[i][j] = max ( Need[i][j] – (j-i+1), min( D[i+1][j], D[i][j-1]))



ANT

Idea: if an ant does not have to go out of the circle then we move it into the bottom of the list.
For example, if N=10, M=3:
1 2 3 4 5 6 7 8 9 10
Move ants 1, 2 into the bottom of the list. Ant 3 has to be removed:
4 5 6 7 8 9 10 11 12
Move ant 4 into the bottom of the list:
5 6 7 8 9 10 11 12 13
And so on.
We have the following observations:
- Ants in positions Mk will be removed
- Ant in position Mk+q will be move into position n + (M-1)k + q
- The lucky ant is at position MN when the game ends.
So we obtain the following algorithm:
- We start from the last position of the lucky Ant: P <- MN
- Then trace back to find the previous position of this ant, until it is in the interval [1, N].
To find the previous position of the lucky ant:
At each step, we have: P = n + (M-1)k + q for 1 <= q < M
=> P – n – 1 = (M-1)k + q – 1, for 0<=q-1<M-1
Or (q-1) is the remainder when dividing (P-n-1) by (M-1)
=> k = (P - n - 1) / (M - 1)
=> Previous position: Mk + q = P + k - n = P + (P - n - 1) / (M-1) - n
Complexity: O(M log N)
 
Đã 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