10511 - Councilling

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10511 - Councilling

Post by brianfry713 » Thu Feb 07, 2013 12:02 am

Impossible should have a period at the end.
Check input and AC output for thousands of problems on uDebug!

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 10511 - Councilling

Post by forthright48 » Thu Feb 07, 2013 8:53 am

Haha. Sorry about that. Thanks for noticing the bug. I fixed it but still WA. Maybe I should solve more Bipartite Matching problems and then come back to this later.
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 10511 - Councilling

Post by forthright48 » Sun Aug 17, 2014 6:38 pm

After 20 submission, I finally found out why I was getting WA. Guys, be careful. Each person will have unique name, BUT, a person name can be same as a party or club. A party name can also be same as club name. We have to count them as different.

1

a a a
b b b
c c c

Answer is
a a
b b
c c
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 10511 - Councilling

Post by nbacool2 » Mon Dec 08, 2014 1:15 am

Hi, fellas. I used Edmond-Karp's Max flow algorithm for solving the problem and hashing with open addressing for storing the strings of the clubs and parties. I solve the sample test caces correctly but I get WA on the judge. Any ideas what could be wrong?
GOT AC AND CODE REMOVED
Last edited by nbacool2 on Thu Dec 11, 2014 5:23 pm, edited 4 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10511 - Councilling

Post by brianfry713 » Tue Dec 09, 2014 12:26 am

If the last test case is Impossible, don't print a blank line after it.
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 10511 - Councilling

Post by nbacool2 » Tue Dec 09, 2014 12:52 pm

brianfry713 wrote:If the last test case is Impossible, don't print a blank line after it.
OK, I edited my code and fixed that but I still get WA :cry:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10511 - Councilling

Post by brianfry713 » Wed Dec 10, 2014 1:19 am

Input:

Code: Select all

1

a d q d b h
b g e k h r m w t n p
c h m n x v d w r b s l g k h u f j c p a q e o
d c r s e u k g c w l b a n d p q
e b g a
f e j s f q c l w u n i b o d
g i g
h f w a n o e g x d m k r q h t l s u f
i j i d x b s w j q f e t
j i p f q a i g s e j r b w v t u o n l m d h x
k l u w h
l f f h l t k n a w
m i k o h e l g t v x f b m r u w i q d n c j p
n h k l g w e c j
o f o t g v c f r b l p e m i h q u d s w x n j a
p e u c t v
q d s d o x
r b b c f h r n d l v p w s a k t i
s h r k i q s o h v l m b d
t d u b w d s a n f v o t x p k q h e c l r i j g m
u d s c n g h b a q x j p u
v f x o g l m k t i n w j s u d p a r e h
w b f e j x n b a d g w o c v l r p h i k m
x g k g j w f x b t c u q m v a o d e
y a i
AC output:

Code: Select all

a d
b e
c k
d r
f b
g g
h m
i t
j p
k h
l n
m v
n w
o q
p u
q x
r s
s l
t f
u c
v j
w a
x o
y i
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 10511 - Councilling

Post by nbacool2 » Wed Dec 10, 2014 11:34 pm

I made some changes to my code (I updated my previous post with the code) and my program produces a correct output for your test case but I still get WA. This starts getting so annoying :roll:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10511 - Councilling

Post by brianfry713 » Thu Dec 11, 2014 2:03 am

Input:

Code: Select all

1

a a a
b b a
c c a
Output should be Impossible.
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 10511 - Councilling

Post by nbacool2 » Thu Dec 11, 2014 5:24 pm

brianfry713, you're awesome, dude. Thanks a lot :) . Got AC

cshung_test
New poster
Posts: 4
Joined: Mon Sep 29, 2014 6:25 pm

Re: 10511 - Councilling

Post by cshung_test » Sat Jan 03, 2015 1:26 am

Beware of input where a club is listed twice in the club list.

PersonA PartyA ClubA ClubA

After taking care of this I've got AC.

Original code and analysis deleted after AC

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 10511 - Councilling

Post by BlackBeard » Wed Mar 02, 2016 4:20 pm

I tried max flow algorithm, but got WA.
My algo:
source->every club(capacity=1);
clubs->their people(capacity=1);
people->their party(capacity=1);
party->sink(capacity=(Club numbers-1)/2);
if(flow!=club_number) print "Impossible" else, print solution.

