Problem - D - Codeforces When there are functions, try to find the monotonic property. Both max function and mix function have monotonic property, for the former is non-decreasing and the latter is non-increasing. We are interested of the …

Problem - C - Codeforces If the first person took a, then the one who took most would have taken a * k^3. The restriction is essentially a * k^3 ≤ n, k > 1, a ≥ 1 If n is fixed, the count of valid ( a, k ) will be And since we want to sear…

Problem - B - Codeforces Well, it's easy. But not what I had expected for pB in division 2. And since the transition cost is constant, bfs = queue was enough, and priority_queue was kind of overkill. void solve(){ int N; cin >> N; vi A( N …

Problem - A - Codeforces Trickiest problem in division 2 ever. There were many different solutions, mine is a little easier than most of them. Consider with 0 and without 0. If there is no 0, it is essentially asking whether there are at l…

Problem - D - Codeforces We will try DP, but realize that merely with left and right bound parameter is insufficient for determining an answer, because if the leftmost tree is falling to the left, we need to know the direction of the falle…

Problem - C - Codeforces The W array given in the input serves for constraining which points can be in those positions. For any ( x, y ), its special value is y - x, and it could only be in a position i, where W[ i ] == y - x. This means, …

Problem - E - Codeforces It's instinctive to come up with timestamp and segment tree. Initially I thought it would be fine with sets to maintain the set of colours, but now it seems like it wouldn't work. Maybe it's because my segment tree…

Problem - D - Codeforces We can simply brute force for 0 and 1 swap, so let's think about 2 swaps. When 2 swaps are committed, and given that asum is the sum for all elements in a, same for bsum, swapping ( i, j ) in A with ( x, y ) in B, …

Problem - D - Codeforces 構造題。 題目給N個點和其各自的父親，若父親為自己就是根。求改變最少的父親使成為一棵樹。 首先想到根只有一個，且如果原本就有根存在（自己的父親是自己），那麼就選它做根。 而如果天生有多數這樣的根，其他根就必須重新導向被…

Problem - D - Codeforces 經典的 XOR Trie，沒什麼好說的。 這次的題目都好簡單，要不是那天有SAT模考就能大賺一波rating了... struct Trie{ Trie *ch[ 2 ]; int cnt; Trie(){ ch[ 0 ] = ch[ 1 ] = NULL; cnt = 0; } void add( int v, int k ){ if( k < 0 )…

Problem - C - Codeforces 很簡單的DP。 dp[ i ][ j ] : minimum cost for already determined i strings, last string reversed ( or not -> j = 0 ) bool ok( string s1, string s2 ){ return s1 <= s2; } void solve(){ int N; cin >> N; vi C( N ); for(…

UVa Online Judge 能練習稀疏表的題目。主要就是把相同的數字都當成塊處理，完整的塊一併用RMQ處理，左右的則是個別判斷。要預處理的表有 blk_idx[ x ] : index among blocks of value x blk_val[ idx ] : value idx'th block holds blk_left_bound[ idx ] :…

UVa Online Judge For each candidate of umpire, the number of matches that can be held is n( contestants in left ) with value lower than umpire's value * n( contestants in right ) with value higher + n( contestants in left ) with value high…

UVa Online Judge Make the disjoint set remember the distance from each node to its direct father. Whenever path compression is in progress, the cost should be updated as well. struct UnionFind{ vector< int > fa, cost; UnionFind( int sz ){ …

UVa Online Judge Formally put, it is that given many edges through input, only connect the ones that do not form cycle, and otherwise count it in the answer. Checking whether a new edge will cause a cycle be formed can be managed by union …

UVa Online Judge First I thought I could simply make a structure to record where each index of the arrays are, and expand them in priority queue, however, did not work out because for example when ( 0, 1 ) and ( 1, 0 ) are both visited, ( …

Problem - C - Codeforces Use set to manage all unread notifications, with amortized complexity, we know that it will be alright because each element will only be inserted and deleted at most once. And actually set was not needed. void solv…

Problem - E - Codeforces Consider rooting the tree with 1 as root. DFS down, and observe each edge, the number of towns that are below the edge, and above the edge ( 2 * K - below_edge_cnt ). We will know that the maximum number of pairs s…

Problem - D - Codeforces 本番中 "reversal of the bus, take place immediately and this time can be neglected" を「バスの移動は時間がかからない」と勘違いし、とけなかった。。反転だけの時間という事。Let's think about binary searching minimum t…

Problem - E - Codeforces Basic doubling technique, nothing quite special. void solve(){ int N; ll K; cin >> N >> K; vi F( N ), W( N ); for( int i = 0; i < N; ++i ) cin >> F[ i ]; for( int i = 0; i < N; ++i ) cin >> W[ i ]; const int LOGN =…

Problem - D - Codeforces The key is to realize that there are only 3 possible optimal strategies. 1. Drive the car once, and walk for the rest. 2. Keep going with the car no matter what. 3. Drive until the remained distance is not worth to…

Problem - E - Codeforces It was quite disgusting, for many optimisations were required. I read pekempey's article and I think it is easy to understand. pekempey.hatenablog.com The small / large id reference especially made me learn somethi…

Problem - D - Codeforces This is actually a good problem. While as always xor-sum will give us only the xor-sum of the values that appeared odd number of times in the range, we have to find the xor-sum of each number that appeared even num…

Problem - C - Codeforces Since the points are already given in a convex-hull fashion, where vertices are given in counter-clockwise order, things are simple. There are 2 cases we need to differentiate. First, if the pedestrian can simply w…

UVa Online Judge Binary search for the answer, and check with O( N ). It is clear that for each selling city, it should do its best to sell to the nearest cities that buys, and vice versa. Therefore, we could simply iterate each selling ci…

Kind of tried making hashing look reusable. #include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; vector< int > hmul = { 10007, 10009, 10039, 10061, 10069, 10093, 10103, 10141, 10177 }; template< typename T > int vtoi( const T &v ){ retu</bits/stdc++.h>…

UVa Online Judge First, we observe that if we have x connected components, we will have to connect them with x - 1 extra edges, whereas such connected components are only limited to those with vertices that at least involve in one edge. We…