Solution UVA: 11235 - Frequent values

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
π |  | discuss11235 - Frequent values	Accepted	C++11	0.220	0.010	1841	7 mins ago

Suggest:

- Lv0: Use RMQ for with value is frequence of a[i]

- Lv1: https://algorithmist.com/wiki/UVa_11235

- Lv2: https://niceproblems.blogspot.com/2012/05/uva-11235-frequent-values.html

* I was able solve after read lv2, i think you can too :)

#include<bits/stdc++.h>

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

using namespace std;

const int N=1000111;

const int oo=1000111000;

int n,m;

int A, B;

int a[N], st[4*N];

unordered_map<int, int> cnt, start;

void build(int id, int l, int r){

    if (l==r){

        st[id]= cnt[ a[l] ];

        return;

    }

    int mid=(l+r)/2;

    build(id*2, l, mid);

    build(id*2+1, mid+1, r);

    st[id]=max(st[id*2], st[id*2+1]);

}

int getMAX(int id, int l, int r){

    if (r < A || l > B) return -oo;

    if (A <= l && r <= B) return st[id];

    int mid=(l+r)/2;

    return max( getMAX(id*2, l, mid) ,getMAX(id*2+1, mid+1, r) );

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    while(cin >> n && n){

        cin >> m;

        cnt.clear();

       

        FOR(i, 1, n){

           

            cin >> a[i];

            cnt[a[i]]++;

            if (cnt[a[i]]==1) start[a[i]]= i;

        }

   

        build(1, 1, n);

       

       

       

        FOR(i, 1, m){

            cin >> A >> B;

            if (a[A] == a[B]) cout<<B-A+1<<"\n";

            else{

                int resL = start[  a[A]  ] + cnt[ a[A] ] - A;

                int resR = B - start[ a[B] ] + 1;

                int ans= max(resL, resR);

               

               

                A= start[ a[ A ] ] + cnt[ a[ A ] ] ;

                B = start[ a[ B ] ] - 1;

               

                cout<<max(ans, getMAX(1, 1, n))<<"\n";

            }

               

        }  

    }

}

   

  

Lưu ý: Tôi đã có thể giải quyết sau khi đọc lv2, tôi nghĩ bạn cũng có thể

Solution UVA: 793 - Network Connections

 Log:

#		Problem	Verdict	Language	Run Time	Submission Date
29222250	793	Network Connections	Accepted	C++11	0.020	2024-02-21 09:27:35

 
Suggest:
- First, you must search Google to know algorithm Union-Find Disjoint Sets

-Then, you only need care to 2 function below:

<1> this function have effect to find they group of u

int root(int u){
     return fa[u]=( fa[u]==u ? u : root(fa[u]) );
}

<2> this function have effect to join u and v to 1 group

void join(int u, int v){
     fa[root(u)]=root(v);
}

NOTE: although i forget detail but i still ez solve problem because i know effect of function

#include<bits/stdc++.h>

#define N 1000111

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

using namespace std;

int n,t;

int fa[N];

void Reset(){

FOR(i, 1, n) fa[i]= i;

}

int root(int u){

return fa[u]=( fa[u]==u ? u : root(fa[u]) );

}

void join(int u, int v){

fa[root(u)]=root(v);

}

void Scanf(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

cin >> t;

while(t--){

cin >> n;

cin.ignore();

Reset();

string s;

int True= 0, False= 0, u, v;

while(getline(cin, s)){

if (s=="") break;

char kind= s[0];

string s1= "";

int i;

for(i=2; s[i] != ' '; i++)

s1 += s[i];

u=stoi(s1);

i++;

s1="";

for(i=i; s[i]; i++)

s1 += s[i];

v=stoi(s1);

if (kind == 'c'){

join(u, v);

}

else{

if (root(u) == root(v)){

True++;

}

else False++;

}

}

cout<<True<<","<<False<<"\n";

if (t>0) cout<<"\n";

}

}

int main(){

Scanf();

}

 

Solution UVA: 908 - Re-connecting Computer Sites

 

Problem:
https://onlinejudge.org/external/9/908.pdf

 

Suggest:

- Use kruskal algorithm

-> Number edge of kruskal in problem is old edge + new edge 

(high-speed lines = edge)

 

Code:

#include<bits/stdc++.h>

#define N 1000111

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

using namespace std;

int n,m,s1=0,m1,m2;

int fa[N];

struct Arr{

int u,v,w;

};

Arr a[N];

bool cmd(Arr a, Arr b){

return a.w < b.w;

}

int root(int u){

return fa[u]=( fa[u]==u ? u : root(fa[u]) );

}

void join(int u, int v){

fa[root(u)]=root(v);

}

void Scanf(){

s1= 0;

FOR(i, 1, n-1)

cin >> a[i].u >> a[i].v >> a[i].w;

FOR(i, 1, n-1)

s1 += a[i].w;

cin >> m1;

FOR(i, 1, m1)

cin >> a[i].u >> a[i].v >> a[i].w;

cin >> m2;

FOR(i, m1+1, m1+m2)

cin >> a[i].u >> a[i].v >> a[i].w;

m = m1 + m2;

}

void Reset(){

FOR(i, 1, n) fa[i]= i;

}

void Solve(){

cout<<s1<<"\n";

int ans=0;

FOR(i, 1, m)

if (root(a[i].u) != root(a[i].v)){

join(a[i].u, a[i].v);

ans+= a[i].w;

if (--n == 1) break;

}

cout<<ans<<"\n";

}

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

