Show all threads Hide all threads Show all messages Hide all messages | How fast could recursion optimised? | 👾_challenger128_[PermSNRU] | 1298. Knight | 2 May 2022 12:12 | 2 | My AC recursion for n=8 gives about 8250733 calls. What is the minimum recursive calls value? My recursion gives only 64 for n=8. I sort moves by count of free cells that can be reached from them. | What's wrong with test #3? | [SESC USU] Komarov && Kantorov | 1298. Knight | 11 Jun 2018 21:54 | 5 | I solved this problem using backtracking with optimization( you start from some position and then you go to the position that has the fewest future possible moves...//from other post). But it's WA 3. Then I checked the answers of my program myself and all was correct.Then I wrote a simple checker for this problem. And it said all right. Then I tried to save the answers(firstly my answers then answers from forum) as the constants in the program. And the answer was WA 3 again. Help me, please!!! P.S. Sorry for my English. Edited by author 12.09.2005 23:16 Edited by author 12.09.2005 23:21 But your solution is wrong! Thank you for answer. I found the mistake in my code and now I got AC! At me the same problem!!! I do not know in what a mistake. Help, please. | Chess problem...TLE on test #10!! how to make it faster????? | michel mizrahi | 1298. Knight | 13 Jan 2018 01:57 | 9 | I really stuck with this, I don't know how to make my algorithm faster here is my code: #include <stdio.h> char board[10][10]; char letter[66],num[66]; int n,s=0,ncuad; int pos_f[8]={-1,-2,-2,-1, 1, 2, 2, 1}; int pos_c[8]={-2, 1,-1, 2, 2, 1,-1,-2}; init_board(){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) board[i][j]='0'; } search(int i,int f,int c){ int j=0; if(s==1) return 0; if(board[f][c]=='0'){ board[f][c]='1'; switch(f){ case 1: letter[i]='a';break; case 2: letter[i]='b';break; case 3: letter[i]='c';break; case 4: letter[i]='d';break; case 5: letter[i]='e';break; case 6: letter[i]='f';break; case 7: letter[i]='g';break; case 8: letter[i]='h';break; } num[i]=c; if(i==ncuad) s=1; while(j<8 && s==0){ if((f+pos_f[j])>0 && (f+pos_f[j])<=n) if((c+pos_c[j])>0 && (c+pos_c[j])<=n) search(i+1,f+pos_f[j],c+pos_c[j]); j++; } board[f][c]='0'; } } int main(){ int i,j; scanf("%d",&n); ncuad=n*n; init_board(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) search(1,i,j); if(s){ for(i=1;i<=ncuad;i++) printf("%c%d ",letter[i],num[i]); return 0; } else printf("IMPOSSIBLE\n"); return 0; } if someone can help me I would appreciate a lot!! Precalc (-) Dmitry 'Diman_YES' Kovalioff 12 May 2005 12:22 else begin writeln('a1'); writeln('b3'); writeln('a5'); writeln('b7'); writeln('d8'); writeln('c6'); writeln('b4'); writeln('a2'); writeln('c3'); writeln('b1'); writeln('a3'); writeln('b5'); writeln('a7'); writeln('c8'); writeln('b6'); writeln('a4'); writeln('c5'); writeln('a6'); writeln('b8'); writeln('d7'); writeln('f8'); writeln('e6'); writeln('d4'); writeln('c2'); writeln('e3'); writeln('d1'); writeln('b2'); writeln('c4'); writeln('d6'); writeln('e8'); writeln('g7'); writeln('f5'); writeln('e7'); writeln('g8'); writeln('f6'); writeln('h7'); writeln('g5'); writeln('e4'); writeln('d2'); writeln('f1'); writeln('h2'); writeln('f3'); writeln('e1'); writeln('g2'); writeln('h4'); writeln('g6'); writeln('h8'); writeln('f7'); writeln('h6'); writeln('g4'); writeln('e5'); writeln('d3'); writeln('c1'); writeln('e2'); writeln('g1'); writeln('h3'); writeln('f2'); writeln('h1'); writeln('g3'); writeln('h5'); writeln('f4'); writeln('d5'); writeln('c7'); writeln('a8'); end; thanks! but can I ask you two questions...? first, how many time takes in your computer if you run my code to get the solution for n=8? because my computer is veryy slow and get stuck and number two is it any way to solve it the problem without precalc?? (sorry for my bad english) and thanks again!!! :D:D:D:D:) byee! and good luck! I didn't use precalc. I calculated answer for N using answer for N-1 if it was not 'No Solution' I took first N moves from it. Use the priority array for the chessboard : void init() { int a,b,c; int chessboard[8][8]={0}; int direction[8][2]= { {2,1},{-2,1},{2,-1},{-2,-1}, {1,2},{-1,2},{1,-2},{-1,-2}, }; for(a=0;a<n;a++) { for(b=0;b<n;b++) { int count=0; for(c=0;c<n;c++) { int x1 = a+direction[c][0]; int y1 = b+direction[c][1]; if(x1>=0&&x1<n&&y1>=0&&y1<n) count++; } chessboard[a][b] = count; } } } For example, n = 8 : 2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 go to the cell with minimum priority first ! Good luck ! Edited by author 17.02.2009 12:04 Edited by author 17.02.2009 12:04 How can here be >=10 tests if 1<=n<=8? | Possible solution. | Mahilewets | 1298. Knight | 17 Jul 2017 01:28 | 1 | You can have an array deg[i][j] = count of adjacent unvisited cells for cell (i;j). While doing DFS sort edges by non-decreasing deg[i+move. first] [j+move. second]. It calls an heuristic after some scientist whose name begins at W. | Hint | Bekzhan | 1298. Knight | 5 May 2014 11:39 | 2 | Hint Bekzhan 23 Nov 2012 23:12 Backtracking works on this problem) I wrote code, using it, and i thought it'll got TL. But when I tried, it get AC) (Sorry for my poor english) The running time of a simple backtracking search will depend on the move search order you use. For example, this order: moves = [ a, e, f, b, c, g, h, d ] where a = (1,-2) b = (1,2) c = (-1,2) d = (-1,-2) e = (2,1) f = (2,-1) g = (-2,1) h = (-2,-1) works great for n = 7, but not 6 or 8. | It's strange. My prog runs faster when n=8 than when n=7. | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1298. Knight | 5 May 2014 11:22 | 2 | If you use a simple depth first search, your run time will depend on the order in which you examine the possible moves. For example, always examining the moves in this order yields a TLE: (1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1). To get the fastest solutions you'll want to adapt the search order at each node in the search tree, but you can get an AC with a static search order. | recursion? | [OSTU]Svetkin | 1298. Knight | 1 Apr 2014 18:16 | 9 | Recursive algorithm seems to slow for n=8. Actually, it depends on the order of moves, but the order fast for n=8 was slow for 6 or 7, the fast one for 7 was slow for 8 and so on... Anyway, I used pregenerated output to solve this. Is there a way to optimize the algorithm? there is a greedy solution but non-demonstrable: you start from some position and then you go to the position that has the fewest future possible moves... here are the solutions that I've computed with this: for n = 5, 6, 7 and 8; N = 5: "a1","b3","a5","c4","e5","d3","e1","c2","a3","b1","d2","e4","c5","a4","b2","d1","e3","d5","b4","a2","c1","e2","c3","b5","d4" N = 6: "a1","b3","a5","c6","e5","f3","e1","c2","a3","b1","d2","f1","e3","f5","d4","b5","d6","c4","b6","a4","b2","d1","f2","e4","f6","d5","c3","a2","b4","a6","c5","e6","f4","d3","c1","e2" N = 7: "a1","b3","a5","b7","d6","f7","g5","e6","g7","f5","e7","g6","f4","g2","e1","c2","a3","b1","d2","f1","g3","e2","g1","f3","d4","b5","a7","c6","b4","a2","c1","d3","b2","a4","b6","c4","e5","d7","c5","a6","c7","d5","c3","d1","e3","g4","f2","e4","f6" N = 8: "a1","b3","a5","b7","d8","f7","h8","g6","f8","h7","g5","h3","g1","e2","c1","a2","b4","a6","b8","c6","a7","c8","e7","g8","h6","g4","h2","f1","d2","b1","a3","c2","e1","f3","h4","g2","e3","d1","b2","a4","c3","b5","d4","f5","d6","c4","e5","d3","f2","h1","g3","e4","c5","d7","b6","a8","c7","d5","f4","e6","g7","e8","f6","h5" i used back and got AC in 0.46 .... I got AC in 0.031s . But I not just submit the answer. I just use DFS. Edited by author 26.06.2004 10:16 I do it in 0.015 sec I don`t use CONSTANT solv I am also use DFS and AC in 0.718s. Why my program slowly from you? What is your fu*king dfs solutions? how did u manage that it is impossible! My answer accepted in 0.734 sec I also used DFS Edited by author 01.04.2014 18:17 I wonder: my recursive solution for n=8 works faster than for n=7. you may be not use recursion. you may draw on sheet this and type answer to program... | Hint | ASK | 1298. Knight | 20 Nov 2012 02:16 | 3 | Hint ASK 22 Feb 2010 21:12 http://delphiforfun.org/Programs/knights_tour.htm A technique known as Warnsdorf's heuristic allows us to make much better choices for next move than random selection. The heuristic, discovered by H. C. von Warnsdorf in 1823 tells us to select as our next move the one which has the fewest choices for moving on from there. This heuristic works so well that , although I have implemented backtracking to remove bad choices, I have yet to see a move retracted while making a tour Re: Hint MOPDOBOPOT (USU) 19 Nov 2012 23:35 Warnsdorf's idea works in linear time! Amazing power of human mind.. :) | Help me please | Roma Labish[Lviv NU] | 1298. Knight | 3 Oct 2011 20:33 | 2 | I had use Warnsdorff heuristic, but I take wrang answer.. Maybe you can find my bug? #include <iostream> using namespace std; struct minimum { int minp; int i; int j; minimum():minp(9999),i(0),j(0){} }; int d[9][9]; bool isnuje_hid(int i, int j,int n) { if(i <= n && i >= 1 && j <= n && j >= 1) return true; else return false; } int reytung(int i,int j,int n) { int k = 0; if(!d[i][j]) { if(isnuje_hid(i+2,j+1,n))k++; if(isnuje_hid(i+1,j+2,n))k++; if(isnuje_hid(i+2,j-1,n))k++; if(isnuje_hid(i+1,j-2,n))k++; if(isnuje_hid(i-2,j+1,n))k++; if(isnuje_hid(i-2,j-1,n))k++; if(isnuje_hid(i-1,j+2,n))k++; if(isnuje_hid(i-1,j-2,n))k++; } else return -1; return k; } void zrobyty_hid(int & i, int & j,int n) { minimum a; if(isnuje_hid(i+2,j+1,n)) if(reytung(i+2,j+1,n) < a.minp && reytung(i+2,j+1,n) > 0) { a.minp = reytung(i+2,j+1,n); a.i = i + 2; a.j = j + 1; } if(isnuje_hid(i+1,j+2,n)) if(reytung(i+1,j+2,n) < a.minp && reytung(i+1,j+2,n) > 0) { a.minp = reytung(i+1,j+2,n); a.i = i + 1; a.j = j + 2; } if(isnuje_hid(i+2,j-1,n)) if(reytung(i+2,j-1,n) < a.minp && reytung(i+2,j-1,n) > 0) { a.minp = reytung(i+2,j-1,n); a.i = i + 2; a.j = j - 1; } if(isnuje_hid(i+1,j-2,n)) if(reytung(i+1,j-2,n) < a.minp && reytung(i+1,j-2,n) > 0 ) { a.minp = reytung(i+1,j-2,n); a.i = i + 1; a.j = j - 2; } if(isnuje_hid(i-2,j+1,n)) if(reytung(i-2,j+1,n) < a.minp && reytung(i-2,j+1,n) > 0) { a.minp = reytung(i-2,j+1,n); a.i = i - 2; a.j = j + 1; } if(isnuje_hid(i-2,j-1,n)) if(reytung(i-2,j-1,n) < a.minp && reytung(i-2,j-1,n) > 0) { a.minp = reytung(i-2,j-1,n); a.i = i - 2; a.j = j - 1; } if(isnuje_hid(i-1,j+2,n)) if(reytung(i-1,j+2,n) < a.minp && reytung(i-1,j+2,n) > 0) { a.minp = reytung(i-1,j+2,n); a.i = i - 1; a.j = j + 2; } if(isnuje_hid(i-1,j-2,n)) if(reytung(i-1,j-2,n) < a.minp && reytung(i-1,j-2,n) > 0) { a.minp = reytung(i-1,j-2,n); a.i = i - 1; a.j = j - 2; } if(i && j) { i = a.i; j = a.j; } d[i][j] = 1; } char convert(int n) { switch(n) { case 1: return 'a'; case 2: return 'b'; case 3: return 'c'; case 4: return 'd'; case 5: return 'e'; case 6: return 'f'; case 7: return 'g'; case 8: return 'h'; } } int main() { int n; cin >> n; if(n < 5 && n > 1){cout << "IMPOSSIBLE"; return 0;} int m = 1,k = 1; d[1][1] = 1;d[0][1] = 1;d[1][0] = 1;d[0][0] = 1; for(int i = 1; i <= n*n; i++) { cout << convert(m) << k << endl; zrobyty_hid(m,k,n); } return 0; } Edited by author 27.02.2007 00:32 Edited by author 27.02.2007 02:42 My algorithm based on Warnsdorff rule got AC. Check your realisation. | Забавно | Michail Yudin | 1298. Knight | 14 Jan 2009 18:21 | 1 | Забавно Michail Yudin 14 Jan 2009 18:21 моя прога Uses SysUtils,Math; {$APPTYPE CONSOLE} var i,f,j,n,c,x,y,x1,y1:integer; a:array [-1..10,-1..10] of byte; b:array[1..8] of char=('a','b','c','d','e','f','g','h'); procedure proc(k,l:integer); var min,i1,j1:integer; begin for i1:=-2 to 2 do for j1:=-2 to 2 do if (abs(i1)+abs(j1)=3) and (a[k+j1,l+i1]=0) then inc(min); if min<c then begin c:=min; x1:=k; y1:=l end;
end; begin {$ifndef online_judge} reset(input,'input.txt'); rewrite(output,'output.txt'); {$endif} fillchar(a,sizeof(a),1); readln(n); for i:=1 to n do for j:=1 to n do a[i,j]:=0; case n of 1:writeln('a1'); 2:writeln('IMPOSSIBLE'); 3:writeln('IMPOSSIBLE'); 4:writeln('IMPOSSIBLE') else begin x:=1; y:=1; f:=0; repeat c:=10; a[x,y]:=1; writeln(b[x],y); for i:=-2 to 2 do for j:=-2 to 2 do if (abs(i)+abs(j)=3) and (a[x+j,y+i]=0) then proc(x+j,y+i); inc(f); x:=x1; y:=y1; until f>=sqr(n); end; end; end. Фишка в том, что прога оптимально(!) обходит псведошахматную доску с заданными размерами ребер n<=8 и находит решение по обходу доски конем, чтобы он только один раз наступал на одно поле(я проверял), но правда, поскольку решение отличается от того что в тестах, приишлось сдать массивом конастант... обидно. Если есть возражения, пишите! | Funny... | CHIDEMYAN SERGEY | 1298. Knight | 31 Jul 2007 17:02 | 1 | Funny... CHIDEMYAN SERGEY 31 Jul 2007 17:02 I think,when n=1 answer is "IMPOSSIBLE",but really right answer is "a1". | LOOK | And IV | 1298. Knight | 10 Jul 2007 07:21 | 1 | LOOK And IV 10 Jul 2007 07:21 | WA#3! it's impossible , there is only 8 test and my program gives right results for all n | Alias (Alexander Prudaev) | 1298. Knight | 26 Mar 2007 22:57 | 4 | [code deleted] Edited by moderator 27.03.2007 09:45 if replace char[8][8] by char [64][64] my program works for n=63 :) 2admis: I realy don't know why i got wa#3 my program work on all my test, please test my program your self. and look at my motto :) Edited by author 26.03.2007 22:10 :) stupid test Thank you Edited by author 26.03.2007 23:00 | WA on test #9? I can't understand because 1<=n<=8 | Ras Misha [t4ce] | 1298. Knight | 5 Jan 2007 11:16 | 2 | Maybe in some tests n < 1 or n > 8? | I don't know why my solution CE (Compilation Error) | thuchoithoi | 1298. Knight | 10 Jun 2006 23:15 | 4 | how about posting your source code? It may be useful I submit a const table .Why CE? | what is a funny tests ! | MSU Teminator | 1298. Knight | 16 Jan 2006 20:40 | 2 | in the problem statement 1<=n<=8. therefore the maximum of the data tests is 8. why there are test 10, test 9. The first two tests are samples. Then follow n = 1, 2, ... 8. | Please help!!! Why my code get Crash (ACCESS_VIOLATION) #4? | REM | 1298. Knight | 11 Jun 2005 16:55 | 8 | Program Acm_Timus_Ru_1298; const dy:array [1..8] of integer=(-2,-2,-1,1,2,2,1,-1); dx:array [1..8] of integer=(-1,1,2,2,1,-1,-2,-2); g:array [1..8] of char=('a','b','c','d','e','f','g','h'); var a:array [-5..15,-5..15] of longint; k,i,j,ip,min,h,x,y,rem:longint; n : longint; p : boolean; Function mo(x,y:integer):boolean; Begin if (x>n) or (x<1) or (y>n) or (y<1) then mo:=false else mo:=a[x,y]=0; End; Function hm(x,y:integer):byte; Var i:integer; Begin k:=0; if not(mo(x,y)) then k:=n*n else for i:=1 to 8 do if mo(x+dx[i],y+dy[i]) then k:=k+1; hm:=k; End; BEGIN readln(n); if (n>=1) and (n<=8) then begin fillchar(a,sizeof(a),0); x:=1;y:=1; for i:=1 to n*n do begin min:=n*n; a[x,y]:=i; for j:=1 to 8 do begin h:=hm(x+dx[j],y+dy[j]); if h<min then begin ip:=j; min:=h; end; end; x:=x+dx[ip]; y:=y+dy[ip]; end; p:=true; for i:=1 to n do for j:=1 to n do if a[i,j]=0 then p:=false; if p=false then begin writeln('IMPOSSIBLE');end else for k:=1 to n*n do for i:=1 to n do for j:=1 to n do if a[i,j]=k then writeln(g[i],j); end else writeln('IMPOSSIBLE'); END. I think the problem is here- x:=x+dx[ip]; y:=y+dy[ip]; may be ip is invalid since it might not be updated. When all the neighbor squares return hm()>=min value, ip will not get updated. It's very intresting! I compiled given source code both on Delphi and FreePascal and checked each program on every possible tests (n from 1 to 8) and I didn't get Access Violation. I am really confused if this code get Access Violation on Timus Judge System. It's very interesting, I wrote a new program in which answers for 5,6,7,8 were constants (which I defined by my program which gets Crash on a server), and I got AC. Admins! Can you give some clarification to this situation? Is it a crash of the program or a Judge? Add ip:=7862341 line after BEGIN, and you'll get crash in both Delphi and FreePascal. I know that ip was not initialized. Delphi gave that warning, but why does the same program run different on my home machine and on timus server. I have no crashes on all possible tests. How do you compile sources exactly? If variable is not initialized it may have arbitrary value, that depends on many factors. It must work different on different machines! |
|
|