I think the algorithm is correct and tried all the above inputs. Please help... :(

Code: Select all

#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define scs(x) scanf("%s",x)
#define pr(x) printf("%d",x)
#define prn(x) printf("%d\n",x)
#define memc(x,y) memcpy(&x,&y,sizeof(x))
#define mems(x,y) memset(x,y,sizeof(x))
#define fli() freopen("in.txt","r",stdin)
#define flo() freopen("out.txt","w",stdout)
#define rep(i,v) for(int i=0;i<v;i++)
#define Repe(i,x,v) for(int i=x;i<=v;i++)
#define repv(i,x) for(auto i=x.begin();i!=x.end();i++)
#define reprv(i,x) for(auto i=x.rbegin();i!=x.rend();i++)
#define what_is(x) cerr << #x << " is " << x << endl
#define pb push_back
#define bl putchar('\n')
#define gcc getchar()
#define pcc putchar
#define si size
#define fi first
#define se second
#define MAX 3050
#define source 3010
#define sink 3011
typedef long long ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef std::pair<int,int> ii;
using namespace std;

int graph[MAX][MAX],r_graph[MAX][MAX],parent[MAX],node_no,edge_no,ans;
bool visited[MAX],al[MAX][MAX];
char st[100],nm[100],pr[100],cl[100];
int nm_id,pr_id,cl_id  ,name,party,club;
map<string,int>pr_node,cl_node;
vector<ii>com;
vector<pair<string,string>>coms;

bool bfs(int s, int t){
    memset(visited, 0, sizeof(visited));
    queue <int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty()){
        int u = q.front();
        q.pop();

        for (int v=0; v<cl_id; v++){
            if (visited[v]==false && r_graph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
        for (int v=1000; v<nm_id; v++){
            if (visited[v]==false && r_graph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
        for (int v=2000; v<pr_id; v++){
            if (visited[v]==false && r_graph[u][v] > 0){
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
        if(visited[t]==0 and r_graph[u][t]>0){
            visited[t]=1;
            parent[t]=u;
            break;
        }
    }

    return (visited[t] == true);
}

int edmonds_karp(int s, int t){
    int u, v;

    memc(r_graph,graph);

    int max_flow = 0;

    while (bfs(s, t)){
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v]){
            u = parent[v];
            path_flow = min(path_flow, r_graph[u][v]);
        }

        for (v=t; v != s; v=parent[v]){
            u = parent[v];
            r_graph[u][v] -= path_flow;
            r_graph[v][u] += path_flow;
        }
        max_flow += path_flow;
    }

    return max_flow;
}

void reset(){
    com.clear();
    coms.clear();
    pr_node.clear();
    cl_node.clear();
    mems(graph,0);
    mems(r_graph,0);
    mems(parent,-1);
    mems(al,0);
}

int main(){
//    fli();
    int t,u,v,w;
    sc(t);
    gcc;
    gcc;
    while(t--){
        reset();
        nm_id=1000;
        pr_id=2000;
        cl_id=0;
        while(gets(st)){
            if(strlen(st)==0)break;
            stringstream ss(st);
            ss>>nm;
            name=nm_id++;
            ss>>pr;
            if(pr_node.find(pr)==pr_node.end()){
                party=pr_id;
                pr_node[pr]=pr_id++;
            }else{
                party=pr_node[pr];
            }
            graph[name][party]=1;
            graph[party][sink]=1;
            while(ss>>cl){
                if(cl_node.find(cl)==cl_node.end()){
                    club=cl_id;
                    cl_node[cl]=cl_id++;
                }else{
                    club=cl_node[cl];
                }
                graph[source][club]=1;
                graph[club][name]=1;
                al[club][name]=1;
                com.pb({club,name});
                coms.pb({cl,nm});
            }
        }
        w=(cl_node.si()-1)/2;
        repv(i,pr_node){
            graph[i->se][sink]=w;
        }
        ans=edmonds_karp(source,sink);
        if(ans!=cl_node.si()){
            puts("Impossible.");
        }else{
            rep(i,com.si()){
                if( r_graph[com[i].fi][com[i].se]==0 and al[com[i].fi][com[i].se] ){
                    printf("%s %s\n",coms[i].se.c_str(),coms[i].fi.c_str());
                }
            }
        }

        if(t) bl;
    }
    return 0;
}

Post Reply

Return to “Volume 105 (10500-10599)”