11390 - The Sultan

[tobby]

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]

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]

AC. Thanks!

[sonyckson]

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]

can somebody help me out?

thanks in advance

[greve]

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]

thanks ..

i will try to implement the idea

[Scarecrow]

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]

Input:

Code: Select all

1

3
3392 1 2
-3314 0
2772 1 2

AC output:

Code: Select all

Case #1: 2850

[Scarecrow]

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]

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]

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]

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]

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]

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.