boleyn.su's blog

By boleyn.su, 6 years ago, , 376A - Lever

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

376B - I.O.U.

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}

375A - Divisible by Seven

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.

375B - Maximum Submatrix 2

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]}

375D - Tree and Queries

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]<=l[i]<=..<=l[i[k]]<=r[i[k]]<=r[i[k-1]]<=..<=r[i](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)).

375E - Red and Black Tree

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.

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]}

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. Tutorial of Codeforces Round #221 (Div. 1) Tutorial of Codeforces Round #221 (Div. 2) By boleyn.su, 6 years ago, , Hi, Codeforces Round #221 will take place on December 24th at 18:00 MSK for both divisions.

Problem setters are whd, oGhost and boleyn.su. This is our first Codeforces Round, and we hope it will be a good one.

We'd like to thank Gerald and alpc104 for helping us prepare this round, and MikeMirzayanov for bringing all of us a place to compete and communicate with others.

The score distribution will be announced before the contest starts.

UPD1: The score distribution is 500-1000-1500-2000-2500 for both divisions.

UPD2:

Congratulations to winnners and Merry Christmas to ones who celebrate it today!

Div 1:

2.al13n

3.rng_58

4.edly02

5.uwi

Div 2:

1.bohuss

2.Tyg3R

3.xhsong

5.Kira96 Announcement of Codeforces Round #221 (Div. 1) Announcement of Codeforces Round #221 (Div. 2) By boleyn.su, 6 years ago, , Minutes ago, I read a post by banana, and thought that there might be other codeforces users who have the same need. I used to write a tool to download all my solutions, and I'd like to share with others.

Too use the tool, you need to download 1) dlls which contains cURL and boost 2) exe (click the button "Raw" to download)

Then put the dlls and the exe in a folder, run downloader.exe and input your handle, and then all last accepted solution will be download to this folder.

Source code of this tool can be found here.

If you have any problems using this tool, leave a comment or send me a message.

UPD0: Python version by imslavko (Thanks to GFW(something bad for Chinese), this link cannot be accessed directly for Chinese users. But you can view it with the help of a proxy however.)

UPD1: I am sorry that there is no boost or libcurl on my new laptop, so I think I will no longer update this tool. However, you can DIY as the source code is provided. By boleyn.su, 6 years ago, , This problem is easy to solve using other languages with or without the help of segment tree.

But as I am learning Haskell, I tried to solve it with segment tree using Haskell. However, after a lot of tries, I found it impossible for me to solve it. So I need your help. I would be glad if you can point out any error in my submission or you can show me a Haskell solution (with the help of segment tree that support updating an interval) to this problem or let me know why it cannot be solved this way.

Thanks!

UPD1: My submission: here

UPD2: Another submission of mine (after reading Data.SegmentTree): here

UPD3: adamax's submission(Accepted. However, I think it doesn't take the advantage of Haskell.): here By boleyn.su, 7 years ago, , Description

I am working on my template for min cost max flow problems.

However after I implemented the most usually used Successive Shortest Path Algorithm, I found it hard to implement Cycle-canceling Algorithm(I got either a Runtime Error or a Wrong Answer Time Limit Exceeded). As far as I know, Successive Shortest Path Algorithm cannot handle the network with negative cycles, so I think it is important to learn Cycle-canceling Algorithm.

I knew someone solved this problem using Cycle-canceling Algorithm ( btw I can solve it without using Cycle-canceling Algorithm ) , while my implementation failed. I guess there must be some better implementations. So I googled its implementation, but found nothing.

I am asking for your help. Any material about it is great. Thanks!

References

Topcoder>Algorithm Tutorials>Minimum Cost Flow, Part 2: Algorithms

By boleyn.su, 7 years ago, ,  