Algorithm Certificate and University GPA

 

Participated in The 2020 ICPC Asia Can Tho Regional Contest

Second place in the Vietnam Student Olympiad in Informatics 2020

Competed in the competition for excellent students of major high shools in the Northern Delta and Coastal Areas 2019

Second place in the informatics subject of province Quang Nam 2020

Participated in National Gifted Student Competition Informatics 2020

GPA current: 3.2 (max 3.86 - session 1, 2023)

Solution UVA: 10199 - Tourist Guide

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10199 - Tourist Guide	Accepted	C++11	0.000	0.000	1107	2 mins ago

Conclusion: Vertex $�$ is an articulation point if:

• Vertex $�$ is not the root of the DFS tree and $\text{low}[�]\ge \text{num}[�]$ for all $�$ which are direct children of $�$ in the DFS tree. Or

• Vertex $�$ is the root of the DFS tree and has at least $2$ direct children in the DFS tree.

Algorithm by VNOI (Click to read detail)

#include <bits/stdc++.h>

#define FOR(i, a, b) for(int i=a; i<=b; i++)

 

using namespace std;

 

const int maxN = 10010;

int n, m, test=0;

bool joint[maxN];

int timeDfs = 0, bridge = 0;

int low[maxN], num[maxN];

vector <int> g[maxN];

 

void dfs(int u, int pre) {

    int child = 0; // Số lượng con trực tiếp của đỉnh u trong cây DFS

    num[u] = low[u] = ++timeDfs;

    for (int v : g[u]) {

        if (v == pre) continue;

        if (!num[v]) {

            dfs(v, u);

            low[u] = min(low[u], low[v]);

            //if (low[v] == num[v]) bridge++;

            child++;

            if (u == pre) { // Nếu u là đỉnh gốc của cây DFS

                if (child > 1) joint[u] = true;

            }

            else if (low[v] >= num[u]) joint[u] = true;

        }

        else low[u] = min(low[u], num[v]);

    }

}

void reset(){

    bridge= 0, timeDfs= 0;

    FOR(i, 1, n) low[i] = num[i] = 0, joint[i]= false, g[i].clear();

}

void testcase() {

    if (test++) cout<<"\n";

    reset();

   

    unordered_map<string, int> encoding;

    unordered_map<int, string> decoding;

    FOR(i, 1, n){

        string s; cin >> s;

        encoding[s] = i;

        decoding[i] = s;

    }  

   

    cin >> m;

    for (int i = 1; i <= m; i++) {

        string u, v;

        cin >> u >> v;

       

        int uu = encoding[u];

        int vv = encoding[v];

       

        g[uu].push_back(vv);

        g[vv].push_back(uu);

    }

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

        if (!num[i]) dfs(i, i);

    int cntJoint = 0;

    set<string> cities;

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

        cntJoint += joint[i];

        if (joint[i]) cities.insert(decoding[i]);

   

    }

    cout<<"City map #"<<test<<": "<<cntJoint<<" camera(s) found\n";

    for(auto city:cities) cout<<city<<"\n";

}

int main(){

    while(cin >> n && n){

        testcase();

    }

} 

Solution UVA: 796 - Critical Links

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss796 - Critical Links	Accepted	C++11	0.020	0.000	3287	1 mins ago

Suggest:

- To solve you need to know Finding Bridge in Graph (because this is a classic algogrithm of graph)

- This is link that help me understand this algorithm very easy

Important:

- Num[u]: index dfs to u

- Low[u] : index dfs to u (but smallest) 

Example:

- You dfs 1 -> 2 -> 3->4 but can 2->4  (this num[4] is 4, but low[4] is 3) 

Fomular: 

- If (num[v] == low[v]) => (u,v) is bridge

#include<bits/stdc++.h>

#define int long long

#define oo LLONG_MAX

#define pb push_back

#define FOR(i, a, b) for(int i=a; i<=b; i++)

using namespace std;

const int N= 1000111;

int t, n, u, v;

char c;

vector<int> a[N];

set<pair<int, int>> bridge;

int num[N], low[N];

int timeDfs = 0; // Thứ tự duyệt DFS

void dfs(int u, int pre) {

    num[u] = low[u] = ++timeDfs;

    for (int v : a[u]){

        if (v == pre) continue;

        if (!num[v]) {

           

            dfs(v, u);

           

            low[u] = min(low[u], low[v]);

            if (low[v]==num[v]) bridge.insert({min(u,v), max(u,v)});

        }

        else low[u] = min(low[u], num[v]);

    }

}

void reset(){

    FOR(i, 0, t-1) a[i].clear(), num[i]= 0, low[i]= 0;

    bridge.clear();

    timeDfs = 0;

}

void read(){

   

    cin >> u >> c >> n >> c;

       

    FOR(i, 1, n){

       

        cin >> v;

        a[u].pb(v);

        a[v].pb(u);

    }

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    while(cin >> t){    

       

        reset();

        FOR(i, 1, t) read();

       

        for (int i = 0; i <= t-1; i++)

            if (!num[i]) dfs(i, i);

       

        cout << bridge.size() << " critical links" << endl;

        for(auto x:bridge) cout<<x.first<<" - "<<x.second<<"\n";    

        cout<<"\n";

    }

}

Solution UVA: 124 - Following Orders

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss124 - Following Orders	Accepted	C++11	0.000	0.000	1611	42 secs ago

Tricky Lines :

Orderings are printed in lexicographical (alphabetical) order

Output for different constraint specifications is separated by a blank line.

Analysis :

backtracking

sort the variables

keep an 2d array ‘role’

role[{x,y}] = true, if x < y

so when role[{y,x}] == true, u must not go further

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<char> a, v;

typedef pair<char, char> ii;

map<ii, bool> role;

unordered_map<char, bool> visited;

char x, y;

string s;

int test= 1;

void reset(){

    a.clear();

    role.clear();

    visited.clear();

}

bool pass_role(int y){

    for(auto x:v)

        if (role[{y,x}]) return false;

    return true;

}

void f(int u){

    if (u == a.size()){

        for(auto x:v) cout<<x;

        cout<<"\n";

    }

   

    for(int i=0; i<a.size(); i++)

        if (not visited[a[i]] and pass_role(a[i])){

           

            v.push_back(a[i]);

            visited[a[i]]= true;

           

            f(u+1);

           

            v.pop_back();

            visited[a[i]]= false;

        }  

}

int main(){

    while(getline(cin, s)){

   

        if (test++ != 1) cout<<"\n";    

       

        reset();

       

        istringstream is(s);    while(is >> x) a.push_back(x);

       

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

       

        getline(cin, s);    istringstream iss(s);       while(iss >> x >> y) role[{x,y}]= true;

       

        f(0);  

    }

}

Ý tưởng từ https://tausiq.wordpress.com/2010/09/02/uva-124-following-orders/