140 - Bandwidth

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

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 140 - bandwith

Post by @li_kuet »

I am getting TLE :(
How can i optimize my time ???

Code: Select all

AC :D
silly mistake :)
Didn't clear the vector thats why number of char get increased and caused TLE

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 140 - bandwith

Post by Sabiha_Fancy »

I am getting wrong answer for this problem. But i can't catch the error with my code. If anyone help i will be glad. #include<stdio.h>
#include<stdlib.h>
#include<string.h>

int flag[27],stock[10],order[10];
int graph[27][27];
int count,max,min_value,max_value;

void bandwidth()
{
int i,j,temp,f;
for(i=0; i<count; ++i)
{
for(j=0; j<count; ++j)
{
if(j != i)
{
if(graph[stock][stock[j]])
{
temp = j-i;
if(temp < 0)
temp = temp * (-1);
if(temp>max_value)
max_value = temp;
}
}
}
}
if(min_value>max_value)
{
min_value = max_value;
for(i=0; i<count; ++i)
{
order = stock;
}
}
else if(min_value == max_value)
{
f=0;
for(i=0; i<count; ++i)
{
if(stock < order)
{
f = 1;
break;
}
else if(stock == order)
continue;
else if(stock > order)
break;
}
if(f==1)
{
for(i=0; i<count; ++i)
{
order = stock[i];
}
}
}
}
void dfs(int i,int k)
{
int j;
if(k==count)
{
bandwidth();
max_value = 0;
return;
}
for(j=0; j<=max; ++j)
{
if(flag[j])
{
flag[j] = 0;
stock[k] = j;
dfs(j,k+1);
flag[j] = 1;
}
}
}

int main()
{
char s[100];
int len,i,j,k;
while(1)
{
gets(s);
if(s[0] == '#')
break;
len = strlen(s);
for(i=0; i<27; ++i)
{
flag[i] = 0;
for(j=0; j<27; ++j)
graph[i][j] = 0;
}
min_value = 1000;
max_value = 0;
count=0;
i=0;
while(i<len)
{
if(s[i]>='A' && s[i]<='Z')
{
if(flag[s[i]-'A']==0)
{
flag[s[i]-'A'] = 1;
count++;
max = i;
}
j = i+2;
for( ; s[j]!=';' ; ++j)
{
if(j>=len)
break;
if(s[j]>='A' && s[j]<='Z')
{
graph[s[i]-'A'][s[j]-'A'] = graph[s[j]-'A'][s[i]-'A'] = 1;
if(flag[s[j]-'A']==0)
{
flag[s[j]-'A'] = 1;
count++;
max = j;
}
}
}
i = j+1;
}
}
for(i=0; i<count; ++i)
{
stock[i] = order[i] = 0;
}
for(i=0; i<=max; ++i)
{
if(flag[i])
{
flag[i] = 0;
stock[0] = i;
dfs(i,1);
flag[i] = 1;
}
}
for(i=0; i<count; ++i)
{
printf("%c ",'A'+order[i]);
}
printf("-> %d\n",min_value);
}
return 0;
}
Fancy

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

Re: 140 - bandwith

Post by brianfry713 »

Input:

Code: Select all

A:D
#
AC output:

Code: Select all

A D -> 1
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 140 - bandwith

Post by Sabiha_Fancy »

Thank you for your reply.
Fancy

buiutripa
New poster
Posts: 6
Joined: Wed Oct 21, 2009 1:44 am

Re: 140 - bandwith

Post by buiutripa »

Does anyone still use this forum?

My code passes in all the test case of this thread, but gets WA. Can anyone identify the wrong part of my code? Or provide a test case in wich it's wrong?

Code: Select all

#include <cstdio>
#include <cstring>

#define max 9
#define char_ini 'A'

char s[max*max*max];
bool g[max][max], visited[max];
int sol[max], best_sol[max], pos[max], letters['Z' - 'A' + 1];
int bw_global, size = max;

int cost(int k) {
	int bw_local = 0;
	for (int i = 0; i < k; i++) {
		for (int j = i+1; j < k; j++) {
			int u = sol[i], v = sol[j];
			if (g[u][v] == true) {
				int bw_current = j-i;
				if (bw_current > bw_local)
					bw_local = bw_current;
			}
		}
	}
	return bw_local;
}

