Show all threads Hide all threads Show all messages Hide all messages | Условия | Toshpulatov (MSU Tashkent) | 1487. Chinese Football | 25 Jan 2021 10:58 | 1 | Условия Toshpulatov (MSU Tashkent) 25 Jan 2021 10:58 В задаче сказано, проверить существует ли такая команда 'x' что она обыграет и команду A и команду В, если существует то ответ No иначе YES в таком случае можно использовать bitset | Am I stupid? | Alexander Sokolov [MAI] | 1487. Chinese Football | 14 May 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. Chinese Football | 10 Feb 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. Chinese Football | 11 Sep 2017 19:20 | 1 | meaning Lucian Ilea 11 Sep 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. Chinese Football | 3 Jan 2017 13:32 | 1 | My algo is O(N*N*sqrt(N)). | Why this code get WA? | Felix_Mate | 1487. Chinese Football | 16 Aug 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. Chinese Football | 7 Mar 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. Chinese Football | 3 May 2013 20:34 | 1 | почему возникает такая проблема? код вроде соответствует примеру, приведенному в руководстве. В Visual Studio 2010 все работает. что делать? | Help pls, I'm bewildered! | HeypaBHoBeceH | 1487. Chinese Football | 8 Mar 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. Chinese Football | 19 Aug 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. Chinese Football | 19 Aug 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. Chinese Football | 18 Feb 2008 20:16 | 1 | Edited by author 10.07.2008 05:40 | Which algorithm should I use? | Ludovic | 1487. Chinese Football | 11 Oct 2006 20:25 | 1 | I use Floyd to obtain the transitive closure and got TLE at case #24... | To Admins! | Ostap Korkuna (LNU) | 1487. Chinese Football | 8 Oct 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. |
|
|