## 140 - Bandwidth

Moderator: Board moderators

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

### Re: 140 - bandwith

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

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

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

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

### Re: 140 - bandwith

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

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

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

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

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

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

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

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

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

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

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