Обсуждение @ 1487. Китайский футбол @ Timus Online Judge

Toshpulatov (MSU Tashkent) Условия // Задача 1487. Китайский футбол 25 янв 2021 10:58

Alexander Sokolov [MAI] Am I stupid? [10] // Задача 1487. Китайский футбол 8 окт 2006 22:12

I cant ivent any tests that my solution will fail, but I have WA1!
Can any body help...
Give me some test!
Plz...

Alexander Sokolov [MAI] Re: Am I stupid? [9] // Задача 1487. Китайский футбол 8 окт 2006 22:28

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!

Burmistrov Ivan (USU) Re: Am I stupid? [8] // Задача 1487. Китайский футбол 8 окт 2006 23:23

You should print "YES", but not "Yes"...

Alexander Sokolov [MAI] Re: Am I stupid? [7] // Задача 1487. Китайский футбол 8 окт 2006 23:47

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.

Burmistrov Ivan (USU) Re: Am I stupid? [6] // Задача 1487. Китайский футбол 9 окт 2006 21:09

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

Sid Re: Am I stupid? [4] // Задача 1487. Китайский футбол 9 окт 2006 23:40

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

Burmistrov Ivan (USU) Re: Am I stupid? [3] // Задача 1487. Китайский футбол 10 окт 2006 23:22

Sid писал(a) 9 октября 2006 23:40

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

Sid Re: Am I stupid? // Задача 1487. Китайский футбол 12 окт 2006 21:48

Thank you, your answer helped me mutch!

Yaroslavtsev Grigory (SpbSPU) Re: Am I stupid? [1] // Задача 1487. Китайский футбол 15 окт 2006 19:01

Burmistrov Ivan (USU) писал(a) 10 октября 2006 23:22

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".

Burmistrov Ivan (USU) Re: Am I stupid? // Задача 1487. Китайский футбол 18 окт 2006 23:10

Yaroslavtsev Grigory (SpbSPU) писал(a) 15 октября 2006 19:01

Burmistrov Ivan (USU) писал(a) 10 октября 2006 23:22

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:11

AnisimovaViktoria Re: Am I stupid? // Задача 1487. Китайский футбол 14 май 2019 23:24

4 1 anwer is No, because 1 better than 3, 3 better than 2, 2 better than 4 => 1 better than 4

decay Transitive closure using std::bitset // Задача 1487. Китайский футбол 10 фев 2019 20:10

Lucian Ilea meaning // Задача 1487. Китайский футбол 11 сен 2017 19:20

Felix_Mate What is complexy? // Задача 1487. Китайский футбол 3 янв 2017 13:32

Felix_Mate Why this code get WA? // Задача 1487. Китайский футбол 16 авг 2016 16:21

Насколько я понял, есть орграф без циклов, при этом если из вершины 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

Roman Rubanenko To admins. Test #5 seems to be wrong. // Задача 1487. Китайский футбол 7 мар 2014 18:21

Pelevina Runtime Error on C# // Задача 1487. Китайский футбол 3 май 2013 20:34

HeypaBHoBeceH Help pls, I'm bewildered! // Задача 1487. Китайский футбол 8 мар 2009 15:02

AndreySUrSU May be Floid? [8] // Задача 1487. Китайский футбол 7 окт 2006 15:15

But i receive WA2.

svr Re: May be Floid? [7] // Задача 1487. Китайский футбол 10 окт 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!

svr Re: May be Floid? [6] // Задача 1487. Китайский футбол 12 окт 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.

elmariachi1414 (TNU) Re: May be Floid? [5] // Задача 1487. Китайский футбол 12 окт 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?

elmariachi1414 (TNU) Re: May be Floid? (+) // Задача 1487. Китайский футбол 12 окт 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"

svr Re: May be Floid? [3] // Задача 1487. Китайский футбол 12 окт 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!

svr Re: May be Floid? [2] // Задача 1487. Китайский футбол 13 окт 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.

Denis Koshman Re: May be Floid? [1] // Задача 1487. Китайский футбол 19 авг 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.

Vedernikoff Sergey (HSE: EconomicsForever!) Re: May be Floid? // Задача 1487. Китайский футбол 19 авг 2008 19:17

My Floyd in O(N^3) got AC within 0.25 sec.

Denis Koshman Need clarifications // Задача 1487. Китайский футбол 19 авг 2008 15:16

JTim AC now // Задача 1487. Китайский футбол 18 фев 2008 20:16

Ludovic Which algorithm should I use? // Задача 1487. Китайский футбол 11 окт 2006 20:25

Ostap Korkuna (LNU) To Admins! [1] // Задача 1487. Китайский футбол 7 окт 2006 17:56

Обсуждение задачи 1487. Китайский футбол