## 11390 - The Sultan's Feast

Moderator: Board moderators

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

### 11390 - The Sultan's Feast

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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
AC. Thanks!

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
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
can somebody help me out?

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:
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
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

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;
}
for(i=1;i<=n;i++)
for(scanf("%d %d",&graph_main[i].like_val,&sz),j=0;j<sz;j++)
{
scanf("%d",&x);
}
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++)
}
return 0;
}

void dfs_rev(int i)
{
graph_rev[i].v_status=VISITED;
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;
}

void dfs_scc(int i)
{
scc[i].v_status=VISITED;
post[indx++]=i;
}

void dfs_MaxSum(int i)
{
scc[i].v_status=BEING_VISITED;
temp+=scc[i].like_val;
}``````
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

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

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

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

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;
}
for(i=1;i<=n;i++)
for(scanf("%d %d",&graph_main[i].like_val,&sz),j=0;j<sz;j++)
{
scanf("%d",&x);
}
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++)
}
return 0;
}

void dfs_rev(int i)
{
graph_rev[i].v_status=VISITED;
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;
}

void dfs_scc(int i)
{
scc[i].v_status=VISITED;
post[indx++]=i;
}

void dfs_MaxSum(int i)
{
scc[i].v_status=BEING_VISITED;
temp+=scc[i].like_val;
}
``````
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

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

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;
}
for(i=1;i<=n;i++)
for(scanf("%d %d",&graph_main[i].like_val,&sz),j=0;j<sz;j++)
{
scanf("%d",&x);
}
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++)
}
return 0;
}

void dfs_rev(int i)
{
graph_rev[i].v_status=VISITED;
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;
}

void dfs_scc(int i)
{
scc[i].v_status=VISITED;
post[indx++]=i;
}

void dfs_MaxSum(int i)
{
scc[i].v_status=BEING_VISITED;
temp+=scc[i].like_val;