void update_solution(int bw_local) {
	bw_global = bw_local;
	for (int i = 0; i < size; i++)
		best_sol[i] = sol[i];
}

void bp(int k) {
	int c = cost(k);
	if (c >= bw_global)
		return;
	else if (k == size) {
		update_solution(c);
		return;
	}
	
	for (int i = 0; i < size; i++) {
		if (visited[i] == false){
			visited[i] = true;
			sol[k] = i;
			bp(k+1);
			visited[i] = false;
		}
	}
}

int make_map() {
	for (int i = 0; i < strlen(s); i++) {
		int u = s[i] - char_ini;
		letters[u] = true;
		i += 2;
		while (s[i] != ';' && i < strlen(s)) {
			int v = s[i] - char_ini;
			letters[v] = true;
			i++;
		}
	}
	
	int k = 0;
	for (int i = 0; i < 1+'Z'-char_ini; i++)
		if (letters[i] == true) {
			pos[k] = i;
			letters[i] = k;
			k++;
		}
	return k;
}

void make_graph() {
	for (int i = 0; i < strlen(s); i++) {
		int u = letters[s[i] - char_ini];
		i++; i++; // jump the ':'
		while (s[i] != ';' && i < strlen(s)) {
			int v = letters[s[i] - char_ini];
			g[u][v] = g[v][u] = true;
			i++;
		}
	}
}

bool input() {
	scanf("%s", s);
	if (strcmp(s, "#") == 0)
		return false;
	size = make_map();
	make_graph();
}

void solve() {
	bw_global = size*size*size*size;
	bp(0);
}

void output() {
	for (int i = 0; i < size; i++)
		printf("%c ", pos[best_sol[i]] + char_ini);
	printf("-> %d\n", bw_global);
}

void clear() {
	for (int i = 0; i < size; i++)
		visited[i] = false;
	for (int j = 0; j < size; j++)
		for (int i = 0; i < size; i++)
			g[j][i] = false;
	for (int i = char_ini; i < 'Z'; i++)
		letters[i-char_ini] = false;
}

int main() {
	clear();
	while (input()) {
		solve();
		output();
		clear();
	}
	return 0;
}

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

Re: 140 - bandwith

Post by brianfry713 »

Try input:

Code: Select all

A:Z
#
Check input and AC output for thousands of problems on uDebug!

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 140 - bandwith

Post by mostruash »

So what's wrong with my code (getting WA)? Passes all test cases here:

Code: Select all

#include <iostream>
#include <memory>
#include <string>
#include <list>
#include <sstream>
#include <cmath>

using namespace std;

#define MAX_NV 8
#define MAX_L 26

bool    edges[MAX_NV][MAX_NV];
int     map[MAX_L];
int     rmap[MAX_NV];

int     min_bandwidth;
string  min_order;

void split(string &s, char delim, list<string>& l) {
    stringstream ss(s);
    string item;
    while(getline(ss, item, delim)) {
        l.push_back(item);
    }
}

int toi(char c) {
    return c - 'A';
}

int calc_bandwidth(int order[MAX_NV], int n) {
    int max = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            if(edges[order[i]][order[j]] && max < abs(i-j)) {
                max = abs(i-j);
            }
        }
    }
    return max;
}

void backtrack(int order[MAX_NV], bool used[MAX_NV], int k, int n) {
    if(k == n) {
        int bandwidth = calc_bandwidth(order, n);
        if(bandwidth <= min_bandwidth) {
            stringstream ss;
            for(int i = 0; i < n; i++) {
                ss << (char)('A' + rmap[order[i]]);
                ss << " ";
            }
            ss << "-> " << bandwidth;
            
            string result = ss.str();
            
            if(bandwidth < min_bandwidth || result < min_order) {
                min_bandwidth = bandwidth;
                min_order = ss.str();
            }
        }
        return;
    }
    
    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            order[k] = i;
            used[i] = true;
            backtrack(order, used, k + 1, n);
            used[i] = false;
        }
    }
    
}

