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

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

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 » Tue Dec 11, 2012 1:56 am

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 » Sat Dec 15, 2012 11:50 am

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

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 » Wed Feb 13, 2013 12:09 am

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

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 » Wed Jun 11, 2014 8:27 pm

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 » Thu Jun 12, 2014 5:27 pm

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 » Thu Jun 12, 2014 7:31 pm

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

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

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

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 » Mon Jun 16, 2014 8:09 pm

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

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)”