11390 - The Sultan's Feast

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

Moderator: Board moderators

Post Reply
tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

11390 - The Sultan's Feast

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?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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

5
1 2 2 4
-2 2 4 5
3 1 5
-4 0
5 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

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

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

AC. Thanks!

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

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
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

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

can somebody help me out?

thanks in advance

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

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.
For help with problems, visit http://www.uvatoolkit.com/

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

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

thanks ..

i will try to implement the idea

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

Re: 11390 - The Sultan

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]);
}
Do or do not. There is no try.

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

Re: 11390 - The Sultan

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

Input:

Code: Select all

1

3
3392 1 2
-3314 0
2772 1 2
AC output:

Code: Select all

Case #1: 2850
Check input and AC output for thousands of problems on uDebug!

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

Re: 11390 - The Sultan

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 :(
Do or do not. There is no try.

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

Re: 11390 - The Sultan

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.
Check input and AC output for thousands of problems on uDebug!

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

Re: 11390 - The Sultan

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]);
}
Do or do not. There is no try.

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

Re: 11390 - The Sultan

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
Check input and AC output for thousands of problems on uDebug!

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

Re: 11390 - The Sultan

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]);
}
Do or do not. There is no try.

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

Re: 11390 - The Sultan

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 113 (11300-11399)”