Show all threads Hide all threads Show all messages Hide all messages | Another approach | andreyDagger | 1218. Episode N-th: The Jedi Tournament | 11 Nov 2021 22:35 | 1 | I see many people solved this with graph algorithms, there is also greedy approach. Let's build graph: u->v, if jedi u is winning v. You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him Edited by author 11.11.2021 22:35 Edited by author 11.11.2021 22:35 Edited by author 11.11.2021 22:36 | Небольшой хак для DFS | Mahilewets | 1218. Episode N-th: The Jedi Tournament | 23 Jul 2017 18:19 | 2 | Если вы используете DFS в итеративной форме, то вы можете получить TLE#4. Если вы перепишите DFS в рекурсивную форму и будете компилировать на Visual C++, то получите AC за менее чем 0.1 секунды. Алгоритм свой я оцениваю как O(N*N*N) по времени, Поскольку я N раз запускаю DFS по графу в котором O(N*N) ребер (В графе проведено ребро от джедая который может победить джедая X в схватке к джедаю Х) | Объяснения по-русски | Felix_Mate | 1218. Episode N-th: The Jedi Tournament | 23 Jun 2016 06:31 | 3 | Короче,у нас проходит некий турнир.Правила таковы: мы выбираем любых двух джедаев из оставшихся ,они между собой сражаются,из них по условию ровно один побеждает,проигравший исчезает с турнира. И так далее: снова выбираем двух джедаев,один остается,и т.д. По условию либо Джедай А сильнее Джедая Б либо наоборот. Сильнее значит не менее чем по двум параметрам один джедай выигрывает у другого(т.е. соответствующие значения строго больше). Нам нужно найти всех возможных победителей,т.е. тех,кто останется последним. Мы можем как угодно формировать расписание турнира,т.е. выбирать кто с кем из оставшихся будет драться. Победитель может провести всего 1 бой,а может 2,а может 3,... .Расписание мы САМИ формируем!!! У кого нет идей,советую узнать про алгоритм Тарьяна и граф конденсации. Edited by author 31.08.2015 22:18 За N*logN решается, есличо)) | what right answer for this test? | [LG]_#\#@P$T[101]R | 1218. Episode N-th: The Jedi Tournament | 5 Jan 2016 16:10 | 3 | 6 one 7 4 5 two 6 3 10 three 5 10 9 four 7 6 7 five 2 5 8 six 3 3 3 I think : one, two, three, four, five. Edited by author 18.03.2009 20:44 test is incorrect, two and six have equal second parameter | How to solve this problem? | Saturn | 1218. Episode N-th: The Jedi Tournament | 8 Jul 2012 03:35 | 6 | BFS (-) Dmitry 'Diman_YES' Kovalioff 28 Jul 2004 09:27 My solution is based on the concept of strong connectivity. I find connected components of the graph, then I print those jedis, that belong to the non-dominated component. It is npt very quick, but it works. I don't know, how BFS can help with this problem. Any explanation will be very much appreciated. (de bene esse: my e-mail is akhmed[at]astranet[dot]ru). for each start among knights mark all that can be reached from start thru winning if all are marked then print start's name To test your speed, you can use the following perl script to generate input: $n = 200; print "$n\n"; for(1..$n){ print "J$_"; print ' ', int(rand()*100000) for 1..3; print "\n" } O(N*log(N)) solution exists :) | Please give me AC answers on my testcase | 3a[3.141592..]Jlu | 1218. Episode N-th: The Jedi Tournament | 11 Aug 2010 19:36 | 3 | 3 q1 1 1 2 q2 1 2 1 q3 2 1 1 2 a1 1 1 1 a2 1 1 1 3 w1 6 6 6 w2 6 4 4 w3 5 5 5 great thanks! Edited by author 11.08.2010 04:41 Quote from statement: Is not possible a draw, because no Jedi any equal parameter may have. Therefore, incorrect all three your tests are. Maybe you give me tricky test? because I've got wa#4 ((( | To Admins !! | sasha | 1218. Episode N-th: The Jedi Tournament | 25 May 2009 10:34 | 4 | Сделайте нормальный человеческий перевод. Ну невозможно читать этот бред. "Are different the lightsaber, and Jedi different are" - вот как это понять, или " If looses a Jedi, must leave the tournament he." - лучше условие на русском сделайте, чем бредовое английское. Then, maybe, not Jedi English, but Yoda English =) | why crash ( access violation ) test #4 | manishmmulani | 1218. Episode N-th: The Jedi Tournament | 5 Jan 2008 04:18 | 1 | #include<iostream> #include<string> #include<vector> using namespace std; struct node { string name; bool flag[205],temp[205]; vector<int> winto; int count ; long int x, y,z; bool canWinOver(struct node p) { int c=0; if( x > p.x ) c++; if( y > p.y ) c++; if( z > p.z ) c++; if( c > 1 ) return true; return false; } }; typedef struct node node; int main() { node jedi[205] ; int i , j , n , k , l; string s; long int p,q,r; cin >> n; for(i=1 ; i <= n ; i++ ) { cin >> s >> p >> q >> r; jedi[i].name=s; jedi[i].x=p; jedi[i].y=q; jedi[i].z=r; } for(i=1; i <= n ; i++) { for(j=i+1; j <= n ; j++) { if( jedi[i].canWinOver(jedi[j]) ) { jedi[i].flag[j]=true; jedi[i].winto.push_back(j); jedi[i].count++; } else { jedi[j].flag[i]=true; jedi[j].winto.push_back(i); jedi[j].count++; } } } for(i=1 ; i <= n ; i++ ) { for(j=1 ; j <= n ; j++ ) { if(i!=j && !(jedi[i].flag[j]) ) { for(k=0 ; k < jedi[i].count ; k++ ) { l = jedi[i].winto[k]; if(!(jedi[j].flag[l])) { jedi[j].winto.push_back(l); jedi[j].temp[l]=true; } } } } } for(i=1 ; i <= n ; i++ ) { int sum=0; for(j=1 ; j <= n ; j++ ) if( jedi[i].flag[j] || jedi[i].temp[j] ) sum++;
if(sum==n-1) cout << jedi[i].name << endl; } return 0; } PLS HELP | Why TL#4??? | Neizvestnii | 1218. Episode N-th: The Jedi Tournament | 15 Aug 2007 18:13 | 5 | I shocked! My program used 2 dfs(for find conecting components). Thats all. n<=200. Dfs work by O(n+m). Why I have TL??? Please help me, I really dont understand, where my mistakes. If you had TL#4 then increase your massivs. Because, if you use graf, then quantity of edges may 40000 What should we search? Components of strong connectivity or cycles? Please help me... If I search for components of strong connectivity that I receive WA#4. When I search for cycles I receive WA#5. What should I search? Please help me. | WA #3 | Yuri | 1218. Episode N-th: The Jedi Tournament | 23 Dec 2006 05:59 | 2 | WA #3 Yuri 1 Oct 2006 20:32 Be careful!!! In the task said that "The parameters are ... not greater than 100000 by the ABSOLUTE value." So you need check not only if the letter, which in digit, is in ['0'..'9'], but '-' too. GOOD LUCK and have AC ) It's just your stupid checking input... :) All boys like to : 8_Ш3 <<<<<<<<< :) c3 | WA#5 | Zubyk Taras | 1218. Episode N-th: The Jedi Tournament | 24 Jul 2006 13:28 | 2 | WA#5 Zubyk Taras 24 Jun 2006 12:02 I do not understand why at me the wrong answer 5. Somebody can help{assist} me? Here my code. Help{Assist} please, I cannot find my mistake{error}. Thanks beforehand!!! Re: WA#5 Todor Tsonkov 24 Jul 2006 13:28 This Problem is not so hard, construct orientated graph that describes the situation and with DFS you can easily make it | How to improve my Algo. I got TL on test 4 | Tabledott | 1218. Episode N-th: The Jedi Tournament | 23 Jun 2006 16:37 | 3 | [code deleted] Edited by moderator 23.06.2006 17:14 I do not understand why at me the wrong answer 5. Somebody can help{assist} me? Here my code. Help{Assist} please, I cannot find my mistake{error}. Thanks beforehand!!! [code deleted] Edited by moderator 23.06.2006 17:14 Please, don't post your code. Just explain your algo... So it would be easier to help (assist =)) you. | Why wrong answer? Help! | Vitalik | 1218. Episode N-th: The Jedi Tournament | 19 Jun 2006 12:50 | 1 | I do not understand why at me the wrong answer 5. Somebody can help{assist} me? Here my code. Help{Assist} please, I cannot find my mistake{error}. Thanks beforehand!!! [code deleted] Edited by moderator 23.06.2006 17:18 | my god who can help me .... i get wa 3... | oier | 1218. Episode N-th: The Jedi Tournament | 14 Nov 2005 13:44 | 1 | i use bfs too!!! i know no one will be patient to look over my code so i do not put it out or give me some texts!fu ck you very much~ Edited by author 14.11.2005 13:46 | problem statement ambiguity | Krayev Alexey(PSU#2) | 1218. Episode N-th: The Jedi Tournament | 15 Apr 2005 20:15 | 1 | I suppose problem statement is not clear enought, because rules for pair composing weren't stated. For me, for instance, isn't obvious that one jedi of ,say, 500 can wait while others kill each other and then kill the last one, so he can take part only in one combat. I thought first time that it is smth like olympic system, I mean. | Compilation Error! Why??? | Michael Medvedev | 1218. Episode N-th: The Jedi Tournament | 26 Jun 2004 23:49 | 2 | program p1218; const mx = 500; var on,tw,th,good:array[1..mx] of longint; s:array[1..mx] of string; v:array[1..mx,1..mx] of boolean; n,k,i,j:integer; c:char; function win(i,j:integer):boolean; var res:integer; begin res := byte(on[i] > on[j]) + byte(tw[i] > tw[j]) + byte(th[i] > th[j]); if res > 1 then win := True else win := False; end; function fill(j:integer):boolean; var i:integer; b:boolean; begin b := True; for i:=1 to n do b := b and v[j,i]; if b then fill := True else fill := False; end; begin readln(n); for i:=1 to n do begin read(c); s[i]:=''; repeat s[i] := s[i] + c; read(c); until c = ' '; readln(on[i],tw[i],th[i]); end; for i:=1 to n do for j:=1 to n do v[i,j] := win(i,j); for k:=1 to n do for i:=1 to n do for j:=1 to n do if not v[i,j] then v[i,j] := v[i,k] and v[k,j]; for i:=1 to n do if fill(i) then writeln(s[i]); end. 'on' is a reserved keyword. | please help! I think my program is right, but always WA! | Protsenko Sergey[ISPU] | 1218. Episode N-th: The Jedi Tournament | 22 Aug 2003 00:57 | 1 | here is my program. 1 i find a jedi which cannot be beaten by another jedi with the ekception of then some jedi which i already visited during DFS. 2 this jedi can be the winner and also jedi which can be reached from this vertex in both sides (can beat and be beaten) please mail your sugestions about this to p_s_@list.ru THANKS IN ADVANCE! VAR Name : ARRAY[1..510] OF String[32]; w1,w,good : ARRAY[1..510] OF integer; Stat : ARRAY[1..510, 0..2] OF LongInt; a:array[1..510,1..510] of integer; N,m,point,num, I, J, Sum,l,i1,k : LongInt; S : String; Ok : Boolean; PROCEDURE init; VAR J,i : LongInt; BEGIN fillchar(a,sizeof(a),0); fillchar(good,sizeof(good),0); for i:=1 to n do for j:=1 to n do if (i<>j)and (((Stat[I][0] > Stat[J][0]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][2] > Stat[J][2]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][0] > Stat[J][0]) AND (Stat[I][2] > Stat[J][2]))) THEN begin a[i,j]:=1; inc(good[i]); end; END; procedure find(i:integer); var j,max:integer; f:boolean; begin j:=1; for i:=2 to n do if good[j]<good[i] then j:=i; k:=j; end; procedure getting1; var j,i:integer; t:array[1..501] of integer; f:boolean; begin fillchar(t,sizeof(t),0); t[k]:=1; repeat f:=true; for i:=1 to n do if t[i]=1 then begin for j:=1 to n do if (a[i,j]=1)and(t[j]=0) then begin t[j]:=1; f:=false; end; end; if f then break; until false; for i:=1 to n do w[i]:=t[i]; end; procedure getting2; var j,i:integer; t:array[1..501] of integer; f:boolean; begin fillchar(t,sizeof(t),0); t[k]:=1; repeat f:=true; for i:=1 to n do if t[i]=1 then begin for j:=1 to n do if (a[j,i]=1)and(t[j]=0) then begin t[j]:=1; f:=false; end; end; if f then break; until false; for i:=1 to n do w1[i]:=t[i]; end; BEGIN ReadLn(N); FOR I := 1 TO N DO BEGIN ReadLn(S); S := S+' '; for j:=1 to length(s) do begin if (s[j]in['A'..'Z'])or(s[j] in ['a'..'z']) then begin insert(s[j],name[i],length(s)); k:=j; end; end; Delete(S, 1, k); WHILE (S[1] = ' ') DO Delete(S, 1, 1); Sum := 0; WHILE (S[1]<>' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][0] := Sum; Sum := 0; WHILE (S[1]<>' ' ) DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][1] := Sum; Sum := 0; WHILE (S[1]<>' ' ) DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; Stat[I][2] := Sum; END; init; ok:=false; fillchar(w,sizeof(w),0); find(1); fillchar(w,sizeof(w),0); fillchar(w1,sizeof(w1),0); getting1; getting2; for i:=1 to n do begin if (w[i]=1)and(w1[i]=1) then writeln(name[i]); end; END. | I think my program is right, but it get WA! | Grebnov Ilya[ISPU] | 1218. Episode N-th: The Jedi Tournament | 14 Mar 2003 12:00 | 1 | VAR Name, Win : ARRAY[1..510] OF String[32]; Flag, Killed : ARRAY[1..510] OF Byte; Stat : ARRAY[1..510, 0..2] OF LongInt; N, I, J, Sum : LongInt; S : String; Ok : Boolean; PROCEDURE Solve(I : LongInt); VAR J : LongInt; BEGIN IF Killed[I] = 1 THEN Exit; Killed[I] := 1; FOR J := 1 TO N DO IF (Killed[J] = 0) AND (I <> J) AND (((Stat[I][0] > Stat[J][0]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][2] > Stat[J][2]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][0] > Stat[J][0]) AND (Stat[I][2] > Stat[J][2]))) THEN BEGIN Solve(J); END; END; BEGIN ReadLn(N); FillChar(Flag, SizeOf(Flag), 0); FOR I := 1 TO N DO BEGIN ReadLn(S); S := S+' '; Name[I] := Copy(S, 1, Pos(' ', S)-1); Delete(S, 1, Pos(' ', S)); WHILE (S[1] = ' ') DO Delete(S, 1, 1); Sum := 0; WHILE (S[1] <> ' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][0] := Sum; Sum := 0; WHILE (S[1] <> ' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][1] := Sum; Sum := 0; WHILE (S[1] <> ' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; Stat[I][2] := Sum; END; FOR I := 1 TO N DO BEGIN FillChar(Killed, SizeOf(Killed), 0); Solve(I); Ok := True; FOR J := 1 TO N DO IF Killed[J] = 0 THEN Ok := False; IF Ok THEN Flag[I] := 1; END; Sum := 0; FOR I := 1 TO N DO IF Flag[I] = 1 THEN BEGIN Inc(Sum); Win[Sum] := Name[I] END; FOR I := 1 TO Sum-1 DO WriteLn(Win[I]); Write(Win[Sum]); END. | Who can give some me some test data about this prob? | JL Wang | 1218. Episode N-th: The Jedi Tournament | 18 Nov 2002 19:45 | 1 | | If anyone who can tell me why it's WA will be very kind! | mace | 1218. Episode N-th: The Jedi Tournament | 18 Nov 2002 18:56 | 1 | Why this WA, Plz Help! ---------------------------------------------------------------------- program a1218; const max=502; type xlist=integer; list=array[1..max]of xlist; atype=array[1..3]of list; gtype=array[1..max,1..max]of integer; ctype=array[1..max]of integer; var name:array[1..max]of string; a:atype; b:list; g:gtype; c:ctype; i,j,n,j1,k:integer; s:shortint; st1,st2:string; ti:boolean; procedure qsort(var a : ctype;lo,hi:integer); procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; begin sort(lo,hi); end; function inarr(x:integer;var s:integer;t:integer):boolean; var i,s1,t1:integer; begin s1:=s;t1:=t;inarr:=false; for i:=s1 to t1 do if c[i]=x then begin s:=i; inarr:=true; exit; end; end; procedure printf(s,t:integer); var i:integer; begin qsort(c,s,t); for i:=s to t do writeln(name[c[i]]); end; procedure findcyc(x,dep:integer); begin for i:=1 to b[x] do begin j:=1; if inarr(g[x,i],j,dep) then begin printf(j,dep); halt; end else begin inc(dep); c[dep]:=g[x,i]; findcyc(g[x,i],dep); c[dep]:=0; dec(dep); end; end; end; begin fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do begin readln(st1); st2:=''; for j:=1 to length(st1) do if st1[j]<>' ' then st2:=st2+st1[j] else break; name[i]:=st2; j1:=j;k:=0; for j:=j1 to length(st1) do if st1[j]=' ' then inc(k) else a [k][i]:=a[k][i]*10+ord(st1[j])-48; end; fillchar(b,sizeof(b),0); for i:=1 to n do for j:=1 to n do begin s:=0; for k:=1 to 3 do if a[k][j]>a[k][i] then s:=s+1; if s>=2 then begin inc(b[i]); g[i,b[i]]:=j; end; end; ti:=true; for i:=1 to n do if b[i]=0 then begin writeln(name[i]); ti:=false; end; if ti then begin c[1]:=1; findcyc(1,1); end; end. |
|
|