| ENG RUS | Timus Online Judge |
Обсуждение задачи 1494. МонобильярдAlexey What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [11] // Задача 1494. Монобильярд 2 ноя 2006 18:48 Samsonov Alex [USU] Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [9] // Задача 1494. Монобильярд 3 ноя 2006 18:13 What do you mean by "ALMOST O(n)"? Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [8] // Задача 1494. Монобильярд 4 ноя 2006 11:19 I mean that I have a loop to read data. It is O(n). But in it I have a loop for checking. In most cases it is about some iterations, but there are some tests that make my algo O(n^2). How to make it faster? svr Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [7] // Задача 1494. Монобильярд 4 ноя 2006 12:34 I think that next sketch is O(N) Let x[1]...x[N]- revisor sequence k- Current number of an element of x under consideration NN- number of balls in billiard pocket now +last ball x[k] xx[]- aray of balls now in billiard pocket for moment k + last ball x[k] S-number of operations //Begining k=1 ;NN=x[1]; xx[]=[1..NN];//array assignment- x[1]- operations S:=x[1]; // Loop aa: j:=0; while (x[k+j]==xx[NN-j]) j++ //revisor takes seguental balls //from Billiard pocket;S:=S+j; k=k+j- next position if (k==N+1) "«Not a proof». END NN=NN-j; //number of balls in pocket after Session of taking; S:=S+1; m1=xx[k1]- next ball after timeout If (m1<=m) -"Cheater"//meet number smallet than taken xx[NN+1..NN+m1-m]:=[m+1..m1];// new sequence in billiard pocket //under ptevious rest S+=m1-m operations NN:=NN+m1-m;//renew S=S+1; goto aa //Loop The resume: S<=2*N -- O(N) Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [5] // Задача 1494. Монобильярд 4 ноя 2006 16:06 I have such algo: a[0..100000]. a[i] means minimal number that can be taken after i not to be a cheater. during reading datas i have to cerrect the massive. but there are some tests that I must correct more than one element. I takes me a loop. So, TLE. P. S. I don't understand your algo ) Can you mail me "_magistr.90@mail.ru" ? We can speak Russian (or Ukrainian ;) ) UdSU: Ajtkulov, Kotegov, Saitov Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [4] // Задача 1494. Монобильярд 5 ноя 2006 11:16 It's just a stack modelling. You should suppose player not to be a cheater. Then he just puts balls into the pocket one by one: 1, 2, 3... until the last ball is the next ball to be checked. So, this ball should be removed. And so on. When the process is finished just check if the pocket is empty. svr Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [3] // Задача 1494. Монобильярд 5 ноя 2006 12:13 Yes! And in my algoritnm xx[]- stac; NN- it's capacity; Alexey Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [2] // Задача 1494. Монобильярд 5 ноя 2006 15:12 ANW, TLE#14 ((( Olzhas2dy Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) [1] // Задача 1494. Монобильярд 30 июн 2007 16:05 For everyone who has TLE, use priority_queue. It is probably not the best solution, but it takes up only few lines. Dusan Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) // Задача 1494. Монобильярд 13 май 2008 03:50 can you give me link where I can find algo or code for priority_queue? Neizvestnii Re: What is the algo? I have almost O(n). But TLE#16. Help, please. (-) // Задача 1494. Монобильярд 30 июн 2007 18:28 to svr: I don't know 2 things in you algoritm: ->m1=xx[k1]- next ball after timeout What is k1? ->If (m1<=m) -"Cheater"//meet number smallet than taken What is m? Please help me Брэнд O(n^2) // Задача 1494. Монобильярд 21 мар 2008 19:28 O(N^2) works! Time - 0.984 seconds))) Edited by author 21.03.2008 19:29 |