11390 - The Sultan's Feast

tobby · Post by **tobby** » Sun Jan 13, 2008 3:34 am

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?

rio · Post by **rio** » Sun Jan 13, 2008 9:34 am

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

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

tobby · Post by **tobby** » Sun Jan 13, 2008 12:04 pm

AC. Thanks!

sonyckson · Post by **sonyckson** » Mon Jan 14, 2008 5:39 am

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

ani_mitr86 · Post by **ani_mitr86** » Wed Jan 23, 2008 5:07 pm

can somebody help me out?

thanks in advance

greve · Post by **greve** » Wed Jan 23, 2008 5:27 pm

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.

ani_mitr86 · Post by **ani_mitr86** » Thu Jan 24, 2008 8:09 am

thanks ..

i will try to implement the idea

Scarecrow · Post by **Scarecrow** » Thu Apr 26, 2012 8:29 pm

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 2
void 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]);
}

brianfry713 · Post by **brianfry713** » Fri Apr 27, 2012 3:36 am

Input:

Code: Select all

AC output:

Code: Select all

Case #1: 2850

Scarecrow · Post by **Scarecrow** » Fri Apr 27, 2012 1:33 pm

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

brianfry713 · Post by **brianfry713** » Fri Apr 27, 2012 9:34 pm

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.

Scarecrow · Post by **Scarecrow** » Sat Apr 28, 2012 1:07 am

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 2
void 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]);
}

brianfry713 · Post by **brianfry713** » Mon Apr 30, 2012 10:23 pm

Input:

Code: Select all

2

7
1518 1 2
-5269 0
434 2 7 2
4608 1 2
-3748 3 1 4 2
-9929 2 1 7
1264 1 6

3
4569 1 3
6924 1 3
-7758 0

AC output:

Code: Select all

Case #1: 857
Case #2: 3735

Scarecrow · Post by **Scarecrow** » Wed May 02, 2012 2:56 pm

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 SCCs
SCC 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, 6


Case #1: Alas, sultan can't invite anyone!


                                        Connected SCCs
SCC 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, 3


Case #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 2
void 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]);
}

brianfry713 · Post by **brianfry713** » Fri May 04, 2012 3:47 am

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.

OJ Board

11390 - The Sultan's Feast

11390 - The Sultan's Feast

Re: 11390 - The Sultan

Re: 11390 - The Sultan

Re: 11390 - The Sultan

Re: 11390 - The Sultan

Re: 11390 - The Sultan

Re: 11390 - The Sultan

Re: 11390 - The Sultan

Re: 11390 - The Sultan