2016年8月29日星期一

Maximum profit by buying and selling a share at most twice

Problem
   In a daily share trading, a buyer buys shares in the morning and sells it on same day. If the trader is allowed to make at most 2 transactions in a day, where as second transaction can only start after first one is complete (Sell->buy->sell->buy). Given stock prices throughout day, find out maximum profit that a share trader could have made.

Code
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 110;
int n;
int a[N];
int dp[N];
int main() {
    scanf("%d",&n);
    for (int i = 0;i < n;i ++) {
        scanf("%d",&a[i]);
    }
    memset(dp,0,sizeof(dp));
    int max_val = a[n - 1];
    for (int i = n - 2;i >= 0;i --) {
        dp[i] = max(dp[i + 1],max_val - a[i]);
        max_val = max(max_val,a[i]);
    }
    
    int min_val = a[0];
    for (int i = 1;i < n;i ++) {
        dp[i] = max(dp[i - 1],a[i] - min_val + dp[i]);
        min_val = min(min_val,a[i]);
    }
    cout << dp[n - 1] << endl;
}

Compute sum of digits in all numbers from 1 to n

Problem
   Given a number x, find sum of digits in all numbers from 1 to n.

Solution
     take 389 for example;
     count[1,299) + [300,389)'s 3 + [1,89)
Code
#include <stdio.h>
#include <iostream>
#include <cmath>
using namespace std;


int f(int n) {
    if (n < 10) {
        return n * (n + 1) / 2;
    }
    
    int d = log10(n);
    
    int a[15];
    a[1] = 45;
    for (int i = 2;i <= d;i ++) {
        a[i] = a[i - 1] * 10 + 45 * pow(10,i - 1);
    }
    int p = ceil(pow(10,d));
    
    int msd = n / p;
    
    int p1 = msd * a[d] + (msd * (msd - 1)) / 2 * p;
    //int p1 = f(msd * p - 1);
    int p2 = msd * (n % p + 1) + f(n % p);
    return p1 + p2;
}

int main() {
 //code
 cout << f(389) << endl;
 return 0;
}

2016年8月28日星期日

Collect maximum points in a grid using two traversals

Problem
   Given a matrix where every cell represents points. How to collect maximum points using two traversals under following conditions?
1) The first traversal starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (R-1, 0). The second traversal starts from top right corner, i.e., (0, C-1) and should reach bottom right corner, i.e., (R-1, C-1)/

2) From a point (i, j), we can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

3) A traversal gets all points of a particular cell through which it passes. If one traversal has already collected points of a cell, then the other traversal gets no points if goes through that cell again.
Solution
     check bound at first is much easier.
Code
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
const int R = 55;
const int C = 55;
int dp[R][C][C];
int a[R][C] = {{3, 6, 8, 2},
         {5, 2, 4, 3},
         {1, 1, 20, 10},
         {1, 1, 20, 10},
         {1, 1, 20, 10},
         };
int n,m;

int dfs(int row,int c1,int c2) {
    if (c1 < 0 || c1 >= m || c2 < 0 || c2 >= m) return -0x3f3f3f3f;
    if (row == n - 1 && c1 == 0 && c2 == m - 1) {
        return a[row][c1] + a[row][c2];
    }
    if (row == n - 1) return -0x3f3f3f3f;
    if (dp[row][c1][c2] != -1) return dp[row][c1][c2];
    int add = 0;
    if (c1 == c2) {
        add = a[row][c1];
    }
    else {
        add = a[row][c1] + a[row][c2]; 
    }
    
    int ans = -0x3f3f3f3f;
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2));
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2 + 1));
    ans = max(ans,add + dfs(row + 1,c1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1,c2));
    ans = max(ans,add + dfs(row + 1,c1,c2 + 1));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2 + 1));
    return dp[row][c1][c2] = ans;
}

int calc() {
    memset(dp,-1,sizeof(dp));
    return dfs(0,0,m - 1);
}

int main() {
    n = 5;
    m = 4;
    cout << calc() << endl;
 return 0;
}

Minimum Points To Reach Destination dp

Problem
   Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. 
Solution
     use bottom-up is much easier than up-bottom;
     and pay attention to that the beginning should has at least 1 point.
Code
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;


const int N = 15;
int T;
int n,m;
int a[N][N];
int dp[N][N];
int main() {
    scanf("%d",&T);
    while (T --) {
        scanf("%d%d",&n,&m);
        for (int i = 1;i <= n;i ++) {
            for (int j = 1;j <= m;j ++) {
                scanf("%d",&a[i][j]);
            }
        }
        dp[n][m] = a[n][m] > 0 ? 1 : -a[n][m] + 1;
        for (int i = n;i >= 1;i --) {
            for (int j = m;j >= 1;j --) {
                if (i == n && j == m) continue;
                int mins = 0x3f3f3f3f;
                if (i + 1 <= n) {
                    mins = min(mins,dp[i + 1][j]);
                }
                if (j + 1 <= m) {
                    mins = min(mins,dp[i][j + 1]);
                }
                dp[i][j] = max(mins - a[i][j],1);
            }
        }
        cout << dp[1][1] << endl;
    }
}

Mobile Numeric Keypad Problem

Problem
   Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
Given a number N, find out the number of possible numbers of given length.
Solution
   dynamic programming

