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