| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Условия | Toshpulatov (MSU Tashkent) | 1487. Китайский футбол | 25 янв 2021 10:58 | 1 | Условия Toshpulatov (MSU Tashkent) 25 янв 2021 10:58 В задаче сказано, проверить существует ли такая команда 'x' что она обыграет и команду A и команду В, если существует то ответ No иначе YES
в таком случае можно использовать bitset | | Am I stupid? | Alexander Sokolov [MAI] | 1487. Китайский футбол | 14 май 2019 23:24 | 11 | I cant ivent any tests that my solution will fail, but I have WA1!
Can any body help...
Give me some test!
Plz... example tests
4
0110
0011
0001
1000
4
1 4
2 3
3 2
4 1
my output:
No
No
No
No
3
010
000
100
3
1 3
3 1
2 3
out:
No
Yes
No
Is it correct?
Give some more tests! You should print "YES", but not "Yes"... WA 2
CODE:
program china;
var
t:char;
i,j,k:integer;
a:array[1..100,1..100] of boolean;
b:array[1..100] of integer;
chk:array[1..100] of boolean;
x,y,q,n,m:integer;
procedure solve(k:integer);
var
i:integer;
begin
for i:=1 to n do begin
if a[k,i] then begin
if not chk[i] then begin
chk[i]:=true;
solve(i);
end;
end;
end;
end;
begin
readln(n);
for i:=1 to n do begin
for j:=1 to n do begin
read(t);
if t='0' then a[i,j]:=false else a[i,j]:=true;
end;
readln;
end;
for i:=1 to n do begin
fillchar(chk,n,false);
solve(i);
for j:=1 to n do begin
if chk[j] then b[i]:=b[i]+1;
end;
end;
readln(q);
for i:=1 to q do begin
readln(x,y);
if b[x]>b[y] then writeln('YES') else writeln('No');
end;
end. may be this test will help you:
4
0010
0001
0100
0000
4
1 2
1 4
4 1
4 3
answer:
YES
YES
YES
No
Why answer for 1 4 and 4 1 YES
and what is the anwer for
4
0100
0000
0001
0000
7
1 2
2 1
3 4
4 3
3 1
1 3
3 2 Why answer for 1 4 and 4 1 YES Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". My answer for your test: YES YES YES YES YES YES YES Thank you, your answer helped me mutch! Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". Where this is written in the statement? Why can't I solve the problem this way: 1. Make transitive closure of the given graph (matrix A)using Floyd. 2. For every request (pair i j) print "YES" if A[i][j] = 1 otherwise print "No". Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". Where this is written in the statement? Here: "In this case we say that the team A is stronger than the teams B and C (more formally, A is stronger than B if A has beaten B or if A has beaten a team C which is stronger than B)." Edited by author 18.10.2006 23:11 Edited by author 18.10.2006 23:114 1 anwer is No, because 1 better than 3, 3 better than 2, 2 better than 4 => 1 better than 4 | | Transitive closure using std::bitset | decay | 1487. Китайский футбол | 10 фев 2019 20:10 | 1 | Really fast.
for (int k = 0; k < n; ++k) {
for (int i = graph[k]._Find_first(); i < n; i = graph[k]._Find_next(i)) {
graph[k] |= graph[i];
}
} | | meaning | Lucian Ilea | 1487. Китайский футбол | 11 сен 2017 19:20 | 1 | meaning Lucian Ilea 11 сен 2017 19:20 What is the meaning of this problem ?
Edited by author 11.09.2017 19:22
Edited by author 11.09.2017 19:22 | | What is complexy? | Felix_Mate | 1487. Китайский футбол | 3 янв 2017 13:32 | 1 | My algo is O(N*N*sqrt(N)). | | Why this code get WA? | Felix_Mate | 1487. Китайский футбол | 16 авг 2016 16:21 | 1 | Насколько я понял, есть орграф без циклов, при этом если из вершины v1 можно попасть в v2, из v2 в v3, то и из v1 можно попасть в v3 (дуга моделирует победу). Команда v1 лучше v2, если нет u, отличной от v1 и v2/ из u можно попасть в v1 и v2.
Код с WA2:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int nmax = 1005;
bool a[nmax][nmax];
int d[nmax], p[nmax]; //d[v]=0,если нет входящих дуг в v, p[v]-вершина u/ v достижима из u и d[v]=0.
bool used[nmax];
char ch;
int n, q, v, u;
void DFS(int v, int par);
void main()
{
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
{
d[i] = 0;
used[i] = false;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
scanf("%c", &ch);
if (ch == '0') a[i][j] = 0;
else a[i][j] = 1;
d[j]+=a[i][j];
if (j == n) scanf("\n");
}
}
for (int i = 1; i <= n; i++)
{
if (d[i] == 0)
{
p[i] = i;
DFS(i, i);
}
}
scanf("%d\n", &q);
for (int i = 1; i <= q; i++)
{
scanf("%d %d\n", &v, &u);
if ((d[v] > 0) && (d[u] > 0) && (p[v] == p[u])) printf("No\n");
else printf("YES\n");
}
}
void DFS(int v, int par)
{
used[v] = true;
for (int i = 1; i <= n; i++)
{
if ((!used[i]) && (a[v][i] == 1))
{
p[i] = par;
DFS(i, par);
}
}
}
Ошибка была в том, что из несколько вершин, не имеющих входные дуги, можно попасть в некоторую вершину.
Edited by author 03.01.2017 22:31 | | To admins. Test #5 seems to be wrong. | Roman Rubanenko | 1487. Китайский футбол | 7 мар 2014 18:21 | 1 | According to my program, test #5 contains cycles. Isn't it forbidden by the statement? | | Runtime Error on C# | Pelevina | 1487. Китайский футбол | 3 май 2013 20:34 | 1 | почему возникает такая проблема? код вроде соответствует примеру, приведенному в руководстве. В Visual Studio 2010 все работает. что делать? | | Help pls, I'm bewildered! | HeypaBHoBeceH | 1487. Китайский футбол | 8 мар 2009 15:02 | 1 | NVM, got AC. Had BIG problems understanding the problem statement! Thanks to all who wrote their contemplations about it!
Edited by author 08.03.2009 15:26 | | May be Floid? | AndreySUrSU | 1487. Китайский футбол | 19 авг 2008 19:17 | 9 | 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! 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. 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? 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" 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! 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. 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. My Floyd in O(N^3) got AC within 0.25 sec. | | Need clarifications | Denis Koshman | 1487. Китайский футбол | 19 авг 2008 15:16 | 1 | 1. Is it true that there are no loops in the input data?
2. Is it true and A and B are always such that neiher A is sronger than B, nor B is stronger than A? | | AC now | JTim | 1487. Китайский футбол | 18 фев 2008 20:16 | 1 |
Edited by author 10.07.2008 05:40 | | Which algorithm should I use? | Ludovic | 1487. Китайский футбол | 11 окт 2006 20:25 | 1 | I use Floyd to obtain the transitive closure and got TLE at case #24... | | To Admins! | Ostap Korkuna (LNU) | 1487. Китайский футбол | 8 окт 2006 03:07 | 2 | What is the answer for sample input and a query 2 1?
Is it YES? Because there is no team C that is stronger then team 1, and that team 2 is weaker than team C. No one is answering, so I'll do it myself :-)
Of course the answer is YES! My explenation is correct. |
|
|