Code
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char board[4][3] = {
  {'1','2','3'},
  {'4','5','6'},
  {'7','8','9'},
  {'*','0','#'}
};

const int N = 110;
int dp[N][12];
int dir[5][2] = {0,0,1,0,-1,0,0,1,0,-1};
int main() {
 memset(dp,0,sizeof(dp));
 for (int i = 0;i <= 9;i ++) {
     dp[0][i] = 0;
     dp[1][i] = 1;
 }
 
 for (int i = 2;i <= 100;i ++) {
     for (int j = 0;j < 4;j ++) {
         for (int k = 0;k < 3;k ++) {
             if (board[j][k] == '*' || board[j][k] == '#') continue;
             int num = board[j][k] - '0';
             for (int t = 0;t < 5;t ++) {
                 int dx = j + dir[t][0];
                 int dy = k + dir[t][1];
                 if (dx < 0 || dy < 0 || dx >= 4 || dy >= 3) continue;
                 if (board[dx][dy] == '*' || board[dx][dy] == '#') continue;
                 int nxtnum = board[dx][dy] - '0';
                 dp[i][num] += dp[i - 1][nxtnum]; 
             }
         }
     } 
 }
 
 int n;
 while (cin >> n) {
     int sum = 0;
     for (int i = 0;i <= 9;i ++) {
         sum += dp[n][i];
     }
     cout << sum << endl;
 }
    return 0;
}

[leetcode weekly contest]390. Elimination Game

Problem
   There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Solution
   recursive, assume you know the answer of f(i) i < n, and you try to calculate the answer of f(n);

Code
class Solution {
public:
    int f(int n,int dir) {
        if (n == 1) return 1;
        if (n % 2 == 0 && dir == -1) {
            int ans = f(n / 2,-dir);
            return ans + (ans - 1);
        }
        else if (n % 2 == 0 && dir == 1) {
            int ans = f(n / 2,-dir);
            int tmp = ans + ans;
            return tmp;
        }
        else if (n % 2 == 1 && dir == 1) {
            int ans = f(n / 2,-dir);
            return ans + ans;
        }
        else if (n % 2 == 1 && dir == -1) {
            int ans = f(n / 2,-dir);
            return ans + ans;
        }
        return 0;
    }
    int lastRemaining(int n) {
        return f(n,1);
    }
};

[leetcode weekly contest]391. Perfect Rectangle

Problem
   Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Code
const int MAXN = 110000;
int sum[MAXN * 4 + 110];
int cover[MAXN * 4 + 110];
int x[MAXN];
struct Seg {
    int l,r,h;
    int flag;
    Seg() {}
    Seg(int a,int b,int c,int d) {
        l = a;
        r = b;
        h = c;
        flag = d;
    }
    bool operator< (const Seg &b) const {
  if (h != b.h)
        return h < b.h;
  return flag < b.flag;
    }
}seg[MAXN];

class Solution {
public:
 
    void update(int L,int R,int val,int l,int r,int rt) {
        if (L <= l && r <= R) {
            cover[rt] += val;
            sum[rt] = x[r + 1] - x[l];
            return ;
        }
        int m = (l + r) >> 1;
        if (cover[rt] > 0) {
            cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
            cover[rt] = 0;
            sum[rt << 1] = x[m + 1] - x[l];
            sum[rt << 1 | 1] = x[r + 1] - x[m + 1];
        }
  
  if (L <= m)  {
   update(L,R,val,l,m,rt << 1);
  }
  if (m < R) {
      update(L,R,val,m + 1,r,rt << 1 | 1);
  }
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int m = 0;
        int n = rectangles.size();
        for (int i = 0;i < n;i ++) {
            x[m] = rectangles[i][0];
            seg[m] = Seg(rectangles[i][0],rectangles[i][2],
                         rectangles[i][1],1);
            m ++;
            x[m] = rectangles[i][2];
            seg[m] = Seg(rectangles[i][0],rectangles[i][2],
                         rectangles[i][3],-1);
   m ++;
        }
        sort(x,x + m);
        sort(seg,seg + m);
        int tot = 1;
        for (int i = 1;i < m;i ++) {
            if (x[i] != x[i - 1]) {
                x[tot ++ ] = x[i];
            }
        }
        memset(cover,0,sizeof(cover));
        memset(sum,0,sizeof(sum));
        int totarea = 0;
        for (int i = 0;i < m - 1;i ++) {
            int l = lower_bound(x,x + tot,seg[i].l) - x ;
            int r = lower_bound(x,x + tot,seg[i].r) - x - 1;
            if (l <= r) {
                update(l,r,seg[i].flag,0,tot - 1,1);
            }
            totarea += sum[1] * (seg[i + 1].h - seg[i].h);
        }


  int area3 = 0;
  vector<pair<int,int> > vec;
  for (int i = 0;i < n;i ++) {
   vec.push_back(make_pair(rectangles[i][0],rectangles[i][1]));
   vec.push_back(make_pair(rectangles[i][2],rectangles[i][3]));
   area3 += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
  }
  sort(vec.begin(),vec.end());
  int curarea = (vec[n * 2 - 1].first - vec[0].first) * (vec[n * 2 - 1].second - vec[0].second);
  return totarea == curarea && totarea == area3;
    }
};