Page 3 of 4

Re: 140 - bandwith

Posted: Thu Jul 05, 2012 12:35 pm
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

Re: 140 - bandwith

Posted: Sat Dec 08, 2012 4:07 pm
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;
}

Re: 140 - bandwith

Posted: Tue Dec 11, 2012 1:56 am
by brianfry713
Input:

Code: Select all

A:D
#
AC output:

Code: Select all

A D -> 1

Re: 140 - bandwith

Posted: Sat Dec 15, 2012 11:50 am
by Sabiha_Fancy
Thank you for your reply.

Re: 140 - bandwith

Posted: Mon Feb 11, 2013 10:06 pm
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;
}

Re: 140 - bandwith

Posted: Wed Feb 13, 2013 12:09 am
by brianfry713
Try input:

Code: Select all

A:Z
#

Re: 140 - bandwith

Posted: Wed May 28, 2014 10:45 pm
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;
}

Re: 140 - bandwith

Posted: Wed Jun 11, 2014 8:27 pm
by brianfry713
Always print a newline char at the end of the last line.

Re: 140 - bandwith

Posted: Thu Jun 12, 2014 5:27 pm
by mostruash
I tried that too, still WA.

Re: 140 - bandwith

Posted: Thu Jun 12, 2014 7:31 pm
by brianfry713
Post your updated code.

Re: 140 - bandwith

Posted: Thu Jun 12, 2014 9:32 pm
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;
}

Re: 140 - bandwith

Posted: Fri Jun 13, 2014 9:18 pm
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

Re: 140 - bandwith

Posted: Mon Jun 16, 2014 12:55 am
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...

Re: 140 - bandwith

Posted: Mon Jun 16, 2014 8:09 pm
by brianfry713
brianfry713 wrote:Post your updated code.

Re: 140 - bandwith

Posted: Tue Jul 01, 2014 10:01 pm
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;
}