192 - Synchronous Design

All about problems in Volume 1. 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
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Apr 06, 2002 2:08 pm

Can someone explain this to me:
What is "The signal delay introduced between two synchronous nodes"? Only the signal delay between two nodes marked with 's' or the signal delay between two nodes not marked with 'a' (that means also between 'i' and 'o').
I am also wondering why in the text the message "Synchronous design ..." ends with period, and the sample output doesn't. What do I have to print?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Apr 06, 2002 2:58 pm

I have now found the mistake in my program. The delay time is measured from a node marked with 'i' or 's' to a node marked with 'o' or 's'. Between these nodes there should only be nodes marked with 'a'.
The message should be printed with the period.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

request for test data for 192 Synchronous Design

Post by epsilon0 » Fri Dec 13, 2002 3:13 pm

hello i'm working on 192, almost done. since the specs for this problem were not very clear, i'd appreciata some test data. thanks.

one of my question is what happens when there are "synchronous loops" i.e loops that have a synchronous node in them, how do you compute the longest path then? my thought is that you discard them, since the synchronous nodes get triggered once on clock edge and don't react to further changes on their inputs....

my other concern was wether a circuit could be assumed to be connex. in the sample input data one can see there's an unconnected input. what happens if the circuit is split in two parts, and one of them is not connected to any ouput but had an asynchronous loop... this shouldn't matter since it's not connected to outputs... i think i'm going too far in analysis there :P

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

192 - Synchronous Design

Post by epsilon0 » Fri Dec 13, 2002 4:07 pm

if you look at 192, you can see the sample output does not match the expected output:

Output

For each circuit in the input file, your output file should contain a line with one of the following messages:

"Synchronous design. Maximum delay: <ss>." if the circuit has a synchronous design.

<ss> should be replaced by the longest delay found on any path between two synchronous nodes.

.....

Sample Output

Synchronous design. Maximum delay: 28

------------------

clearly the trailing dot is missing from the sample output. i think this is the reason why i got WA. so what is the correct specification for this problem???

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri Dec 13, 2002 4:29 pm

There must be a point after delay's value, i.e.
[c] if (nmax > ct)
printf("Clock period exceeded.\n");
else
printf("Synchronous design. Maximum delay: %d.\n", nmax);
[/c]

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

help with 192

Post by epsilon0 » Fri Dec 13, 2002 4:45 pm

here's my source: i got WA

[c]#include <stdio.h>
#include <stdlib.h>

/* MAX macro */

#define MAX(a,b) ((a) > (b) ? (a) : (b))

/* node types */

#define INPUT 1
#define OUTPUT 2
#define SYNC 3
#define ASYNC 4

/* global stuff */

int *type;
int *delay;
int *network;
int n_nodes;


int has_cycle(int i, int *been_there)
{
int j;
int *been_there_too;
if (type != ASYNC)
return 0;
if (been_there)
return 1;
been_there_too = malloc(sizeof(int)*n_nodes);
memcpy(been_there_too,been_there,sizeof(int)*n_nodes);
been_there_too = 1;
for (j=0;j<n_nodes;j++)
if (network[n_nodes*i+j])
if (has_cycle(j, been_there_too))
{
free(been_there_too);
return 1;
}
free(been_there_too);
return 0;
}


int has_async_cycle()
{
int i;
int *been_there = malloc(sizeof(int)*n_nodes);
memset(been_there,0,sizeof(int)*n_nodes);
for (i=0;i<n_nodes;i++)
if (type == ASYNC)
if (has_cycle(i, been_there))
{
free(been_there);
return 1;
}
free(been_there);
return 0;
}


int longer(int i, int *been_there, int sum)
{
int j;
int max=0;
int tmp;
int *been_there_too;
if (been_there)
return 0;
if (type == OUTPUT)
return sum;
been_there_too = malloc(sizeof(int)*n_nodes);
memcpy(been_there_too,been_there,sizeof(int)*n_nodes);
been_there_too = 1;
if (type == ASYNC)
sum += delay;
for (j=0;j<n_nodes;j++)
if (network[n_nodes*i+j])
{
tmp = longer(j,been_there_too,sum);
max = MAX(max,tmp);
}
free(been_there_too);
return max;
}

