|
|
вернуться в форумStructure vector<int>Pos[100][100] gave Ac. With O(lgN) find(S) and O(N) insert(S) where S- new position set<int>Pos[100][100] led to MLE Thus only all position generating without any combinatorical counting. Who can advice more effective structure for store position, please, do it. Does your algo gives right answers on all possible tests? I see you use only ~5Mb Do you store all positions? More efficient structure is simple liniear array:) I Qsort it and found different elements P.S. I understand your algo it's not fast but it works Edited by author 11.03.2007 14:05 My algo absolute correct and simple It simply build all possible two-moving new positions and store them in vector<int>Poses[100][100] where If S[0..4]- new position then value 10001*S[2]+101*S[3]+S[4] stored in Poses[S[0]][S[1]]. You opinion that array[] better than vector<int> does't understand me fully because we must have dynamic structure and maxsize 10000 unacceptible. Edited by author 11.03.2007 18:32 Edited by author 11.03.2007 18:33 Edited by author 11.03.2007 18:34 Yes. It is possible to use common array. But using char Poses[3300000][5] will give MLE. Therefore because 100<128=2^7 it is enaught 35 bit for one position. Or ~12Mbait for all matrix. After apply qsort and count differet copies moving along sorted array. Thank for effective advice. Follow it i will try to be in first 10 on 1425. 35 bit is bad for adressing max num of positions is <2900000 (test: 5 100 50 50 50 50 50) so you can store all But when I tried qsort array[3000000] of string[5] I got TLE You can store position as integer+byte=5 byte And it can be sorted fast enough But I got MLE in this case (array[3000000]*5) ... strange Any case it's not easy do it less then 1 sec 3000000 values for qsort it's not small:)
Edited by author 11.03.2007 21:46 I will use variant of my idea. int *Poses[100][100] array of pointers to dynamic memory. Use int Buffer[100] for periodic increasing taken memory. After it apply qsort and count in each Poses[i][j]. Shue that time will diminish without MLE Edited by author 11.03.2007 22:15 Edited by author 11.03.2007 22:28 Many dimensional arrays and dynamic memory will work slow IMHO Why you stil don't solve 1220 :) It's more interesting in coding If you need help with 1220 mail me, but I think you can solve it yourself easily Because 1220 as i undestood needs stable sorting on place. I couldn't find in literature algos for stable sorting without additional memory. Continuing! Thank for Reminder very much! I was thinking about 1220(Stacs) 1 year ago and failed. Now, after training in timus I can solve it. I tried to manage stable sort on PUSH A B rows and couldn't pack A and B in Int type. But it possible to work with POP A rows and in for each such row in int type variable there is place for A and number of POP or for stable information. After it each PUSH A B row can O(lg N) find corresponding POP in POPs part of global array. push and pop in O(1) but I think it better discuss in other thread or mail:) KIRILL!! I got AC(1220) making stable sorting using bubble sort in 10 segments of Push data with size of <=10000 yes:) but easy ways not for us:) It can be solved with self organazed lists and own 3 byte type byte mas[700001] (blocks by 7 byte) and int last[1001] for pointers on last value in mas Edited by author 13.03.2007 14:23 Edited by author 13.03.2007 14:24 |
|
|