11390 - The Sultan

Moderator: Board moderators

11390 - The Sultan

The problem description is bad. The constraint 1 <= ri <= N-1 is wrong (even in the sample input, some ri = 0). I am also not sure whether I understand the meaning of ri correctly. Can anyone give some hints on how to solve this problem?
tobby
Learning poster

Posts: 95
Joined: Fri Dec 30, 2005 3:31 pm

The constraint 1 <= ri <= N-1 is wrong (even in the sample input, some ri = 0).

Yes. It should be 0 <= ri <= N-1.

I am also not sure whether I understand the meaning of ri correctly.

For example:
Code: Select all
`51 2 2 4-2 2 4 53 1 5-4 05 1 1`

If you invite person1, he also invites person2 and person4. Then person2 invites person4(already invited by persion1) and person 5.
So if you invited person1, then preson1,2,4 and 5 comes.

Hint :
I don't think that greedy algorithm works.
-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

AC. Thanks!
tobby
Learning poster

Posts: 95
Joined: Fri Dec 30, 2005 3:31 pm

Another hint?? i cant figure it out, i just see that you can get an acyclic graph with the component digraph.... :'(... Thanks!, Eric.
sonyckson
New poster

Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

can somebody help me out?

ani_mitr86
New poster

Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

In my solution I first ran an algorithm for finding strongly connected components to get an equivalent problem on a DAG. This step should not even be necessary, but it might give a better time in the rank list.

I thought about the equivalent problem on a DAG for some time and was not able to come up with an algorithm that ran in polynomial time (does anybody know if this is possible?). So instead I just coded a standard backtracking algorithm, where I kept track of the best solution so far and pruned away whenever I knew that we could never get a better solution than the current best. The pruning I did was not even very clever.
For help with problems, visit http://www.uvatoolkit.com/
greve
New poster

Posts: 27
Joined: Tue May 29, 2007 8:52 pm

thanks ..

i will try to implement the idea
ani_mitr86
New poster

Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

Re: 11390 - The Sultan

can some1 help me plz? i can't find the bug in my code, and not sure of the logic too

i first found out the SCCs of the graph. then made a topological sort of the SCCs. then for each of the SCCs, i found out the sum "like value" keeping track of which of the SCCs are going to be added to the result. is this approach correct? if it is, then what's wrong in the code? plz help some1. stucked with this problem

Code: Select all
`#include<cstdio>#include<vector>#define UNVISITED 0#define VISITED 1#define BEING_VISITED 2void dfs_rev(int);void dfs_main(int);void dfs_scc(int);void dfs_MaxSum(int);struct graph { char v_status; int like_val,scc_num; std::vector<int>adj_list; }graph_main[101],graph_rev[101],scc[101];int post[100],indx,temp;int main(){    //freopen("input.txt","r",stdin);    int test,test_num=1,n,sz,x,sum,scc_num,i,j; bool flag=false;    for(scanf("%d",&test);test_num<=test;test_num++,flag=false)    {        scanf("%d",&n);        for(i=1;i<=n;i++)        {            graph_main[i].v_status=graph_rev[i].v_status=graph_main[i].scc_num=0;            graph_main[i].adj_list.clear();            graph_rev[i].adj_list.clear();        }        for(i=1;i<=n;i++)            for(scanf("%d %d",&graph_main[i].like_val,&sz),j=0;j<sz;j++)            {                scanf("%d",&x);                graph_main[i].adj_list.push_back(x);                graph_rev[x].adj_list.push_back(i);            }        for(indx=0,i=1;i<=n;i++)            if(graph_rev[i].v_status==UNVISITED)                dfs_rev(i);        for(indx=0,i=n-1;i>=0;i--)            if(graph_main[post[i]].v_status==UNVISITED)            {                ++indx;                scc[indx].v_status=scc[indx].like_val=0;                dfs_main(post[i]);            }        for(i=1,scc_num=indx,indx=0;i<=scc_num;i++)            if(scc[i].v_status==UNVISITED)                dfs_scc(i);        for(sum=i=0;i<indx;i++,temp=0)        {            scc[post[i]].v_status=UNVISITED;            dfs_MaxSum(post[i]);            if(temp>=0)            {                for(flag=true,sum+=temp,j=0;j<=i;j++)                    if(scc[post[j]].v_status==BEING_VISITED)                        scc[post[j]].v_status=VISITED;            }            else                for(j=0;j<=i;j++)                    if(scc[post[j]].v_status==BEING_VISITED)                        scc[post[j]].v_status=UNVISITED;        }        printf("Case #%d: ",test_num);        flag?printf("%d\n",sum):printf("Alas, sultan can't invite anyone!\n");        for(i=1;i<=scc_num;i++)            scc[i].adj_list.clear();    }    return 0;}void dfs_rev(int i){    graph_rev[i].v_status=VISITED;    for(int j=0,sz=graph_rev[i].adj_list.size();j<sz;j++)        if(graph_rev[graph_rev[i].adj_list[j]].v_status==UNVISITED)            dfs_rev(graph_rev[i].adj_list[j]);    post[indx++]=i;}void dfs_main(int i){    graph_main[i].v_status=VISITED;    graph_main[i].scc_num=indx;    scc[indx].like_val+=graph_main[i].like_val;    for(int j=0,sz=graph_main[i].adj_list.size();j<sz;j++)        if(graph_main[graph_main[i].adj_list[j]].v_status==UNVISITED)            dfs_main(graph_main[i].adj_list[j]);        else if(graph_main[graph_main[i].adj_list[j]].scc_num!=indx)            scc[indx].adj_list.push_back(graph_main[graph_main[i].adj_list[j]].scc_num);}void dfs_scc(int i){    scc[i].v_status=VISITED;    for(int j=0,sz=scc[i].adj_list.size();j<sz;j++)        if(scc[scc[i].adj_list[j]].v_status==UNVISITED)            dfs_scc(scc[i].adj_list[j]);    post[indx++]=i;}void dfs_MaxSum(int i){    scc[i].v_status=BEING_VISITED;    temp+=scc[i].like_val;    for(int j=0,sz=scc[i].adj_list.size();j<sz;j++)        if(scc[scc[i].adj_list[j]].v_status==UNVISITED)            dfs_MaxSum(scc[i].adj_list[j]);}`
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11390 - The Sultan