int longer_path()
{
int i;
int max=0;
int tmp;
int *been_there = malloc(sizeof(int)*n_nodes);
memset(been_there,0,sizeof(int)*n_nodes);
for (i=0;i<n_nodes;i++)
if (type == INPUT)
{
tmp = longer(i,been_there,0);
max = MAX(max,tmp);
}
free(been_there);
return max;
}


int main()
{
int n_circuits;
int clock;
int n_wires;
int i,j;
int n1,n2;
char c;
int _longer;
scanf("%d\n",&n_circuits);
for (i=0;i<n_circuits;i++)
{
scanf("%d\n",&clock);
scanf("%d\n",&n_nodes);
type = malloc(sizeof(int)*n_nodes);
delay = malloc(sizeof(int)*n_nodes);
network = malloc(sizeof(int)*n_nodes*n_nodes);
memset(network,0,sizeof(int)*n_nodes*n_nodes);
for (j=0;j<n_nodes;j++)
{
scanf("%c %d\n",&c, &(delay[j]));
switch(c)
{
case 'i': type[j] = INPUT; break;
case 'o': type[j] = OUTPUT; break;
case 's': type[j] = SYNC; break;
case 'a': type[j] = ASYNC;
}
}
scanf("%d\n",&n_wires);
for (j=0;j<n_wires;j++)
{
scanf("%d %d\n",&n1,&n2);
network[n_nodes*n1+n2] = 1;
}
/* the work is done here */
if (has_async_cycle())
printf("Circuit contains cycle.\n");
else
if ((_longer = longer_path()) > clock)
printf("Clock period exceeded.\n");
else
printf("Synchronous design. Maximum delay: %d.\n",_longer);
/* done, clean and loop */
free(type);
free(delay);
free(network);
}
return 0;
}
[/c][/c]

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

192 Synchronous Design : is there a trick?

Post by epsilon0 » Mon Dec 23, 2002 8:27 am

hello,

i've programmed 192 last week, but it would get WA. i tested it a lot and it seems to give the right output in each case.

could you please give me special cases test data input/output or any trick there could be. thanx
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Mon Dec 23, 2002 8:30 am

see also my source code a few posts down the board:

http://acm.uva.es/board/viewtopic.php?t=1907
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

User avatar
sduval
New poster
Posts: 3
Joined: Sat May 24, 2003 2:53 am

Post by sduval » Sat May 24, 2003 9:45 pm

Hello,

Here is a simple set of data for problem 192 (Synchronous Design) :

1
30
11
i 0
i 0
i 0
i 0
i 0
o 0
a 2
a 7
s 0
a 4
a 10
12
0 7
1 10
2 10
3 6
4 6
10 7
7 8
10 8
6 9
8 9
9 5
9 10


and the corresponding output

Synchronous design. Maximum delay: 23.

Loops containing synchronous nodes should'nt be considered. You can't
pass through a synchronous node.
The circuit may not be connex.

Hope this help... :D

riisiingsun
New poster
Posts: 4
Joined: Fri May 18, 2007 12:03 pm
Location: Bangladesh

please Help me...output limit exceed in prob 192

Post by riisiingsun » Fri May 18, 2007 9:07 pm

can any one tell me what is the problem with my code? why it is showing output limit exceed? :evil:

[/code]
#include<stdio.h>