int main() {
    string graph;
    bool first = true;
    while(cin >> graph && graph != "#") {
        if(!first) cout << endl;
        else first = false;
        for(int i = 0; i < MAX_NV; i++) {
            rmap[i] = -1;
            for(int j = 0; j < MAX_NV; j++)
                edges[i][j] = false;
        }
        
        for(int i = 0; i < MAX_L; i++) {
            map[i] = -1;
        }
        
        min_bandwidth = 100;
        
        
        int nVertices = 0;
        list<string> records;
        split(graph, ';', records);
        
        for(auto it = records.begin(); it != records.end(); it++) {
            string s = *it;
            int v = toi(s[0]);
            map[v] = nVertices;
            rmap[nVertices] = v;
            nVertices++;
        }
        
        for(auto it = records.begin(); it != records.end(); it++) {
            string s = *it;
            int v = toi(s[0]);
            for(int i = 2; i < s.length(); i++) {
                int y = toi(s[i]);
                if(map[y] == -1) {
                    map[y] = nVertices;
                    rmap[nVertices] = y;
                    nVertices++;
                }
                edges[map[v]][map[y]] = true;
                edges[map[y]][map[v]] = true;
            }
        }
        
        int order[MAX_NV];
        bool used[MAX_NV];
        
        backtrack(order, used, 0, nVertices);
        cout << min_order;
    }
    return 0;
}

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

Re: 140 - bandwith

Post by brianfry713 »

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 140 - bandwith

Post by mostruash »

I tried that too, still WA.

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

Re: 140 - bandwith

Post by brianfry713 »

Post your updated code.
Check input and AC output for thousands of problems on uDebug!

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 140 - bandwith

Post by mostruash »

Thanks again.

Code: Select all

#include <iostream>
#include <memory>
#include <string>
#include <list>
#include <sstream>
#include <cmath>

using namespace std;

#define MAX_NV 8
#define MAX_L 26

bool    edges[MAX_NV][MAX_NV];
int     map[MAX_L];
int     rmap[MAX_NV];

int     min_bandwidth;
string  min_order;

void split(string &s, char delim, list<string>& l) {
    stringstream ss(s);
    string item;
    while(getline(ss, item, delim)) {
        l.push_back(item);
    }
}

int toi(char c) {
    return c - 'A';
}

int calc_bandwidth(int order[MAX_NV], int n) {
    int max = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            if(edges[order[i]][order[j]] && max < abs(i-j)) {
                max = abs(i-j);
            }
        }
    }
    return max;
}

void backtrack(int order[MAX_NV], bool used[MAX_NV], int k, int n) {
    if(k == n) {
        int bandwidth = calc_bandwidth(order, n);
        if(bandwidth <= min_bandwidth) {
            stringstream ss;
            for(int i = 0; i < n; i++) {
                ss << (char)('A' + rmap[order[i]]);
                ss << " ";
            }
            ss << "-> " << bandwidth;
            
            string result = ss.str();
            
            if(bandwidth < min_bandwidth || result < min_order) {
                min_bandwidth = bandwidth;
                min_order = ss.str();
            }
        }
        return;
    }
    
    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            order[k] = i;
            used[i] = true;
            backtrack(order, used, k + 1, n);
            used[i] = false;
        }
    }
    
}

int main() {
    string graph;
    while(cin >> graph && graph != "#") {
        //
        // removed stuff that prints endl except for the first line
        //
        for(int i = 0; i < MAX_NV; i++) {
            rmap[i] = -1;
            for(int j = 0; j < MAX_NV; j++)
                edges[i][j] = false;
        }
        
        for(int i = 0; i < MAX_L; i++) {
            map[i] = -1;
        }
        
        min_bandwidth = 100;
        
        
        int nVertices = 0;
        list<string> records;
        split(graph, ';', records);
        
        for(auto it = records.begin(); it != records.end(); it++) {
            string s = *it;
            int v = toi(s[0]);
            map[v] = nVertices;
            rmap[nVertices] = v;
            nVertices++;
        }
        
        for(auto it = records.begin(); it != records.end(); it++) {
            string s = *it;
            int v = toi(s[0]);
            for(int i = 2; i < s.length(); i++) {
                int y = toi(s[i]);
                if(map[y] == -1) {
                    map[y] = nVertices;
                    rmap[nVertices] = y;
                    nVertices++;
                }
                edges[map[v]][map[y]] = true;
                edges[map[y]][map[v]] = true;
            }
        }
        
        int order[MAX_NV];
        bool used[MAX_NV];
        
        backtrack(order, used, 0, nVertices);

        //
        // New line all the time
        //
        cout << min_order << endl;
    }
    return 0;
}

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

