writer: boleyn.su
O(n):
Let mid = position of ^
Let value(x) = x if x is a digit , 0 otherwise.
Let sum = value(i-th char)*(i-mid)
If sum = 0 then answer = balance
Else if sum<0 then answer = left
Else answer = right
writer: oGhost
O(n^4):
Let f[i][j] = how many money i owes j
#It can be proved we only need to loop n times.
Loop n times do:
For i,j,k in [1..n]
If f[i][j]>0 and f[j][k]>0 then
Let delta = min (f[i][j], f[j][k])
Decrease f[i][j] and f[j][k] by delta
Increase f[i][k] by delta
Answer will be sum{f[i][j]}
O(m+n):
Let owe[i] = 0 for all i
#Suppose there is an agnecy to help people with debts.
#If you owe someone, you give money to the agency.
#If someone owes you, you get money from the agency.
For each ai, bi, ci
Increase owe[ai] by ci
Decrease owe[bi] by ci
Ansewr will be sum{owe[i]|owe[i]>0}
writer: oGhost
O(n):
Because permutation of 1, 6, 8, 9 can form integers that mod 7 equals 0, 1, 2, 3, 4, 5, 6.
So you can construct answer like this: nonzero digits + a permutation of 1, 6, 8, 9 + zeros.
writer: oGhost
O(n*m):
#We can get right[i][j] by O(n*m) dp.
Let right[i][j] = how many continuous 1s is on cell (j, i)'s right.
Let answer = 0
For all column i
Sort right[i] #You can use O(n) sorting algorithm
For j in [1..n]
If right[i][j]*(n-j+1) > answer then answer = right[i][j]*(n-j+1)
375C - Circling Round Treasures
writer: whd
#T = number of treasures, B = number of booms
O(n*m*2^(T+B)):
#State(i, j, ts, bs) means:
# 1. You are at cell (i, j)
# 2. If the i-th bit of ts is 0 i-th treasure cross even edges of current path, otherwise odd edges.
# 3. If the i-th bit of bs is 0 i-th boom cross even edges of current path, otherwise odd edges.
Let dis[i][j][ts][bs] = min step to go to reach state (i, j, ts, bs).
Then we can use bfs algorithm to calculate dis.
The answer will be max{value(ts) — dis[Si][Sj][ts][0]}
writer: whd
O(nlogn) or O(nlog^2n):
Use binary search tree and merge them by rank.
Use binary search tree that supports O(n) merging to get O(nlogn) solution.
O(n*sqrt(n)):
Dfs the tree to transform the problem to:
Given a[i], query [l,r] k.
To solve this problem:
Build sqrt(n) bucket, put query [l,r] into (l/sqrt(n)+1)-th bucket
For each bucket
For thoese queries whose r is also in the bucket (l/sqrt(n) equals r/sqrt(n)), a brute-froce O(n) solution exists.
For thoes queries whose r is not in the same bucket, let we sort them by l. We will get l[i[1]]<=l[i[2]]<=..<=l[i[k]]<=r[i[k]]<=r[i[k-1]]<=..<=r[i[1]](do not forget we get l[] and r[] by dfs the tree!). Solving them can be done in O(n) too.
Since we only have O(sqrt(n)) buckets, the total time is O(n*sqrt(n)).
writer: boleyn.su
This problem can be solved by integer programming:
min sum{c[i]*x[i]}
subject to
sum{A[i][j]*x[j]} >= 1 for all i
sum{x[i]} = R
x[i] = 0 or 1 for all i
where
c[i] = 1 if node i is black, 0 otherwise
A[i][j] = 1 if distance between i and j is no greater than X, 0 otherwise
R = number of red nodes.
As it is known, integer programming is NP-hard.
Thus, this cannot be the solution.
But we can prove the following linear programing's solution is same as the integer programming's.
min sum{c[i]*x[i]}
subject to
sum{A[i][j]*x[j]} >= 1 for all i
sum{x[i]} <= R
x[i] >= 0 for all i
where
c[i] = 1 if node i is black, 0 otherwise
A[i][j] = 1 if distance between i and j is no greater than X, 0 otherwise
R = number of red nodes.
And the known fastest algorithm to solve linear programming is O(n^3.5).
But in fact due to the property of this problem, using simplex algorithm to solve linear programming is even faster. I think it can be O(n^3), but I have no proof.
So just use simplex to solve the linear programming problem above.
The tutorial is not finished yet. More details will be added later.
UPD
Thanks to Codeforces users, a lot of details supposed to be added can be found in comments. I am adding something that is not clearly explained in the comments or something that I want to share with you.
Div1C:
There are few questions about this one. So I am explaining it more clearly.
#State(i, j, ts, bs) means:
# 1. You are at cell (i, j)
# 2. If the i-th bit of ts is 0 i-th treasure cross even edges of current path, otherwise odd edges.
# 3. If the i-th bit of bs is 0 i-th boom cross even edges of current path, otherwise odd edges.
Let dis[i][j][ts][bs] = min step to go to reach state (i, j, ts, bs).
Then we can use bfs algorithm to calculate dis.
About the bfs algorithm:
We know dis[Si][Sj][0][0] = 0.
For state(i, j, bs, ts) we can goto cell (i-1, j), (i+1, j), (i, j-1) and (i, j+1). Of course, we cannot go out of the map or go into a trap. So suppose we go from cell (i, j) to cell (ni, nj) and the new state is (ni, nj, nts, nbs). We can see if a treasure is crossing through the edge (i, j) - (ni, nj), if i-th treasure is, then the i-th bit of nts will be 1 xor i-th bit of ts, otherwise, the i-th bit of nts and ts will be same. The same for nbs.
We can reach state (ni, nj, nts, nbs) from (i, j, ts, bs) in one step, so we just need to start bfs from state(Si, Sj, 0, 0) to get the min dis of all state.
The answer will be max{value(ts) — dis[Si][Sj][ts][0]}
My submission: 5550863
Div1D:
To our surprise, there seems to be many different solutions to Div1D, which is very good. In fact, we thought about changing this problem so that only online algorithm will be accepted, but we didn't have much time to change it. I guess if we only accept online algorithm, the problem will be less interesting becasue we might not have so many different solutions. So, not changing it is a good decision.
However, it may(some solution is hard to change to solve the online-version, so I use 'may') be quite simple to solve the online-version of this problem if you have solved the offline-version. You just need to use persistent data structure when implementing binary search trees. You can get more detail from wiki.
Div1E:
The meaning of the integer programming:
We use x[i] to stand whether node i is red or not. So we have:
x[i] = 0 or 1 for all i
There is a beautiful tree, for each node, exists an red node whose distance to this node is no more than X. So we have:
sum{A[i][j]*x[j]} >= 1 for all i
There are only R red node. So we have:
sum{x[i]} = R
And we need to minimize the swap number, and in fact the swap number equals to number of nodes that changed from black to red. So we need to minimize:
sum{c[i]*x[i]}
After changing it to linear programming:
Firstly, it is obvious that the solution of the linear programming will not be worse than integer programming, because integer programming has stronger constraint.
So we only need to show the solution of the linear programming will not be better than integer programming.
To prove this, we need to show for an optimal solution, there will be an solution which is as good as it and all x[i] is either 0 or 1.
1. Because for "sum{A[i][j]*x[j]} >= 1 for all i", there is no need to make some x[i] > 1. It is obvious that if the solution has some x[i] > 1, we can increase x[i] for nodes that are red in the first place, so that there will not be any x[i] > 1 and this solution is as good as the old one.
2. We need to prove in an optimal solution, making some x[i] not being an integer will not get btter solution. It is really hard to decribe it. So just leave you a hint: use the property of trees to prove and consider leaves of the tree.
My submission: 5523033
There is a nice DP solution too, check this submission 5516578 by Touma_Kazusa.
