ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1487. Chinese Football

May be Floid?
Posted by AndreySUrSU 7 Oct 2006 15:15
Re: May be Floid?
Posted by svr 10 Oct 2006 20:43
Problem is standart transative closer algorithm using DFS
Interesting feater that in chaina football player may be stronger than himself because of circle.
Let P(a)=list of Ancestors and GrandAncestors and .. of a;
Then a,b-YES ~P(a)^P(b)=Empty
P(a) would better have as bitset
I have TLE 24 because forgotten reachabylity algorithm O(n)
For our forum shold maintain standard algorithm Use library please!
Re: May be Floid?
Posted by svr 12 Oct 2006 00:36
It seems that transative closure as a rule has o(n^3) therefore when n=1000 we have no chances. But by god help strong components can be calculated for linear time and we can use forest of strong components. No for players a and b if and only if a and be dosn't belong to the same tree in this fotest.
Re: May be Floid?
Posted by elmariachi1414 (TNU) 12 Oct 2006 01:39
So what about sample? 2 and 3 belong to the same tree, but answer is "No".
I thought, answer is "No", only if a and b common parent and there is no way from a to b.
Am i right?
Re: May be Floid? (+)
Posted by elmariachi1414 (TNU) 12 Oct 2006 05:36
1. DFS for all parent nodes
2. For each node store its parent in matrix [N][N/8] (bit mask)
3. For each A and B - if there is a common parent return "No"
Re: May be Floid?
Posted by svr 12 Oct 2006 13:29
Excuse me!. I were mistaken.
But I am shure that answer can be taken in terms of forest of strong components or Gerz graf.
Let Sc(a)- number of component for a;
NumT(i) - number of tree in the forest for comp i
Ncomp[i]- amount of vertex in i-th comp
Root[i]=1 if i- root in forest
Then:
1) if (Sc(a)==Sc(b)) and (a!=b)) F(a,b)=No;
2) if NumT(Sc(a))==NumT(Sc(b)) and Root(Sc(a))==0
and Root(Sc(b))==0 F(a,b)=No;
3) if NumT(Sc(a))==NumT(Sc(b)) and Root(Sc(a))==1
and Ncomop(Sc(a)>1) F(a,b)=No;
4) if NumT(Sc(a))==NumT(Sc(b)) and Root(Sc(b))==1
and Ncomop(Sc(b)>1) F(a,b)=No;

Otherwise F(a,b)=YES
Algo for strong comps has O(|V|+|E|)=O(n^2)
But I have WA4
If your don't agree with my arguments send message ,plese!
Re: May be Floid?
Posted by svr 13 Oct 2006 01:44
I finished and have Ac (0.6) on my Idea. All is right but final refinement says that sftrong component i may belong to many trees and we must use SubT[1..Nco][1..NT] matrix instead of array SubT[1..Nco].I used my previous strong components program algo O(|V|+O(|E|) from Kormen where i used vector container for adjacent lists this is the reason of bad time of executing. This is interface of the program:
void S_Comps(vector<short>smeg[MAX],short Nv,short &Nco,bool korn[MAX], short Scomps[MAX],char *Sm,short &NT,char *SubT,short Ncomp[MAX])
After O(n^3) Floid difficulties program has passed all tests immediately after removing silly mistakes.
Re: May be Floid?
Posted by Denis Koshman 19 Aug 2008 15:22
I doubt there are any strong components larger than 1 (otherwise words "stronger" and "beaten" in problem statement loose big part of their original meaning).

Also, strong components form DAG, not necessarily a forest.
Re: May be Floid?
My Floyd in O(N^3) got AC within 0.25 sec.