Input:
Code: Select all
`133392 1 2-3314 02772 1 2`

AC output:
Code: Select all
`Case #1: 2850`
brianfry713
Guru

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

Re: 11390 - The Sultan

ow, there's some fault in the logic. a topological sort of the SCC DAG and then processing them sequentially won't give the correct result always. Sir, what should be the correction? can't find the way
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11390 - The Sultan

I tested your code on a few hundred thousand random inputs, and all matched my AC code except for the case I posted. Try fixing your code for that case and post the updated code if you can't get it AC.
brianfry713
Guru

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

Re: 11390 - The Sultan

nope sir, i couldn't get AC. i modified my code by processing the topological sort of the SCC DAG again after the 1st run to check whether any possible sums remained. this way my code passed your given I/O set. but still it gets WA
i kept the previous code here for convenience of checking whether the correction approach is correct

Code: Select all
`#include<cstdio>#include<vector>#define UNVISITED 0#define VISITED 1#define BEING_VISITED 2void dfs_rev(int);void dfs_main(int);void dfs_scc(int);void dfs_MaxSum(int);struct graph { char v_status; int like_val,scc_num; std::vector<int>adj_list; }graph_main[101],graph_rev[101],scc[101];int post[100],indx,temp;int main(){    int test,test_num=1,n,sz,x,sum,scc_num,i,j; bool flag=false;    for(scanf("%d",&test);test_num<=test;test_num++,flag=false)    {        scanf("%d",&n);        for(i=1;i<=n;i++)        {            graph_main[i].v_status=graph_rev[i].v_status=graph_main[i].scc_num=0;            graph_main[i].adj_list.clear();            graph_rev[i].adj_list.clear();        }        for(i=1;i<=n;i++)            for(scanf("%d %d",&graph_main[i].like_val,&sz),j=0;j<sz;j++)            {                scanf("%d",&x);                graph_main[i].adj_list.push_back(x);                graph_rev[x].adj_list.push_back(i);            }        for(indx=0,i=1;i<=n;i++)            if(graph_rev[i].v_status==UNVISITED)                dfs_rev(i);        for(indx=0,i=n-1;i>=0;i--)            if(graph_main[post[i]].v_status==UNVISITED)            {                ++indx;                scc[indx].v_status=scc[indx].like_val=0;                dfs_main(post[i]);            }        for(i=1,scc_num=indx,indx=0;i<=scc_num;i++)            if(scc[i].v_status==UNVISITED)                dfs_scc(i);        for(sum=i=0;i<indx;i++,temp=0)        {            scc[post[i]].v_status=UNVISITED;            dfs_MaxSum(post[i]);            if(temp>=0)            {                for(flag=true,sum+=temp,j=0;j<=i;j++)                    if(scc[post[j]].v_status==BEING_VISITED)                        scc[post[j]].v_status=VISITED;            }            else                for(j=0;j<=i;j++)                    if(scc[post[j]].v_status==BEING_VISITED)                        scc[post[j]].v_status=UNVISITED;        }        for(i=0;i<indx;i++)        {            if(scc[post[i]].v_status==UNVISITED)            {                dfs_MaxSum(post[i]);                if(temp>=0)                {                    for(flag=true,sum+=temp,j=0;j<=i;j++)                        if(scc[post[j]].v_status==BEING_VISITED)                            scc[post[j]].v_status=VISITED;                }                else                    for(j=0;j<=i;j++)                        if(scc[post[j]].v_status==BEING_VISITED)                            scc[post[j]].v_status=UNVISITED;                temp=0;            }        }        printf("Case #%d: ",test_num);        flag?printf("%d\n",sum):printf("Alas, sultan can't invite anyone!\n");        for(i=1;i<=scc_num;i++)            scc[i].adj_list.clear();    }    return 0;}void dfs_rev(int i){    graph_rev[i].v_status=VISITED;    for(int j=0,sz=graph_rev[i].adj_list.size();j<sz;j++)        if(graph_rev[graph_rev[i].adj_list[j]].v_status==UNVISITED)            dfs_rev(graph_rev[i].adj_list[j]);    post[indx++]=i;}void dfs_main(int i){    graph_main[i].v_status=VISITED;    graph_main[i].scc_num=indx;    scc[indx].like_val+=graph_main[i].like_val;    for(int j=0,sz=graph_main[i].adj_list.size();j<sz;j++)        if(graph_main[graph_main[i].adj_list[j]].v_status==UNVISITED)            dfs_main(graph_main[i].adj_list[j]);        else if(graph_main[graph_main[i].adj_list[j]].scc_num!=indx)            scc[indx].adj_list.push_back(graph_main[graph_main[i].adj_list[j]].scc_num);}void dfs_scc(int i){    scc[i].v_status=VISITED;    for(int j=0,sz=scc[i].adj_list.size();j<sz;j++)        if(scc[scc[i].adj_list[j]].v_status==UNVISITED)            dfs_scc(scc[i].adj_list[j]);    post[indx++]=i;}void dfs_MaxSum(int i){    scc[i].v_status=BEING_VISITED;    temp+=scc[i].like_val;    for(int j=0,sz=scc[i].adj_list.size();j<sz;j++)        if(scc[scc[i].adj_list[j]].v_status==UNVISITED)            dfs_MaxSum(scc[i].adj_list[j]);}`
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11390 - The Sultan

