12442 - Forwarding Emails

brianfry713 · Post by **brianfry713** » Tue Feb 28, 2012 10:57 am

Here's some random input:

My AC code produced this output in less than 0.2 seconds:

Code: Select all

Case 1: 4068

mathgirl · Post by **mathgirl** » Mon May 07, 2012 6:21 pm

My code produces the same output as above, but I m getting TLE. Any suggestions ?

Code: Select all

#include<iostream>

using namespace std;

int main()
{
	int t;
	cin >> t;
	int j = 1;
	while(j<=t)
	{
		int n;
		cin >> n;
		int forward[50001];
		int a;
		for(int i=1;i<=n;i++)
		{
			cin >> a;
			cin >> forward[a];
		}

		int len[50001] = {0};

		int high = 0,answer = 0;
		for(int i=1;i<=n;i++)
		{
			int start = forward[i],count = 1;
			bool cycle[50001] = {false};
		
			if(!len[i]) 
			{
				cycle[i] = true;
				while(!cycle[start])
				{
					cycle[start] = true;
					start = forward[start];
					count++;
				}

				if(start == i)
				{
					for(int j=1;j<=n;j++)
					{
						if(cycle[j])
							len[j] = count;
					}
				}
				else
				{
					len[i] = count;
				}

				if(count > high)
				{
					high = count;
					answer = i;
					if(count == (n-1))
						break;
				}
			}
		}

		cout << "Case " << j << ": " << answer;
		cout << "\n";

		j++;
	}
	return 0;
}

brianfry713 · Post by **brianfry713** » Tue May 08, 2012 12:08 am

Your code doesn't match the sample I/O.

mathgirl · Post by **mathgirl** » Tue May 08, 2012 8:31 am

Ok. I have made modifications, i checked my output with sample I/O and the input given by u. Is there any tricky input? I m still getting TLE.

Code: Select all

#include<iostream>
#include<vector>
#include <time.h>

using namespace std;

int main()
{
	int t;
	cin >> t;
	int j = 1;
	while(j<=t)
	{
		int n;
		cin >> n;
		int forward[50001];
		int a;
		for(int i=1;i<=n;i++)
		{
			cin >> a;
			cin >> forward[a];
		}

		int len[50001] = {0};

		int high = 0,answer = 0;
		for(int i=1;i<=n;i++)
		{
			int start = i,count = 0;
			bool cycle[50001] = {false};
			vector<int> temp;
			
			if(!len[i]) 
			{
				while(!cycle[start])
				{
					if(len[start])
					{	
						count = count + len[start] + 1;
						break;
					}
					cycle[start] = true;
					temp.push_back(start);
					count++;
					len[start] = count;
					start = forward[start];
				}

				if(start == i)
				{
					if(count > high)
					{
						high = count;
						answer = i;
					}

					for(int j=0;j<temp.size();j++)
					{
						len[temp[j]] = count-1;
					}
				}
				else
				{
					for(int j=0;j<temp.size();j++)
					{
						len[temp[j]] = count - len[temp[j]];
						if(len[temp[j]] > high)
						{
							high = len[temp[j]];
							answer = temp[j];
						}
					}
				}
			}

			if(high == (n-1))
				break;
		}

		cout << "Case " << j << ": " << answer;
		cout << "\n";

		j++;
	}
	
	return 0;
}

brianfry713 · Post by **brianfry713** » Wed May 09, 2012 9:26 pm

Create a test case with N=50000 and all Martians in a circle forwarding the email to the person on it's right. The output should be 1. My AC code handles that case on my machine in 0.16 sec, your code takes 3.38 sec.

mathgirl · Post by **mathgirl** » Fri May 11, 2012 7:25 pm

I got AC in 0.416 sec, but I m interested to know how i can improve my algo. Is there any particular technique to be used ? I read about centrality in social networks. It sounded quite similar to this problem.

brianfry713 · Post by **brianfry713** » Sat May 12, 2012 6:34 am

I got AC in 0.088 sec with a recursive solution checking for cycles. If you're concerned about runtime, scanf and printf are faster than cin and cout.

