10252 - Common Permutation: (WA) Forgot completely clear out testing messages.
10071 - Back to High School Physic: (WA) Carelessly used abs() in the signed display value (displacement).
10055 - Hashmat the Brave Warrior: (WA) Forgot use abs().
100 - The 3n+1 problem: (WA)(TL) 1. Although the input < 30000, the output < MAX(long), we still need (long long) variables in the calculation in order to get a correct answer. 2. Alert: the first input can greated than the second input. 3. Dynamic programming method will cause the TL, Please just use simple recursive function.
108 - maxSum: 1. Based on Kadane 1D algorithm. 2. Notice shortest resulted seqence can be {} or {min element}. 3. 2D: O(n^3) if 1D: O(n).
305 - Joseph: we need solve M for all P[0] to P[K-1] >= K. where N=2K.
M can be >> N
// P[0]=(M-1)%N
// P[i+1] = (P[i]+M-1) % (N-i)
// Please notice that ALL labels (of position > P[i]) will decrease 1 in each round.
// -> If last player is 1, Only label 1 will not be changed in the whole calculation.
10616 - Division Group Sum :
= Subset Sum Problem - check My Dynamic Programming Study: Subset sum problem
348 - Optimal Array Multiplication Sequence (CE)
Minmize the number of multipication operations of A1 x A2 .....Ai X Ai+1 .... An
Core idea: recursive function + dp
#mult(1,N) = min(i) { mult(1,i) + mult(i+1,n) + R(a)*C(i)*C(b) }
Why R(a)*C(i)*C(b) ?
==> (Aa x...x Ai) becomes a matrix of Row(A1) X Column(Ai)
& (Ai+1 x...x Ab) becomes a matrix of Row(Ai+1) X Column(Ab)
so the # of multiplication of product these two Matrix is R(a)*C(i)*C(b)
* UVA Compile Error(CE): Don't use _I64_MAX for long long, use 1LL<<63-1 instead. UVA don't accept.
543 - Goldbach's Conjecture (CE) error: 'memset' was not declared in this scope --> need #include <cstring>
10054 - The Necklace : Euler tour: Visit all edges. completely connected/even degrees.
connected? find(u)==find(v)? for all u,v
By function: find(x){ if(x==p[x])?return x; else {p[x]=find(p[x]); return p[x];}};
Euler Tour: void dfs(u){
forr(v,N) // all outgoing edges will be traced finally...
if(G[u][v]>0)
{
G[u][v]--;G[v][u]--;
dfs(v);
cout<<u<<","<<v;
};
};
// We MUST use G[u][v]--;G[v][u]--; otherwise Euler cannot be traced.
(You may try to use if(u<v)G[u][v]--elseG[v][u]-- instead, but this doesn't work. )
443 -
- Find out the humble number iteratively.
- Cannot use lareg ranged value-dp[], because 20000000000 > 32bit int and it is too large.
- Same reason, cannot use Eratosthenes Prime Number Sieve
- (WA)Notice how to generate 1st, 2nd, 111th, 221st etc... check both N%10 and N%100 (easy to miss N%100 part).
string su;
su="th";
N10=N%10;
N100=N%100;
if(N10==1&&N100!=11)su="st";
if(N10==2&&N100!=12)su="nd";
if(N10==3&&N100!=13)su="rd";
cout<<"The "<<N<<su<<" humble number is "<<h[N]<<"."<<endl;
10161 -
Locate the number in O(1) time.
X=
r=1: 1
r=2: 122
r=3: 33321
r=4: 1234444
r=5:555554321
// size of row r = 2r-1
// tail(r) = r^2
// head(r) = (r-1)^2+1
// midvalue(r) = r
// when N>=head(r) => 0>=r^2-2r+2-N
// r=1 when N=1;
// r=(int)(1+sqrt(1+(N-2)))
// c=N-head(r); 0...2r-2
// when r is odd, if c<r, x=r, else x=(2r-c-1)
// when r is even, if c<r, x=c+1, else x=r
Y=
r=1: 1
r=2: 221
r=3: 12333
r=4: 4444321
r=5:123455555
// when r is odd, if c<r, y=c+1, else y=r
// when r is even, if c<r, y=r, else y=(2r-c-1)
No comments:
Post a Comment