# summary-contests

## Codeforces

### Round #327 (Div 1) [5/5]

during I coded in the virtual contest, the server of codeforces had some mistakes. I just submitted the code by vjudge. (My contest score is '0', f**k!)

#### DONE T1 (-2) (#) (X)   special

I didn't think out all situations.

I just get ans from this situation like this: "…1101011…". but I missed a similar one, such as "…110100…" with two '1' at front and two '0' at rear. This is my failure.

I didn't think binary search was OK in the beginning… Because of $vmax ^ 2 >= vx ^ 2 + vy ^ 2$ (the same as $wx, wy), the man can stay at any position he reaches. Just binary search. binary search time and work out the new position of the man. But if your eps is '1e-9' and even smaller when doing binary search, the problem won't stop. eps is too small. #### DONE T3 (-2) (#) (X) graph dfs I didn't think out all situations, again! There isn't only one way to build the road. I didn't think out this way: build three roads from a node '.' to three states. It means we can go to any state from the node, and it's the same the other way round. Sometimes this scheme is the best. #### DONE T4 (-2) (*) (X) knapsack In the beginning, I didn't realize that we could make the first k numbers become any situation with the operator n2 times at most. If we know this, this problem can be solved prefectly by knapsack. If we need to get a maximim scheme, initing all the DP val as '-oo' is useful, at least in this problem. "Think twice, Code once." –by Matthew99 #### DONE T5 (-2) (*) AC_trie bipartite_graph DAG 最长反链 Change the problem to a DAG problem. if s(v) is a substring of s(u), then AddEdge(u –> v). This subtask can solved with AC-trie. Then we get a DAG. We should choose nodes as more as possible which cannot reach to any of others. This is a problem about 最长反链. Solve this with bipartite graph. ### Round #319 (Div 1) [5/5] Some interesting problems. #### DONE T1 (-0) (#) math prime A easy math problem. For any prime p, query$ p ^ 1, p ^ 2, p ^ 3, … p ^ k $, until$ p ^ {k + 1} > n $. This is best way. If we query$ p1 ^ k1 * p2 ^ k2 $, some numbers can make this scheme worse than the above one. #### DONE T2 (-2) (#) permutation A problem about permutation. Attention p[] is a permutation. for two circulation (1 2 3) (4 5), if we add a edge 1 –> 4, then there must be these edges: { 1 –> 4, 2 –> 5, 3 –> 4, 1 –> 5, 2 –> 4, 3 –> 5 } But then there are circle in the graph. this is due to the size of the two circulation.' Think carefully, and you will get the right way. #### DONE T3 (-2) (*) block I was so stupid… Like 莫队. If the size of block is$ S $, then the count is:$ n * S + 2 * n / S $. We can find the best$ S $and then solve the problem by sort. #### DONE T4 (-2) (*) matrix floyd The biggest problem is when these edges are available. One way is using matrix. Using matrix to know that after passing$ d $edges, which nodes node$ 1 $can reach. Then for those nodes, they can use the edges whose val is lower than$ d $. #### DONE T5 (-?) (*) If you divide and conquer with DSU, the main problem is that we don't know if the edge is changed successfully, and it will influence other edge. So we should add edge to the node dynamically in the segment-tree. If you use LCT, there will be many details. For unicom nodes, if the size is$ N $, we only keep$ N - 1 $edges in LCT. But which edges should be keeped? Just like humdrum queue. ### Round #313 (Div 1) [5/5] #### DONE T1 (#) (0) A easy problem about area. the answer is the area of the big triangle minus the area of three small triangles. #### DONE T2 (#) (-1) string A problem about the conversion of string. But in the beginning, I write a BF whose time complexity is T(n) = 4T(n / 2) + O(n) = O(n ^ 2), and n is at most 1e5… I heard that someone got AC with this wrong algorithm! None hack him? With this conversion, a string can be changed into many kinds of new strings; and this new strings can also be changed into the origin string. If string A can be changed into string B, then output "YES", otherwise output "NO". This means that if A can change to a string S, then A can also change to B, otherwise the answer is "NO". We make S the minimum (字典序最小) string which A can change to, and S0 for B. If S0 == S, then the answer is "YES", otherwise the answer is "NO". #### DONE T3 (#) (-1) count a counting problem. But in the first submission the array size is a little small, then I get RE … Let DP(i) be the count of the schemes to walk from (0, 0) to (h, w), which is the position of point i. If some point j, whose position is (h0, w0) (h0 < h & w0 < w), cannot be reached, then decrease the contribution of this point. In the beginning, DP(i) is the count of the schemes to walk from (0, 0) to (h, w), ignoring the point cannot be reached. DP(i) -= DP(j) * (the count of the schemes to walk from (h0, w0) to (h, w), ignoring the point cannot be reached). If you want to know the prove, http://codeforces.com/blog/entry/19237. #### DONE T4 (*) (?) Let think a O(n ^ 2) algorithm first. Enumerate i and j, calculate how many points won't be in the new polygon when the edge (i –> j) is in it. We need to use Pick's theorem. Attention, if i + 1 == j, the theorem cannot be used normally. it needs special judging. This one is very important. Then just cal the probability of the edge appearing. the point From i + 1 to j - 1 cannot appear and point i, j must appear. Only one scheme is OK. At least one of the point from j + 1 to i - 1 needs to appear. Only one scheme is not OK, let it be$ sumi, j $. Then$ sumi, j / cntofallschemes $is the probability. But if there are many points between point i and j in the origin polygon, the probability is very small. If the count of the point between them is$ cnt $, the probability is smaller than 2 ^ -(cnt). when cnt is bigger than 60, it is very small for 1e-9 — the reqire of this problem. So just Enumerate i and j, j is from (i + 1) % n to (i + n - 1) % n. when j == (i + 60) % n, stop and enumerate a new i. #### DONE T5 (*) (-5) A problem about DP.$ ai $is too large. Discrete! If let$ DPi $means at the left of$ DPi $, how long the path is at most, and use every spotlight to update the value, we will found that there will be a problem like this: if the i th spotlight update$ DPs $with $$DP_{s - 1}$$, and the i + 1 th update$ DPs - 1 $($$DP_{s - 1}$$ become larger), we know that $$DP_{s}$$ may be able to be updated by $$DP_{s - 1}$$ with the i th. But i + 1 > i, so we won't enumerate i again! So, we should use a new dp status. Let$ dp(R, i) \$ means the length of the longest path with the spotlights numbered 1, 2, 3, … , n, and the scheme should light position i.

But how to update the status? Think by yourself.

With more, http://fuboat.leanote.com/problem-CF-559-E.

## Atcoder

### <2016-12-10> arc065 [4/4]

#### DONE E Manhattan Compass

##### 题目大意

1. 如果点对 (a, b) 合法, 则点对 (b, a) 合法.
2. 如果点对 (a, b) 合法且另一个点对(b, c) 满足 d(a,b) = d(b,c), 则点对 (b, c) 合法.

### <2016-01-22> agc009 [2/3]

n <= 100000.

#### TODO B Tournament

$$n \leq 10^5$$

(明明是道水题)

#### DONE C Division into Two

(我代码里是反过来的, 即 $$f(i)$$ 表示第 i 个数在 $$Y$$ 集合中的方案数)

HOME