UVa Online Judge maxl[ i ][ j ] = maximal number of digits of a possible number x, where x is constructible with not more than i sticks and remains j for % M maxd[ i ][ j ] = having maxl[ i ][ j ], the maximal digit that could be used maxl…

Problem - D - Codeforces The number that some prime would be involved in the multiplication, is the cumulative product of the count of power for all other primes, again multiplied by ( 1 + 2 + .. + c ), where c is the count of power of the…

Problem - B2 - Codeforces Having done so many ( not really many though ) problems, I always warn myself to think of an easier solution. Anyways, this could be solved with DP. Since MAXN = 1e9, and 2*3*7*11*13*17*19*31*37 ≥ 2e9, there will …

Problem - 106C - Codeforces I do seriously doubt the tag is nonsense. Anyways, for the buns that do not require stuffings, we will do infinite knapsack. For the buns that need stuffings, simply do multiple knapsacks. const int MAXN = 1e3 +…

http://codeforces.com/problemset/status The number of situations such that the face x is of the maximum, is ( x^n - ( x - 1 )^n ). So the expectancy we are looking for can be calculated as However, simply implementing this, you will find i…

Problem - D - Codeforces Without losing generality, let n ≤ m, we are to find all such pairs ( n, m ) that satisfy: Do a little math and we will conclude that Since n ≤ m, the upper bound of n is of some constant multiple of X^( 1 / 3 ). T…

對因數分解困惑的時候剛好經過這個文章: 如何快速验证一个超大的数为质数 - SegmentFault 以前是聽過麻煩的 Miller-Rabin偽素數檢驗法，倒是沒聽過除此之外有這麼簡潔的隨機算法可以快速判斷是否質數。原理是根據 Fermat's little theorem： a ^ ( p - 1 ) =…

fermat: フェルマー方程式 (Fermat) - 2007年 日本情報オリンピック春合宿OJ | AtCoder http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day2_21.pdf Although it is a known fact that no integer solution exists for x^n + y^n = z^n, for n ≥ 3,…

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf mall: ショッピングモール (Mall) - 2007年 日本情報オリンピック春合宿OJ | AtCoder Get column prefix sum for each individual row, and enumerate top left corner to reduce unnece…

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf factorial: 階乗 (Factorial) - 2007年 日本情報オリンピック春合宿OJ | AtCoder First we will decompose N into powers of prime factors. Anything left after decomposing the first…

Problem - C - Codeforces Well, I came up with an algorithm to look at every previous operations in each operation, and splitting bifurcating paths into two unique paths. That gave me a TLE though I believe is good to go in terms of time co…

Problem - B - Codeforces Silly I really failed this one in the real test. Should have calmed down and check all cases manually since there weren't many to come up. void solve(){ string s; cin >> s; int dec_pos = s.size(); for( int i = 0; i …

http://codeforces.com/contest/606/problem/D Having MST, we will first want to sort the edges according to their weight. If we assign for each edge from which has smaller weight, if it is to be part of the MST, we will have to have it conne…

http://codeforces.com/contest/691/problem/D Being able to swap as many times, that means swappable positions are in the same disjoint set, where in each disjoint set values in those positions could be arranged arbitrarily. We have to manag…

http://codeforces.com/contest/606/problem/C Imagine if we decided exactly which cars are going to be moved, and of course each of them will be moved no more than once( quite obvious ). The ones left, putting them into a separate sequence, …

http://codeforces.com/contest/691/problem/C Well, I thought it was not quite easy, some details need to be wary of. void solve(){ string s; cin >> s; int _t; // cut off leading zeros for( _t = -1; _t + 1 < s.size(); ++_t ) if( s[ _t + 1 ] …

#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <utility> #include <functional> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair< int, int > pii; typedef vector< int > vi; typedef vector< vi >…</functional></utility></set></stack></queue></vector></algorithm></iostream>

https://www.hackerrank.com/challenges/liars 差分约束系统 - 维基百科，自由的百科全书 Well, it is a well known trick. For any inequality, take a[ u ] + W ≥ a[ v ], it will be equivalent to having a unidirectional edge with weight W, from u t…

Problem - E - Codeforces dp[ i ][ j ][ k ]: possible or not to make value k, out of a set with sum j, examining the first i coins in the array. dp[ i ][ j ][ k ] = dp[ i - 1 ][ j ][ k ] or dp[ i - 1 ][ j - C[ i ] ][ k ] or dp[ i - 1 ][ j -…

Problem - D - Codeforces According to the CRT, we have the conclusion that x % M = resolute value, if all values x % m[ i ] are known, where m[ i ] are all co-prime, and PRODUCT( m[ * ] ) = M. It is obvious that knowing x % p, where p % q …

Problem - C - Codeforces It's not difficult to see that only a bipartite graph will meet the requirements. bool dfs( int u, const vvi &G, vi &col ){ for( int v : G[ u ] ){ if( col[ v ] && col[ u ] == col[ v ] ) return false; if( !col[ v ] …

https://www.hackerrank.com/challenges/find-median-1 The classical two heap technique.. Don't forget to add ( int ) before calling size for container.. void solve(){ int N; cin >> N; vi A( N ); for( int i = 0; i < N; ++i ) cin >> A[ i ]; pr…

https://www.hackerrank.com/challenges/2s-complement It's easy to count the number of 1s that will be written in positive range with digit DP, simply remember the number of ways to reach some state will do. Let's think about cases where it'…

https://www.hackerrank.com/challenges/quicksort2 第一次寫 quickSort，只是想記錄一下。 void quickSort( int ql, int qr, vi &A ){ if( ql == qr ) return; int pivot = A[ ql ]; queue< int > small, large; for( int i = ql + 1; i <= qr; ++i ){ if( …

PEG Judge - IOI '96 - A Game 經典問題 就不多說了。 好啦，dp[ i ][ j ] 就是 [ i, j ] 的情況下先手最高得分，轉移的時候使對手最小，min-max問題。 void subSolve( int ql, int qr, const vi &A, const vi &pA, vvi &dp ){ if( dp[ ql ][ qr ] != -1 ) r…

https://www.hackerrank.com/challenges/maximize-sum 所有區間連續和都能表達成兩個前綴和的差，因此可以利用 set尋找適合的另一個前綴。 debug了一個小時，原來第一次插入 set的時候從 0開始了，然後就 WA半天摸不著頭緒。。。 void solve(){ int N; ll M;…

https://www.hackerrank.com/challenges/playing-with-numbers 差不多就是把不會變符號的先處理掉，然後把會變號的區間找出來做特別處理。做幾個 case就會發現會變號的部分造成的影響是 區間長度 * x + 2 * 區間和 注意 long long 然後我寫了快兩個小時，low…

https://www.hackerrank.com/challenges/bike-racers 參考了這篇：用于二分图匹配的匈牙利算法 | Comzyh的博客 第一次寫二分圖最大匹配，原來沒有想像中那麼難。我想二分圖最大匹配基本上可以想成是求婚問題，一群男士和一群女士有一些關聯，這些關聯可以用…

https://www.hackerrank.com/challenges/square-subsequences Sum up all the number of different common subsequences, for a = s[ 0, x ), b = s[ x ] + s( x, s.size() ) Ɐ 1 ≤ x with an additional restriction where s[ x ] must be taken in b. // n…

https://www.hackerrank.com/challenges/vertical-sticks I really consider this one quite tough. It took me literally an hour to understand how someone else's idea worked. algorithm - How to approach Vertical Sticks challenge? - Stack Overflo…