void main()
{
char ch,str1[2000000];
long int i;

while(scanf(" %[^\n]",str1)==1)
{
for(i=0;str1!=NULL;i++)
{
if(str1=='a' || str1=='A' || str1=='e'|| str1=='E' || str1=='i' || str1=='I' || str1=='o' || str1=='O' || str1=='u' || str1[i]=='U')
{
while((str1[i]<64 && str1[i]>91) || (str1[i]>96 && str1[i]<123))
{
printf("%c",str1[i]);
i++;
}
i--;
printf("ay");
}

else if((str1[i]<64 && str1[i]>91) || (str1[i]>96 && str1[i]<123))
{
ch=str1[i];
i++;
while((str1[i]<64 && str1[i]>91) || (str1[i]>96 && str1[i]<123))
{
printf("%c",str1[i]);
i++;
}
i--;
printf("%cay",ch);
}
else
printf("%c",str1[i]);
}
printf("\n");
}
}
R!!$!!NG$UN

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 192 - Synchronous Design

Post by metaphysis » Fri Mar 25, 2016 6:01 pm

WA, can anyone give me some critical test data?

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INPUT = 0, OUTPUT = 1, SYN = 2, ASYN = 3;
const string typeText = "iosa";

struct vertex
{
	int index, delay, type;
};

vector < vertex > verties;
vector < int > parent, path;
vector < bool > discovered;
vector < vector < int > > edges;
int maximumDelay, maxNodes;
bool foundCycle = false;

void dfs(int start)
{
    if (foundCycle)
        return;

    discovered[start] = true;
    for (int i = 0; i < edges[start].size(); i++)
    {
        vertex v = verties[edges[start][i]];
        if (v.type == ASYN)
        {
            if (discovered[v.index] == false)
            {
                parent[v.index] = start;
                dfs(v.index);
            }
            else
            {
                if (parent[v.index] != start)
                {
                    foundCycle = true;
                    return;
                }
            }
        }
    }
}

bool findCycle()
{
    parent.clear();
    discovered.clear();
    
    parent.resize(verties.size());
    discovered.resize(verties.size());
    
    for (int i = 0; i < verties.size(); i++)
        if (verties[i].type == ASYN)
        {
            foundCycle = false;
            
            fill(parent.begin(), parent.end(), -1);
            fill(discovered.begin(), discovered.end(), false);
            
            dfs(i);
            
            if (foundCycle)
                return true;
        }
}

void forward(int v, int index)
{
    path[index] = v;
    
    if (index >= 1 && verties[path[index]].type != ASYN)
    {
        int tempMax = 0;       
        for (int i = 0; i <= index; i++)
            tempMax += verties[path[i]].delay;
        maximumDelay = max(tempMax, maximumDelay);
    }
    else
    {
        for (int i = 0; i < edges[v].size(); i++)
            forward(edges[v][i], index + 1);        
    }
}

void findMaximumDelay()
{
    path.resize(verties.size());
    maximumDelay = 0;
    for (int i = 0; i < verties.size(); i++)
        if (verties[i].type == INPUT || verties[i].type == SYN)
            forward(i, 0);
}

int main(int argc, char *argv[])
{
    int clock, circuits, delay, nodes, start, end, typeIndex;
    string type;
    
    cin >> circuits;
    while (circuits--)
    {
        cin >> clock >> nodes;
        
        verties.clear();
        edges.clear();
        edges.resize(nodes);
        
        for (int i = 0; i < nodes; i++)
        {
            cin >> type >> delay;
            typeIndex = (int)typeText.find(type);
            if (typeIndex == INPUT || typeIndex == OUTPUT || typeIndex == SYN)
                delay = 0;
            verties.push_back((vertex){i, delay, typeIndex});
        }
        
        int m;
        cin >> m;
        for (int i = 1; i <= m; i++)
        {
            cin >> start >> end;
            edges[start].push_back(end);
        }
          
        if (findCycle())
            cout << "Circuit contains cycle." << endl;
        else 
        {
            findMaximumDelay();
            if (maximumDelay > clock)
                cout << "Clock period exceeded." << endl;
            else
                cout << "Synchronous design. Maximum delay: " << maximumDelay << "." << endl;
        }
    }
    
	return 0;
}

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 192 - Synchronous Design

Post by metaphysis » Sun Mar 27, 2016 4:06 pm

I found my mistake, DFS is not proper for finding cycle in directed graph.

Post Reply

Return to “Volume 1 (100-199)”