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/

Solution UVA: 679 - Dropping Balls

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss679 - Dropping Balls	Accepted	C++11	0.270	0.000	4922	36 secs ago

Suggest:

The first, we create branch from ball 1 (we will have 1, 2, 4, 8, ...) and save result F[deapth(i)] [1] =node(i). 

Then continue create branch ball 2 (we will have 1, 3, 6, 12, ...) and save result F[deapth(i)] [2] =node(i).

So on ...

Finally, we have a tree and result dynamic programming top down ! 

Happy Coding :)

#include<bits/stdc++.h>

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

using namespace std;

const int maxNode= (int)pow(2, 20) - 1;

const int maxBall= 524288;

int F[21][maxBall+1];

bool state[maxNode+1];

int t, n, depth, ball;

   

void f(int node, int depth, int ball){

    if (node > maxNode) return;

    if (state[node]) f(node*2+1, depth+1, ball);

    else f(node*2, depth+1, ball);

   

    if (F[depth][ball] == 0) F[depth][ball]= node;

    state[node] = (state[node] ? false : true);

}

void init(){

   

    FOR(i, 1, maxBall) f(1, 1, i);

}

void solve(){

   

    cin >> depth; if (depth == -1) exit(0);

    cin >> ball;

   

    cout << F[depth][ball]<<"\n";

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    init();

   

    cin >> t;

    while(t--){ solve();}

}

Solution UVA: 193 - Graph Coloring

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss193 - Graph Coloring	Accepted	C++11	0.040	0.000	2822	1 mins ago

Suggest:

- Only 2 state to Recurive Backtracking (u black or u white, with u from 1-> n)

* I have a close branch used to stop early, but I think we don't need this and it's still acceptable

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

const int N= 1000111;

int t, n, m, u, v, maxBlack, minWhite;

vector<int> a[N];

int color[N];

vector<int> res;

void f(int u, int white, int black){

    if (minWhite < white) return;

   

    if (white + black == n){

       

        if (maxBlack < black){

            maxBlack= black;

            minWhite= white;

            res.clear();

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

                if (color[i]==1) res.pb(i);

        }

        return;

    }

   

    bool ok= true;

    for(auto v:a[u])

        if (color[v]==1){

            ok= false;

            break;  

        }

    if (ok){

        color[u]= 1;

        f(u+1, white, black+1);

       

        color[u]= 0;

        f(u+1, white+1, black);

    }

    else{

        color[u]= 0;    

        f(u+1, white+1, black);

    }

}

void reset(){

    for(int i=1; i<=n; i++) color[i]= -1, a[i].clear();

    maxBlack= 0;

    minWhite= 1000111000;

}

int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

   

    cin >> t;

    while(t--){

        cin >> n >> m;

       

        reset();

       

        while(m--){

           

            cin >> u >> v;

            a[u].pb(v);

            a[v].pb(u);

        }

        f(1, 0, 0);

        cout<<maxBlack<<"\n";

        if (not res.empty()) cout<<res[0];

        for(int i=1; i<res.size(); i++) cout<<" "<<res[i];

        cout<<"\n";

    }

}

Quay lại định kỳ