Solution UVA: 348 - Optimal Array Multiplication Sequence

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss348 - Optimal Array Multiplication Sequence	Accepted	C++11	0.200	0.000	2357

Suggest:
- I only view tutorial in youtube Matrix Chain Multiplication and then code it by Top-down DP

#include<bits/stdc++.h>

#define X first

#define Y second

#define int long long

using namespace std;

const int N= 1000111;

int L[N], R[N];

unordered_map<int, pair<int, string>> F[11];

pair<int, string> f(int i, int j){

    if (F[i].count(j)) return F[i][j];

    if (i == j) return {0, "A"+to_string(i)};

    if (i+1 == j) return {L[i]*R[i]*R[j], "(A"+to_string(i)+" x A"+to_string(j)+")"};

   

    int x = 1e18;

    string y;

   

    for(int k=i; k<j; k++){

       

        auto p1 = f(i, k);

        int x1 = p1.X;

        string y1 = p1.Y;

       

        auto p2 = f(k+1, j);

        int x2 = p2.X;

        string y2 = p2.Y;

       

        int val = L[i] * R[k] * R[j];

           

        if (x > x1 + x2 + val){

           

            x = x1 + x2 + val;

            y = "("+y1+" x "+y2+")";

        }  

    }

    return F[i][j] = {x,y};

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    int n, cnt= 0;

    while(cin >> n && n){

        for(int i=1; i<=n; i++)

            cin >> L[i] >> R[i];

       

        for(int i=1; i<=10; i++) F[i].clear();

       

        cout<<"Case "<<++cnt<<": "<<f(1, n).Y<<"\n";    

    }

   

}

 

Solution UVA: 10911 - Forming Quiz Teams

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10911 - Forming Quiz Teams	Accepted	C++11	0.010	0.000	735	18 secs ago

We must "dynamic programming with bitmask" to solve problem if not want use another algorithm harder. (CP Book 4 Part 2 have tutorial detail)

If you not know dp bitmask before, i think we need go to from:

/1/ basic dp with state use vector<bool> 

/2/ upgrade dp with state use bitset

/3/ And final use dp bitmask !

Version /3/ use bitmask (Accepted -  Code from CP Book 4 Part 2): //version 1 and 2 in bottom

// Forming Quiz Teams

#include <algorithm>            // if you have problems with this C++ code,

#include <cmath>            // consult your programming text books first...

#include <cstdio>

#include <cstring>

using namespace std;

        /* Forming Quiz Teams, the solution for UVa 10911 above */

          // using global variables is a bad software engineering practice,

int N, target;                  // but it is OK for competitive programming

double dist[20][20], memo[1 << 16];  // 1 << 16 = 2^16, note that max N = 8

double matching(int bitmask) {                        // DP state = bitmask

                       // we initialize `memo' with -1 in the main function

  if (memo[bitmask] > -0.5)          // this state has been computed before

    return memo[bitmask];                   // simply lookup the memo table

  if (bitmask == target)                // all students are already matched

    return memo[bitmask] = 0;                              // the cost is 0

  double ans = 2000000000.0;               // initialize with a large value

  int p1, p2;

  for (p1 = 0; p1 < 2 * N; p1++)

    if (!(bitmask & (1 << p1)))

      break;                              // find the first bit that is off

  for (p2 = p1 + 1; p2 < 2 * N; p2++)              // then, try to match p1

    if (!(bitmask & (1 << p2)))     // with another bit p2 that is also off

      ans = min(ans,                                    // pick the minimum

                dist[p1][p2] + matching(bitmask | (1 << p1) | (1 << p2)));

  return memo[bitmask] = ans;    // store result in a memo table and return

}

int main() {

  int i, j, caseNo = 1, x[20], y[20];

  // freopen("10911.txt", "r", stdin);      // redirect input file to stdin

  while (scanf("%d", &N), N) {                    // yes, we can do this :)

    for (i = 0; i < 2 * N; i++)

      scanf("%*s %d %d", &x[i], &y[i]);                // '%*s' skips names

    for (i = 0; i < 2 * N - 1; i++)        // build pairwise distance table

      for (j = i + 1; j < 2 * N; j++)      // have you used `hypot' before?

        dist[i][j] = dist[j][i] = hypot(x[i] - x[j], y[i] - y[j]);

    // use DP to solve min weighted perfect matching on small general graph

    for (i = 0; i < (1 << 16); i++) memo[i] = -1.0;  // set -1 to all cells

    target = (1 << (2 * N)) - 1;

    printf("Case %d: %.2lf\n", caseNo++, matching(0));

} } // return 0;

