I have given up using Simplex Method.... Given an augmented matrix, where each row, say { a, b, c, .. z }, represents a * x1 + b * x2 + .. ≤ z, we will find the maximum value for some vector of coefficient for these variables. A brute forc…

First it will retrieve a possible solution for the augmented matrix. Then if valid() returns false, there is no solution. If it is required to distinguish whether there are infinite solutions or not, do an extra work checking whether there…

Dashboard - Round 2 2009 - Google Code Jam Let us first represent the relations of the charts by directing edges from chart A to chart B iff A can be laid under B on the same sheet of paper ( as the description says ) without interfering o…

Given N nodes, M arcs, returns max flow from 0 to N. #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair< int, int > pii; typedef pair< int, ll > pil; typedef pair< ll, int > pli; typedef pair< ll, ll > pll; typedef vector< i</bits/stdc++.h>…

Problem - E - Codeforces Quite creative a problem. If it were no problem E, I would have really thought performing brute force counting sort will somehow pass. Anyways, we will try bundling the same alphabets together for the sake of impro…

Problem - D - Codeforces Let's try to simulate. First we have lazy-propagation on discretized segment tree where it only creates nodes when really needed, that is, the total memory consumption will be about O( M lg N ). The objective is cl…

Problem - C - Codeforces First we should notice that if some number x does not include factor p ( p > 2 and p is not of form 2^k ), it can never be p nor a multiple of p. We should also realize it is impossible that the optimal answer is o…

Problem - E - Codeforces It is obvious we should perform DP, probably one from the upper-left, the other from the bottom-right, getting close to each other, marching across grids only when they match. We cannot store both the x-y-coordinat…

Problem - D - Codeforces First, we will notice that iff there are more than 1 alphabet with frequency of an odd number, a palindrome sequence cannot be formed. Thus we are only concerned with whether the frequency of each alphabet is odd o…

Problem - C - Codeforces We will first retrieve the answer for the original string, then update one by one in each query. Without loss of generality, we will assume that each update is meaningful ( that is, either changes a character to a …

Problem - B - Codeforces Imagine the tile that occupies the range. Mark the position where the other player had chosen beforehand. It is now obvious that we will choose the range with greater range, and put ours exactly next to the foe's. …

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair< int, int > pii; typedef pair< int, ll > pil; typedef pair< ll, int > pli; typedef pair< ll, ll > pll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll</bits/stdc++.h>…

Problem Description: Given an arithmetic sequence, add parentheses freely to create the maximal outcome. For example, the optimal way to add parentheses for: 5-8+7*4-8+9 would be: 200 = (5 − ((8 + 7) × (4 − (8 + 9))))Constraints: 1. Only +…

Problem Description: Given 2 strings, output the minimal edit distance between them. There are 3 valid operations, each with cost of 1. 1. Delete a character. 2. Insert a character. 3. Replace a character. The objective is to make both str…

UVa Online Judge I have read a few good sites for reference. phoenixzhao.github.io http://apir8181.github.io/algorithm/2014/10/02/closest_pair.html A very classic problem for divide and conquer. There are 3 ways to solve this, with D&C ( O…

Problem - E - Codeforces Seems like there were cases that deliberately hacked those who used only one MOD value for hashing, where such hack tests can easily be prepared with a little knowledge of birthday paradox. First, it might be a lit…

Problem - D - Codeforces I thought this resembled quite a lot with this problem. What we really have to do is to perform dynamic programming on: dp[ S ][ i ] : the value of having each element in set S eaten and i'th as the last int bit_co…

Problem - C - Codeforces Not much do I really need to mention. We will only have to traverse the graph with a single DFS. void dfs( const vvi &G, const vi &has_cat, int cat_cnt, int u, int fa, int &ans ){ if( has_cat[ u ] ) ++cat_cnt; // c…

Problem - B - Codeforces If the friends are sorted such that each of their money is in ascending order, any valid combinations, having maximised the largest value, will be a contiguous segment. Hence we will apply crawling technique to fin…