| ENG RUS | Timus Online Judge |
Discussion of Problem 1613. For Fans of StatisticsEnigma [UB of TUIT] Why TLE#6????????? Please HELP!!!!!!! [4] // Problem 1613. For Fans of Statistics 5 Oct 2011 12:33 Deleted by author 06.10.2011 15:39 Edited by author 06.10.2011 15:40 Enigma [UB of TUIT] Re: Why TLE#6????????? Please HELP!!!!!!! [3] // Problem 1613. For Fans of Statistics 5 Oct 2011 14:17 My idea: There are 2 arrays: peoples[] and index[]. First with "quicksort" I sorted peoples[] and use "binary search". Then with AntiQuickSort I changed the array, as it appears before the first sorting and I've got TLE? Why? I don't found my misteke and I hope that you will help me!! Enigma [UB of TUIT] Re: Why TLE#6????????? Please HELP!!!!!!! // Problem 1613. For Fans of Statistics 5 Oct 2011 22:41 Anybody tell me your algo!!!!!!!!!!! Ramil Khayruddinov Re: Why TLE#6????????? Please HELP!!!!!!! [1] // Problem 1613. For Fans of Statistics 5 Oct 2011 22:58 Let's count the complexity of your algo. As I see: NlogN(sorting)+NlogN(antiqsort)+logN(to find any occurrence of people) + N/2(to find suitable number that matches a segment)= (2N+1)logN+N/2. It's only for one query. So, in total it will be N((2N+1)logN+N/2). It's too slow. Try to sort once and answer for each query using binary search. Edited by author 05.10.2011 23:01 Enigma [UB of TUIT] Re: Why TLE#6????????? Please HELP!!!!!!! // Problem 1613. For Fans of Statistics 6 Oct 2011 10:55 Thank you Ramil! You say that I should try to sort once, but how? I have three days could not decide! Edited by author 06.10.2011 10:56 Night I have WA#4 I can't find... [5] // Problem 1613. For Fans of Statistics 27 May 2011 22:59 Solution deleted by author Edited by author 06.06.2011 01:53 jlcastrillon Re: I have WA#4 I can't find... // Problem 1613. For Fans of Statistics 29 May 2011 11:09 you are blowing balloons in this excercise AterLux Re: I have WA#4 I can't find... [3] // Problem 1613. For Fans of Statistics 30 May 2011 01:50 May be there: L = 0;R = n; must be L = 1;R = n; Night No subject [2] // Problem 1613. For Fans of Statistics 1 Jun 2011 19:59 I still get wrong answer. AterLux Re: No subject [1] // Problem 1613. For Fans of Statistics 1 Jun 2011 22:49 I don't know C++ well enough. Algorithm seems to be ok Are you sure in construction sort(arr,arr+n); not sort(arr,arr[n]); ? Night Re: No subject // Problem 1613. For Fans of Statistics 6 Jun 2011 01:21 Oh thanks ... I already find my mistake. sort(arr,arr+n) are wrong sort(arr+1,arr+n+1); acceped aSSault Fast solution? [1] // Problem 1613. For Fans of Statistics 19 Apr 2011 20:23 I suppose quicksort + binary is not the optimal one. In Java I'm having TLE#10. I tried the solution by dimozzz (in another topic), but only with some optimizations I could get AC 0.91s Can anyone suggest really fast solution or the reason is that Java cannot perform better? (I didn't try in Pascal or C++). AterLux@Java Re: Fast solution? // Problem 1613. For Fans of Statistics 28 May 2011 11:56 Pavel How it can be solved? [7] // Problem 1613. For Fans of Statistics 4 Apr 2008 03:50 How to solve it?) Quick sort with binary search gets TLE on the 10'th test, and binary search tree - on the 9'th one! Брэнд * [5] // Problem 1613. For Fans of Statistics 4 Apr 2008 15:28 I did it! Hint for all: quicksort + binary search works. Pavel Re: * [4] // Problem 1613. For Fans of Statistics 4 Apr 2008 18:05 Can you show your code?) Or send it to my e-mail: 0x6fwhite@gmail.com Брэнд * [3] // Problem 1613. For Fans of Statistics 4 Apr 2008 20:30 I can tell my idea. a[i] - numbers of people, b[i] - numbers of towns. I sort it. First sorting - array a, second sorting - if a[i]=a[j] then you must sort b[i] and b[j]. And finally use binary search. That's all) Pavel Re: * [1] // Problem 1613. For Fans of Statistics 5 Apr 2008 02:53 Hmm. I do the same) But, I think, I do it some more simple. I use structure <people, year>. I sort the array of this type by people... And then I use binary search. Shit! But it gets TLE! I write my programs in PASCAL. Where do you do it? In C++ ? Maybe it works faster... Temp_for_one_day Re: * // Problem 1613. For Fans of Statistics 15 Apr 2008 01:59 Pavel, it doesnt matter, pascal or C++, its depends on only your brains, how your program works.. Your algo seems to be right, but think about your bin.search realization. Try to find endless cycle, for example. Good luck ;) Crash_access_violation Re: * // Problem 1613. For Fans of Statistics 7 May 2008 03:42 thanks... I got AC... Edited by author 08.05.2008 01:10 georgi_georgiev Re: How it can be solved? // Problem 1613. For Fans of Statistics 2 Sep 2009 02:45 I just sort the array and use lower bound Bobur strange!!! [1] // Problem 1613. For Fans of Statistics 4 May 2008 21:56 i did it problem qsort+binarysearch and i've TLE#3, but with simple search i've TLE#6; Denis Koshman Re: strange!!! // Problem 1613. For Fans of Statistics 5 Aug 2008 05:28 I use built-in C 'qsort' and custom binary search routines (find-equal, find-first-greater-eq, find-last-less-eq). AC in 0.156 sec Li Wang Ji WA#4... WHY? My algo is here... [2] // Problem 1613. For Fans of Statistics 26 May 2008 02:53 I wrote simple Binary search but got WA#4... Where is my mistake? Maybe there are some special cases... Can you help me, please? Thanks in advance... SPb SU 14 Re: WA#4... WHY? My algo is here... [1] // Problem 1613. For Fans of Statistics 30 May 2008 17:37 I had wa4 and this test helped me to get AC: 6 1 0 1 0 0 1 6 2 2 1 1 1 1 3 3 1 4 4 1 6 6 1 4 5 1 // correct answer is 011010 Howard Liu Re: WA#4... WHY? My algo is here... // Problem 1613. For Fans of Statistics 31 May 2008 02:26 Try using the STL lower_bound for binary search. It really cuts down potential errors on edge cases. titan What is the best Data Structure for this problem? [4] // Problem 1613. For Fans of Statistics 4 Apr 2008 22:30 Alias aka Alexander Prudaev Re: What is the best Data Structure for this problem? // Problem 1613. For Fans of Statistics 4 Apr 2008 22:52 the array. just array of integer. int a[N]; but i have used vector<int> v[N]; array of dynamic arrays. each number in first array in input we must associate with some smaller number from 1 to N for this purpose i have used map<int, int> but it can be hashtable, hashmap or just another array + binary search. svr Re: What is the best Data Structure for this problem? [2] // Problem 1613. For Fans of Statistics 4 Apr 2008 22:59 Forum says that 1613 most interesting problem in last list. This is because sorting one of the most fundamental idea in algorithmics. Concerning to this problem my advise: struct data{ int val; int num; }; bool operator <(struct data d1,struct data d2) { if (d1.val<d2.val)return 1; if (d2.val<d1.val)return 0; if (d1.num<d2.num) return 1; return 0; } After that we should make qsort, leftmost and right most binary search and so on. More exactly: Let l r x- inqure; and i1=leftmost(l,x); i2=rightmost(r,x); if ((i1!=-1)&&(i2!-1)&&(i1<i2)&&(data[i1]==x)&&(data[i2])==x)- Ok Edited by author 04.04.2008 23:08 titan Re: What is the best Data Structure for this problem? [1] // Problem 1613. For Fans of Statistics 5 Apr 2008 03:13 I used map and vector with stl sort function got AC, but my solution time is 0.6s then I try to solve it by hash table with Double hash key, but i can't improve the time, and i got .91s. i increas the array lenghts to 2pow17 and hash key is : key% (2pow17-1) // it's prime rh key is: (i+(1+key% (2pow17-2) ) % (2pow17-1) but it appear that isn't good way. plz tell me your solutions with high performance titan hurray: AC with 0.125 and 1100KB // Problem 1613. For Fans of Statistics 5 Apr 2008 18:39 zhhy_oi why I was TLE? // Problem 1613. For Fans of Statistics 2 Apr 2008 18:54 I used a trie to record the question numbers,but why I was TLE on test 10? Could anybody help me or tell me something about test 10? E-mail:zhhy_oi@163.com Edited by author 02.04.2008 18:57 Emil Pls help with quick sort [2] // Problem 1613. For Fans of Statistics 30 Mar 2008 23:13 Can any body wright me code of quick sort? It's a very important thing,but i don't know it. KIRILL(ArcSTUpid coder:) Re: Pls help with quick sort [1] // Problem 1613. For Fans of Statistics 31 Mar 2008 00:17 sort array mas of integer between l and r Procedure Qsort(l,r:integer); var x,i,j,y:integer; begin i:=l; j:=r; x:=mas[(l+r) shr 1]; repeat while mas[i]<x do inc(i); while mas[j]>x do dec(j); if i<=j then begin y:=mas[i]; mas[i]:=mas[j]; mas[j]:=y; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; Ferman Re: Pls help with quick sort // Problem 1613. For Fans of Statistics 31 Mar 2008 13:51 procedure sort(r,l:longint); var i,j,x,b:longint; begin i:=r; j:=l; x:=ar[(i+j) div 2]; repeat while ar[i]>x do inc(i); while ar[j]<x do dec(j); if i<=j then begin b:=ar[i]; ar[i]:=ar[j]; ar[j]:=b; inc(i); dec(j); end; until i>j; if j>r then sort(r,j); if l>i then sort(i,l); end;
|