Re: 140 - bandwith

Post by brianfry713 »

Maybe there is an input like this:

Code: Select all

A:B;A:C;B:A;C:A
#
My AC output:

Code: Select all

B A C -> 1
Check input and AC output for thousands of problems on uDebug!

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 140 - bandwith

Post by mostruash »

Yeah, that is possible I guess. I'll fix my code and let you know. Thanks.

Edit: I fixed that (i.e. omitted duplicate nodes on the left hand side of the colon) but still getting WA. I wonder what other critical case that I'm missing...

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

Re: 140 - bandwith

Post by brianfry713 »

brianfry713 wrote:Post your updated code.
Check input and AC output for thousands of problems on uDebug!

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 140 - bandwith

Post by mostruash »

Code: Select all

#include <iostream>
#include <memory>
#include <string>
#include <list>
#include <sstream>
#include <cmath>

using namespace std;

#define MAX_NV 8
#define MAX_L 26

bool    edges[MAX_NV][MAX_NV];
int     map[MAX_L];
int     rmap[MAX_NV];

int     min_bandwidth;
string  min_order;

void split(string &s, char delim, list<string>& l) {
    stringstream ss(s);
    string item;
    while(getline(ss, item, delim)) {
        l.push_back(item);
    }
}

int toi(char c) {
    return c - 'A';
}

int calc_bandwidth(int order[MAX_NV], int n) {
    int max = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            if(edges[order[i]][order[j]] && max < abs(i-j)) {
                max = abs(i-j);
            }
        }
    }
    return max;
}

void backtrack(int order[MAX_NV], bool used[MAX_NV], int k, int n) {
    if(k == n) {
        int bandwidth = calc_bandwidth(order, n);
        if(bandwidth <= min_bandwidth) {
            stringstream ss;
            for(int i = 0; i < n; i++) {
                ss << (char)('A' + rmap[order[i]]);
                ss << " ";
            }
            ss << "-> " << bandwidth;
            
            string result = ss.str();
            
            if(bandwidth < min_bandwidth || result < min_order) {
                min_bandwidth = bandwidth;
                min_order = ss.str();
            }
        }
        return;
    }
    
    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            order[k] = i;
            used[i] = true;
            backtrack(order, used, k + 1, n);
            used[i] = false;
        }
    }
    
}

int main() {
    string graph;
    while(cin >> graph && graph != "#") {
        for(int i = 0; i < MAX_NV; i++) {
            rmap[i] = -1;
            for(int j = 0; j < MAX_NV; j++)
                edges[i][j] = false;
        }
        
        for(int i = 0; i < MAX_L; i++) {
            map[i] = -1;
        }
        
        min_bandwidth = 100;
        
        
        int nVertices = 0;
        list<string> records;
        split(graph, ';', records);
        
        for(auto it = records.begin(); it != records.end(); it++) {
            string s = *it;
            int v = toi(s[0]);
            if(map[v] == -1) {
                map[v] = nVertices;
                rmap[nVertices] = v;
                nVertices++;
            }
        }
        
        for(auto it = records.begin(); it != records.end(); it++) {
            string s = *it;
            int v = toi(s[0]);
            for(int i = 2; i < s.length(); i++) {
                int y = toi(s[i]);
                if(map[y] == -1) {
                    map[y] = nVertices;
                    rmap[nVertices] = y;
                    nVertices++;
                }
                edges[map[v]][map[y]] = true;
                edges[map[y]][map[v]] = true;
            }
        }
        
        int order[MAX_NV];
        bool used[MAX_NV];
        
        backtrack(order, used, 0, nVertices);
        cout << min_order << endl;
    }
    return 0;
}

Post Reply

Return to “Volume 1 (100-199)”