Wednesday, February 29, 2012

My UVA competitive programming notes

10189 - Minesweeper : (WA) Carelessly added unwanted blank line after the last displaying item.

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...

// 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 - Humble Numbers
- 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;
        cout<<"The "<<N<<su<<" humble number is "<<h[N]<<"."<<endl;

Locate the number in O(1) time.


r=1:      1
r=2:    122 
r=3:   33321
r=4: 1234444

// 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

r=1:       1
r=2:     221
r=3:   12333
r=4: 4444321

// 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