Discussion @ 1176. Hyperchannels @ Timus Online Judge

Algorist WHY DO I GET TL EXCEEDED? PLZ HELP :((( [8] // Problem 1176. Hyperchannels 18 Feb 2002 22:53

#include <iostream>
using namespace std;

struct stack {
int data;
stack* next;
};

stack* m[1001];
int n,a;
stack *st,*ce;

void push(stack* &s,int what) {
stack* tmp=new stack;
if (tmp==NULL) { cout<<"Allocation Error"<<endl; return; }
tmp->next=s;
tmp->data=what;
s=tmp;
}

int pop(stack* &s) {
stack* tmp;
int q;
if (s==NULL) { cout<<"Stack already empty"<<endl; return -1; }
tmp=s;
q=s->data;
s=s->next;
delete tmp;
return q;
}

int top(stack* s) {
if (s==NULL) { cout<<"Stack empty"<<endl; return -1; } else return s-
>data;
}

void init() {
int p;
cin>>n>>a;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) {
   cin>>p;
   p=!p;
   if(i==j) p=0;
   if (p) push(m[i],j);
}
}

int empty(stack* s) {
if (s==NULL) return 1; else return 0;
}

void solve() {
push(st,a);
while (st!=NULL) {
int v=top(st);
if (m[v]!=NULL) push(st,pop(m[v]));
   else push(ce,pop(st));
}
}

void print() {
int prev=pop(ce);
while(ce!=NULL) {
cout<<prev<<" "<<top(ce)<<endl;
prev=pop(ce);
}
}

int main() {
st=NULL;
ce=NULL;
init();
solve();
print();
return 0;
}

Nazarov Denis (nsc2001@rambler.ru) ...because your algorithm is very bad. Use Hungry algorithm and you'll get AC :-))) [7] // Problem 1176. Hyperchannels 18 Feb 2002 23:09

> #include <iostream>
> using namespace std;
>
> struct stack {
> int data;
> stack* next;
> };
>
> stack* m[1001];
> int n,a;
> stack *st,*ce;
>
> void push(stack* &s,int what) {
> stack* tmp=new stack;
> if (tmp==NULL) { cout<<"Allocation Error"<<endl; return; }
> tmp->next=s;
> tmp->data=what;
> s=tmp;
> }
>
> int pop(stack* &s) {
> stack* tmp;
> int q;
> if (s==NULL) { cout<<"Stack already empty"<<endl; return -1; }
> tmp=s;
> q=s->data;
> s=s->next;
> delete tmp;
> return q;
> }
>
> int top(stack* s) {
> if (s==NULL) { cout<<"Stack empty"<<endl; return -1; } else return
s-
> >data;
> }
>
>
> void init() {
> int p;
> cin>>n>>a;
> for (int i=1;i<=n;i++)
>   for (int j=1;j<=n;j++) {
>    cin>>p;
>    p=!p;
>    if(i==j) p=0;
>    if (p) push(m[i],j);
>   }
> }
>
> int empty(stack* s) {
> if (s==NULL) return 1; else return 0;
> }
>
> void solve() {
> push(st,a);
> while (st!=NULL) {
>   int v=top(st);
>   if (m[v]!=NULL) push(st,pop(m[v]));
>    else push(ce,pop(st));
> }
> }
>
> void print() {
> int prev=pop(ce);
> while(ce!=NULL) {
>   cout<<prev<<" "<<top(ce)<<endl;
>   prev=pop(ce);
> }
> }
>
> int main() {
> st=NULL;
> ce=NULL;
> init();
> solve();
> print();
> return 0;
> }

Renato Baba Re: "Hungry" == "Greedy"? :-)) (-) // Problem 1176. Hyperchannels 18 Feb 2002 23:28

> > #include <iostream>
> > using namespace std;
> >
> > struct stack {
> > int data;
> > stack* next;
> > };
> >
> > stack* m[1001];
> > int n,a;
> > stack *st,*ce;
> >
> > void push(stack* &s,int what) {
> > stack* tmp=new stack;
> > if (tmp==NULL) { cout<<"Allocation Error"<<endl; return; }
> > tmp->next=s;
> > tmp->data=what;
> > s=tmp;
> > }
> >
> > int pop(stack* &s) {
> > stack* tmp;
> > int q;
> > if (s==NULL) { cout<<"Stack already empty"<<endl; return -1; }
> > tmp=s;
> > q=s->data;
> > s=s->next;
> > delete tmp;
> > return q;
> > }
> >
> > int top(stack* s) {
> > if (s==NULL) { cout<<"Stack empty"<<endl; return -1; } else
return
> s-
> > >data;
> > }
> >
> >
> > void init() {
> > int p;
> > cin>>n>>a;
> > for (int i=1;i<=n;i++)
> >   for (int j=1;j<=n;j++) {
> >    cin>>p;
> >    p=!p;
> >    if(i==j) p=0;
> >    if (p) push(m[i],j);
> >   }
> > }
> >
> > int empty(stack* s) {
> > if (s==NULL) return 1; else return 0;
> > }
> >
> > void solve() {
> > push(st,a);
> > while (st!=NULL) {
> >   int v=top(st);
> >   if (m[v]!=NULL) push(st,pop(m[v]));
> >    else push(ce,pop(st));
> > }
> > }
> >
> > void print() {
> > int prev=pop(ce);
> > while(ce!=NULL) {
> >   cout<<prev<<" "<<top(ce)<<endl;
> >   prev=pop(ce);
> > }
> > }
> >
> > int main() {
> > st=NULL;
> > ce=NULL;
> > init();
> > solve();
> > print();
> > return 0;
> > }

Algorist You're making me smile :)) [4] // Problem 1176. Hyperchannels 19 Feb 2002 01:12

Well,
1. I know a person who got AC with exactly that :))
2. Finding an Euler Cycle in a graph is not a bad algorithm. It isO
(|E|) operations, where E is the quantity of the edges in the graph.
And if it is 32000, calculate how much time it takes :))) Certainly,
the algorithm (having in mind that even someone got AC with that ) is
not bad........................

Algorist And..................... [3] // Problem 1176. Hyperchannels 19 Feb 2002 01:16

What is more, I
1. Read the input(there is no way to escape from that :)))) )
2. Go through the graph once(to find the cycle) (can't solve the
problem without going through the edges........)
3. Print it (no way to escape, too :))) )
So, where is the problem? I cannot realise how can you solve it
without doing all these :))
Btw, what is your greedy?

Algorist One last thing [2] // Problem 1176. Hyperchannels 19 Feb 2002 01:19

Well, it's possible that I'm mistaken beacuse I'm rather sleepy now,
but I think that the algorithm is not so bad :))))))))))))))))))

Nazarov Denis (nsc2001@rambler.ru) It's only a joke. Your algorithm is rigth, but yout implemalation isn't so good (Use linked list!!!) [1] // Problem 1176. Hyperchannels 19 Feb 2002 15:51

> Well, it's possible that I'm mistaken beacuse I'm rather sleepy
now,
> but I think that the algorithm is not so bad :))))))))))))))))))

Algorist Re: It's only a joke. Your algorithm is rigth, but yout implemalation isn't so good (Use linked list!!!) // Problem 1176. Hyperchannels 19 Feb 2002 17:00

Does it matter whether I use a linked list or a stack? To me, it does
not matter AT ALL...Because I use always the first element, so the
stack is wonderful.. Or perhaps you are joking again?

HNT You are creative :) // Problem 1176. Hyperchannels 19 Feb 2002 12:06

Discussion of Problem 1176. Hyperchannels