140 - Bandwidth

[@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]

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.

Code: Select all

#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;
}

[brianfry713]

Input:

Code: Select all

A:D
#

AC output:

Code: Select all

A D -> 1

[Sabiha_Fancy]

Thank you for your reply.

[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]

Try input:

Code: Select all

A:Z
#

[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]

Always print a newline char at the end of the last line.

[mostruash]

I tried that too, still WA.

[brianfry713]

Post your updated code.

[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]

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

[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]

Post your updated code.

[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;
}