Input:
Code: Select all
`271518 1 2-5269 0434 2 7 24608 1 2-3748 3 1 4 2-9929 2 1 71264 1 634569 1 36924 1 3-7758 0`

AC output:
Code: Select all
`Case #1: 857Case #2: 3735`
brianfry713
Guru

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

Re: 11390 - The Sultan

sorry sir. i couldn't fix my code. and my algo needs some correction. but can't implement the correction into code

for your last given I/O set, the sum like values of the SCCs and their traversal order(according to topological sort) is as below. eg. in the 1st I/O set, for the 2nd SCC, the like value gets negative (4608 - 5269). same goes for the 3rd SCC (1518 - 5269). but if both the SCC sets(2,3) are invited, then the sum like value is positive. here i'm facing the problem. can't fix it appropriately how to handle these situations. sir i need some help in the correction of the code.

Code: Select all
`                                        Connected SCCsSCC num : 1, SCC_like_val :  -5269, 1 -> SCC num : 2, SCC_like_val :   4608, 2 -> 1, SCC num : 3, SCC_like_val :   1518, 3 -> 1, SCC num : 4, SCC_like_val :  -8665, 4 -> 3, SCC num : 5, SCC_like_val :    434, 5 -> 4, 1, SCC num : 6, SCC_like_val :  -3748, 6 -> 3, 2, 1, Traversal Order of the SCCs : 1, 2, 3, 4, 5, 6Case #1: Alas, sultan can't invite anyone!                                        Connected SCCsSCC num : 1, SCC_like_val :  -7758, 1 -> SCC num : 2, SCC_like_val :   6924, 2 -> 1, SCC num : 3, SCC_like_val :   4569, 3 -> 1, Traversal Order of the SCCs : 1, 2, 3Case #2: Alas, sultan can't invite anyone!`