ycmario · Post by **ycmario** » Fri Jun 15, 2012 3:41 am

In fact, you don't need recursion, since there is only one edge out of each vertex, you can use a while loop.

brianfry713 · Post by **brianfry713** » Fri Jul 05, 2013 12:17 pm

Input:

Code: Select all

Output should be:

Code: Select all

Case 1: 2

brianfry713 · Post by **brianfry713** » Fri Jul 05, 2013 10:54 pm

Input:

Code: Select all

AC output:

Code: Select all

Case 1: 13
Case 2: 10
Case 3: 18
Case 4: 21
Case 5: 22
Case 6: 2
Case 7: 2
Case 8: 11
Case 9: 6
Case 10: 10

brianfry713 · Post by **brianfry713** » Mon Jul 08, 2013 11:09 am

Input:

Code: Select all

output should be:

Code: Select all

Case 1: 4

alexiago · Post by **alexiago** » Sat Aug 17, 2013 12:44 am

I tried to solve this problem using DFS, starting a new iteration at each vertex and counting the max distance, I thought it would be enough as it completes within 1 sec on my laptop but I'm getting TLE. I tried another approach, starting at a vertex that hasn't been calculated its distance, I visit every neighbour until a visited node is found (i.e. cycle), and sum up the current distance to the cycle distance, but this approach has a problem when a larger sequence contains the cycle (it calculates de cycle again) so it would require to verify if the cycle it found was part of the same sequence (not sure if doing that everytime would give another TLE).
Anyway, what's the approach you used and what's the trick to pass this problem without TLE?

brianfry713 · Post by **brianfry713** » Mon Aug 19, 2013 10:37 pm

DFS with cycle checking. It should run in O(N).

alexiago · Post by **alexiago** » Wed Sep 04, 2013 11:37 pm

My solution was accepted using this algorithm:

Find cycles using DFS and store the cycle length for every node on the cycle, for the graph below their distances would be {3, 3, 3}
1 2
2 3
3 1

If a larger path starts before a cycle, the starting distance should be reversed and include the cycle length so the starting node has the largest length, having their distances as { 5, 4, 3, 3, 3} instead of {1, 2, 3, 4, 5} - and cycles keep their cycle length not the max length.
1 2
2 3
3 4
4 5
5 3

Finally, find the max distance and print the index.

Saminur Islam · Post by **Saminur Islam** » Tue Dec 10, 2013 12:16 pm

i cant understand why i am getting RE ..... i cant find the bug of the code..... any help would be appreciated

Code: Select all

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<list>
#include<utility>
#include<fstream>
#include<cmath>
using namespace std;
list<int> adj[50005];
bool visited[50005];
int counts;
void DFS_visit(int v)
{
    list<int> ::iterator it;
    if(visited[v]) return;
    if(!visited[v])
    {
        visited[v]=true;
        counts++;
    }
    for(it=adj[v].begin();it!=adj[v].end();++it)
    {
        if(!visited[(*it)])
        {
            DFS_visit(*it);
        }
    }
}

int main()
{
    //freopen("i.txt","r",stdin);
    int i,j,k,N;
    int T,P1,P2;
    cin>>T;
    for(i=1;i<=T;i++)
    {
        cin>>N;
        for(j=0;j<50005;j++)
        {
            adj[j].clear();
        }
        for(j=0;j<N;j++)
        {
            scanf("%d %d",&P1,&P2);
            adj[P1-1].push_back(P2-1);
        }
        int MR=-1;
        int Email=0;
        for(j=0;j<N;j++)
        {
            memset(visited,false, sizeof visited);
            counts=0;
            DFS_visit(j);
            if(counts>MR)
            {
                MR=counts;
                Email=j;
            }
            if(MR==counts)
            {
                if(Email<j) Email=Email;
                else Email=j;
            }
        }
        printf("Case %d: %d\n",i,Email+1);
    }
    return 0;
}

OJ Board

12442 - Forwarding Emails

12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails

Re: 12442 - Forwarding Emails