int cnt=0;

while(cin >> n){

if (cnt++ != 0){

cout<<"\n";

}

Scanf();

Reset();

sort(a+1, a+1+m, cmd); // m

Solve();

}

}

 

 

Solution UVA: 11034 - Ferry Loading IV

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11034 - Ferry Loading IV	Accepted	C++11	0.000	0.000	1133	12 mins ago

#include <bits/stdc++.h>

#define int long long

using namespace std;

int t, n, L;

int32_t main() {    

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    cin >> t;

    while(t--){

        cin >> L >> n; L*=100;

        bool isLeft= true;      

        queue<int> left, right;

        int x;

        string y;

        while(n--){

            cin >> x >> y;

            if (y=="left") left.push(x); else right.push(x);

        }

        int cnt= 0;

       

        while(not left.empty() or not right.empty()){

       

            cnt++;

            if (isLeft){

                isLeft= false;

                int ferry= 0;

                while (not left.empty() and ferry + left.front() <= L ){

                    ferry += left.front();

                    left.pop();

                }

            }

            else{

                isLeft= true;

                int ferry= 0;

                while (not right.empty() and ferry + right.front() <= L ){

                    ferry += right.front();

                    right.pop();

                }

            }

        }

        cout<<cnt<<"\n";

    }

}

Solution UVA: 10194 - Football (aka Soccer)

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10194 - Football (aka Soccer)	Accepted	C++11	0.000	0.000	1040	28 secs ago

Suggest:

- Use STL map + Struct (team football) + Sort by compare function (ranking)

#include<bits/stdc++.h>

using namespace std;

string s, fifa;

int t, m, n;

struct team{

    int point;

    int win;

    int lose;

    int tie;

    int goal_against;

    int goal_scored;

    int less_game;

    string name;

    string name_origin;

};

bool cmp(team x, team y){

    if (x.point > y.point) return true;

    if (x.point == y.point){

       

        if (x.win > y.win) return true;

        if (x.win == y.win){

           

            if (x.goal_scored - x.goal_against > y.goal_scored - y.goal_against) return true;

            if (x.goal_scored - x.goal_against == y.goal_scored - y.goal_against){

               

                if (x.goal_scored > y.goal_scored) return true;

                if (x.goal_scored == y.goal_scored){

                   

                    if (x.less_game < y.less_game) return true;

                    if (x.less_game == y.less_game ){

                       

                        string team1 = "", team2 = "";

                        for(auto val:x.name) team1 += tolower(val);

                       

                        for(auto val:y.name) team2 += tolower(val);

                       

                        return (team1 < team2);

                    }

                }

               

               

            }

        }

    }

    return false;

}

 

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    cin >> t;  cin.ignore();

   

    while(t--){

        getline(cin, fifa);

       

        cin >> n; cin.ignore();

       

       

        unordered_map<string, team> M;

       

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

       

            getline(cin, s);

            M[s].point= 0;

            M[s].win= 0;

            M[s].lose= 0;

            M[s].tie= 0;

            M[s].goal_against= 0;

            M[s].goal_scored= 0;

            M[s].less_game= 0;

            M[s].name = s;

        }

        cin >> m; cin.ignore();

       

       

       

       

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

            getline(cin, s);

            s+='#';

           

            string team1="", goal1="", goal2="", team2="";

            int kind = 1;

           

            for(int i=0; s[i]; i++){

                if (s[i]=='#') {kind++; continue;}

                if (s[i]=='@') {kind++; continue;}

               

                if (kind==1) team1 += s[i];

                if (kind==2) goal1 += s[i];

                if (kind==3) goal2 += s[i];

                if (kind==4) team2 += s[i];

            }

            int g1 = stoi(goal1);

            int g2 = stoi(goal2);

           

            M[team1].name = team1;

            M[team1].goal_scored += g1;

            M[team1].goal_against += g2;

            M[team1].point += (g1 > g2 ? 3 : 0);        

                M[team1].point += (g1 == g2 ? 1 : 0);  

            M[team1].win += (g1 > g2 ? 1 : 0);      

            M[team1].less_game += 1;

            M[team1].lose += (g1 < g2 ? 1 : 0);        

            M[team1].tie += (g1 == g2 ? 1 : 0);        

           

           

            M[team2].name = team2;

            M[team2].goal_scored += g2;

            M[team2].goal_against += g1;

            M[team2].point += (g2 > g1 ? 3 : 0);    

                M[team2].point += (g2 == g1 ? 1 : 0);  

            M[team2].win += (g2 > g1 ? 1 : 0);      

            M[team2].less_game += 1;

            M[team2].lose += (g2 < g1 ? 1 : 0);        

            M[team2].tie += (g2 == g1 ? 1 : 0);        

                   

        }

       

        vector<team> ranking;

        for(auto it=M.begin(); it!=M.end(); it++)

            ranking.push_back(it->second);

        sort(ranking.begin(), ranking.end(), cmp);

       

        cout<<fifa<<"\n";

        int rank= 0;

        for(auto x:ranking)

            cout<<++rank<<") "<<x.name<<" "<<x.point<<"p, "<<x.less_game<<"g ("<<x.win<<"-"<<x.tie<<"-"<<x.lose<<"), "<<x.goal_scored-x.goal_against<<"gd ("<<x.goal_scored<<"-"<<x.goal_against<<")"<<"\n";    

        if (t) cout<<"\n";

    }  

}