My Code

Code: Select all
`#include<cstdio>#include<vector>#define UNVISITED 0#define VISITED 1#define BEING_VISITED 2void dfs_rev(int);void dfs_main(int);void dfs_scc(int);void dfs_MaxSum(int);struct graph { char v_status; int like_val,scc_num; std::vector<int>adj_list; }graph_main[101],graph_rev[101],scc[101];int post[100],indx,temp;int main(){    //freopen("input.txt","r",stdin);    int test,test_num=1,n,sz,x,sum,scc_num,i,j; bool flag=false;    for(scanf("%d",&test);test_num<=test;test_num++,flag=false)    {        scanf("%d",&n);        for(i=1;i<=n;i++)        {            graph_main[i].v_status=graph_rev[i].v_status=graph_main[i].scc_num=0;            graph_main[i].adj_list.clear();            graph_rev[i].adj_list.clear();        }        for(i=1;i<=n;i++)            for(scanf("%d %d",&graph_main[i].like_val,&sz),j=0;j<sz;j++)            {                scanf("%d",&x);                graph_main[i].adj_list.push_back(x);                graph_rev[x].adj_list.push_back(i);            }        for(indx=0,i=1;i<=n;i++)            if(graph_rev[i].v_status==UNVISITED)                dfs_rev(i);        for(indx=0,i=n-1;i>=0;i--)            if(graph_main[post[i]].v_status==UNVISITED)            {                ++indx;                scc[indx].v_status=scc[indx].like_val=0;                dfs_main(post[i]);            }        for(i=1,scc_num=indx,indx=0;i<=scc_num;i++)            if(scc[i].v_status==UNVISITED)                dfs_scc(i);        for(sum=i=0;i<indx;i++,temp=0)        {            scc[post[i]].v_status=UNVISITED;            dfs_MaxSum(post[i]);            if(temp>=0)            {                for(flag=true,sum+=temp,j=0;j<=i;j++)                    if(scc[post[j]].v_status==BEING_VISITED)                        scc[post[j]].v_status=VISITED;            }            else                for(j=0;j<=i;j++)                    if(scc[post[j]].v_status==BEING_VISITED)                        scc[post[j]].v_status=UNVISITED;        }        printf("Case #%d: ",test_num);        flag?printf("%d\n",sum):printf("Alas, sultan can't invite anyone!\n");        for(i=1;i<=scc_num;i++)            scc[i].adj_list.clear();    }    return 0;}void dfs_rev(int i){    graph_rev[i].v_status=VISITED;    for(int j=0,sz=graph_rev[i].adj_list.size();j<sz;j++)        if(graph_rev[graph_rev[i].adj_list[j]].v_status==UNVISITED)            dfs_rev(graph_rev[i].adj_list[j]);    post[indx++]=i;}void dfs_main(int i){    graph_main[i].v_status=VISITED;    graph_main[i].scc_num=indx;    scc[indx].like_val+=graph_main[i].like_val;    for(int j=0,sz=graph_main[i].adj_list.size();j<sz;j++)        if(graph_main[graph_main[i].adj_list[j]].v_status==UNVISITED)            dfs_main(graph_main[i].adj_list[j]);        else if(graph_main[graph_main[i].adj_list[j]].scc_num!=indx)            scc[indx].adj_list.push_back(graph_main[graph_main[i].adj_list[j]].scc_num);}void dfs_scc(int i){    scc[i].v_status=VISITED;    for(int j=0,sz=scc[i].adj_list.size();j<sz;j++)        if(scc[scc[i].adj_list[j]].v_status==UNVISITED)            dfs_scc(scc[i].adj_list[j]);    post[indx++]=i;}void dfs_MaxSum(int i){    scc[i].v_status=BEING_VISITED;    temp+=scc[i].like_val;    for(int j=0,sz=scc[i].adj_list.size();j<sz;j++)        if(scc[scc[i].adj_list[j]].v_status==UNVISITED)            dfs_MaxSum(scc[i].adj_list[j]);}`
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11390 - The Sultan

As greve points out in this thread, you can use recursive backtracking and it is fast enough. My code gets AC in 0.14 sec.
brianfry713
Guru

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