Verison /1/ basic dp use vector<bool> (Only apply N <= 4, my code)

#include<bits/stdc++.h>

using namespace std;

const int N= 9;

int x[N], y[N];

double d[N][N];

int n;  

string s;

map<vector<bool>, double> F;

double f(vector<bool> state){

    if (F.count(state)) return F[state];

   

    int i= 0;

    for(i; i<state.size(); i++)

        if (state[i] == false) break;

    if (i == state.size()) return 0;

   

    double ans = 1000111000;

    int p1, p2;

   

    for(p1 = 0; p1 < 2*n; p1++)

        if (state[p1] == false) break;

   

    for(p2 = p1 + 1; p2 < 2*n; p2++)

        if (state[p2] == false){

           

            state[p1]= true;

            state[p2]= true;

           

            ans = min(ans, d[p1][p2] + f(state));

           

            state[p1]= false;

            state[p2]= false;

        }

   

    return F[state] = ans;

   

}

int main(){

    while(cin >> n && n){

        for(int i=0; i<2*n; i++)

            cin >> s >> x[i] >> y[i];

           

        for(int i=0; i<2*n; i++)

            for(int j=0; j<2*n; j++)

                d[i][j] = hypot(x[i]-x[j], y[i]-y[j]);

       

        vector<bool> state(2*n, false);            

        F.clear();

        cout << f(state) <<"\n";

    }

}

Verison /2/ dp use bitset (Only apply N <= 4, memory smaller than vector<bool> and deploy near bitmask,  my code)

#include<bits/stdc++.h>

using namespace std;

const int N= 8;

int x[N], y[N];

double d[N][N];

int n;  

string s;

unordered_map<bitset<16>, double> F;

double f(bitset<16> state){

    if (F.count(state)) return F[state];

   

    int i= 0;

    for(i; i<2*n; i++)

        if (state.test(i) == false) break;

    if (i == 2*n) return 0;

   

    double ans = 1000111000;

    size_t p1, p2;

   

    for(p1 = 0; p1 < 2*n; p1++)

        if (state.test(p1) == false) break;

       

    for(p2 = p1 + 1; p2 < 2*n; p2++)

        if (state.test(p2) == false){

           

            state.flip(p1);

            state.flip(p2);

           

            ans = min(ans, d[2*n-1-p1][2*n-1-p2] + f(state));

           

            state.flip(p1);

            state.flip(p2);

        }

   

    return F[state] = ans;

   

}

int main(){

    while(cin >> n && n){

        for(int i=0; i<2*n; i++)

            cin >> s >> x[i] >> y[i];

           

        for(int i=0; i<2*n; i++)

            for(int j=0; j<2*n; j++)    

                d[i][j] = hypot(x[i]-x[j], y[i]-y[j]);

       

        bitset<16> state; //00...000(16)                

        F.clear();

        cout << fixed << setprecision(3) << f(state) <<"\n";

    }

}

Solution UVA: 820 - Internet Bandwidth

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss820 - Internet Bandwidth	Accepted	C++11	0.000	0.000	1678	1 days ago

Suggest:

- The problem is max flow basic (i found clean code to solve)  

#include <bits/stdc++.h>

 

using namespace std;

 

const int INF = 1e9;

 

struct Edge {

    int u, v;

    int capacity;

    int flow;

};

 

struct Network {

    int n;

    int source, sink;

 

    vector<vector<int> > a;

    vector<Edge> E;

 

    vector<int> cur;

    vector<int> dist;

 

    Network() {}

    Network(int n, int s, int t) {

        this->n = n;

        source = s; sink = t;

        a = vector<vector<int> > (n + 1);

        cur = dist = vector<int> (n + 1);

    }

 

    void addEdge(int u, int v, int c) {

        a[u].push_back(E.size()); E.push_back({u, v, c, 0});

        a[v].push_back(E.size()); E.push_back({v, u, 0, 0});

    }

 

    bool bfs() {

        fill(dist.begin(), dist.end(), -1);

        queue<int> Q; Q.push(source); dist[source] = 0;

        while (!Q.empty()) {

            int u = Q.front(); Q.pop();

            for (int i = 0; i < a[u].size(); ++i) {

                int id = a[u][i], v = E[id].v;

                if (dist[v] < 0 && E[id].flow < E[id].capacity) {

                    dist[v] =  dist[u] + 1;

                    Q.push(v);

                }

            }

        }

        return dist[sink] >= 0;

    }

 

    int dfs(int u, int flow) {

        if (!flow) return 0;

        if (u == sink) return flow;

        for (; cur[u] < a[u].size(); ++cur[u]) {

            int id = a[u][cur[u]], v = E[id].v;

            if (dist[v] != dist[u] + 1) continue;

            int delta = dfs(v, min(flow, E[id].capacity - E[id].flow));

            if (delta) {

                E[id].flow += delta; E[id ^ 1].flow -= delta;

                return delta;

            }

        }

        return 0;

    }

 

    int maxFlow() {

        int ans = 0;

        while (bfs()) {

            fill(cur.begin(), cur.end(), 0);

            while (true) {

                int delta = dfs(source, INF);

                if (!delta) break;

                ans += delta;

            }

        }

        return ans;

    }

};

 

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    int n, m, s, t, cnt= 0;

    while(cin >> n && n){

       

        cin >> s >> t >> m;

        Network G (n, s, t);

        while (m--) {

            int u, v, c;

            cin >> u >> v >> c;

            G.addEdge(u, v, c);

            G.addEdge(v, u, c);

         }

        cout << "Network "<<++cnt<<"\n";

        cout <<"The bandwidth is "<<G.maxFlow()<<"."<<"\n\n";

    }

}

 

Solution UVA: 10533 - Digit Primes

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10533 - Digit Primes	Accepted	C++11	0.220	0.010	1261	55 secs ago

Suggest:

- Sieve Prime

- Involving DP 1D RSQ/RMQ

#include<bits/stdc++.h>

using namespace std;

int dp[1000111];

bool isPrime[1000111];

   

bool digit_prime(int n){

    int s= 0;

    while(n>0){

        s+=n%10;

        n/=10;

    }

    return isPrime[s];

}

void sieve(int N) {

    for(int i = 0; i <= N;++i) {

        isPrime[i] = true;

    }

    isPrime[0] = false;

    isPrime[1] = false;

    for(int i = 2; i * i <= N; ++i) {

         if(isPrime[i] == true) {

             // Mark all the multiples of i as composite numbers

             for(int j = i * i; j <= N; j += i)

                 isPrime[j] = false;

        }

    }

    for(int i=1; i<=N; i++)

        dp[i] = dp[i-1] + (digit_prime(i) && isPrime[i] ? 1 : 0);

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    sieve(1000000);

    int t;  cin >> t;

    while(t--){

        int l,r;    cin >> l >> r;

        cout<<dp[r] - dp[l-1]<<"\n";

    }

}

Solution UVA: 10539 - Almost Prime Numbers

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10539 - Almost Prime Numbers	Accepted	C++11	0.000	0.000	183	1 mins ago

Suggest:

- Almost prime is the exponential of a prime number

- To find all the multipliers of prime numbers in the given time, we use the sieve prime

- After getting all the almost primes, to find out how many numbers are in a segment we use sort + binary search

#include<bits/stdc++.h>

#define int long long

using namespace std;

vector<int> a;

void sieve(int N) {

    int NN = N*N;

    bool isPrime[N+1];

    for(int i = 0; i <= N;++i) {

        isPrime[i] = true;

    }

    isPrime[0] = false;

    isPrime[1] = false;

    for(int i = 2; i * i <= N; ++i) {

         if(isPrime[i] == true) {

             // Mark all the multiples of i as composite numbers

             for(int j = i * i; j <= N; j += i)

                 isPrime[j] = false;            

        }

    }

     for(int i = 2; i <= N; ++i)

        if (isPrime[i])

            for(int j= i*i; j <= NN; j *= i) a.push_back(j);

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    sieve(1000000);

    sort(a.begin(), a.end());

   

    int t;  cin >> t;

    while(t--){

        int l, r;   cin >> l >> r;  

        int L = lower_bound(a.begin(), a.end(), l) - a.begin();

        int R = lower_bound(a.begin(), a.end(), r) - a.begin();

        if (a[R] > r) R--;

        cout << R - L + 1 <<"\n";

    }

}