## 4 Implementation and Running Time
He stores \(3\) non-changing arrays (see bellow), a changing Boolean array \(B_{m}\), a dequeue (double-ended queue), two pointers, the number \(P_{m}\) of preferred women (relative to his fiancee, such that the number of maidens who are within the same tie with his fiancee), and his status (originally lad). The first array \(W_{m}\) contains all the acceptable women in non-increasing order of priorities. The second array \(PR_{m}\) contains the corresponding priorities at \(m\). The third array \(I_{m}\) stores the relative positions, such that if \(m\) is in the \(i\)th position in the list of woman \(W_{m}(j)\) then \(I_{m}(j)=i\) (by our assumption these are known at the beginning). He keeps \(B_{m}(j)=\)True, if \(W_{m}(j)\) is a maiden, and False otherwise. This array is initialized to all-True, and an item is changed to False, when he gets the corresponding message from a woman. The first pointer \(f_{m}\) points to the first woman of the current tie, and the second one \(n_{m}\) points to the first woman on \(m\)'s list, who has strictly lower priority than the woman pointed by \(f_{m}\). At the beginning, for all acceptable women \(w=W_{m}(j)\), man \(m\) sends a message \((m,i,j)\) to \(w\), where \(i=I_{m}(j)\) (and woman \(w\) stores \(I_{w}(i)=j\)). At the beginning \(m\) is a lad, and he considers the first woman on his list, \(f_{m}\) points to her (such that \(f_{m}=1\)), and remember her priority \(p\). He scans his list until finding a woman with lower priority than \(p\), and changes \(n_{m}\) pointing to this woman (if he reaches the end of the list then he defines \(n_{m}=\infty\)). While scanning he checks every woman \(w\) whether she is a maiden. If yes then he puts \(w\) in front of his dequeue, else (if \(w\) is engaged) he puts \(w\) at the end of his dequeue. Meanwhile he counts the maidens in the dequeue and stores this number in \(P_{m}\). Whenever he gets a message \"engaged\" and has to change the corresponding value of \(B_{m}\), he also checks whether the sender is in the dequeue (such that for her index \(j\) we have \(f_{m}\leq j<n_{m}\)), and if yes, then he decreases \(P_{m}\). Whenever he is asked whether he is uncertain, he returns yes, if and only if \(P_{m}>0\). Then he takes the first element out of the dequeue, and proposes to this woman. Whenever man \(m\) gets a rejection from \(w\), he first checks whether \(w\) is flighty (this is equivalent to check whether \(P_{m}>0\)), if yes, he puts back \(w\) at the end of the dequeue. Then he takes the first element out of the dequeue and checks whether she is a maiden. If this is not the case then he puts back this woman at the end of his dequeue, and takes the next one from the front. Otherwise he proposes to this woman. Otherwise, if \(P_{m}=0\) then he checks whether the dequeue is empty. If not then he simply takes the first woman from the dequeue and proposes to her. When the dequeue is empty, he rather proceeds as follows. He first changes \(f_{m}\) to \(n_{m}\). If \(f_{m}=\infty\) at the first time then he changes his status to bachelor, and reset \(f_{m}\) to 1. If \(f_{m}=\infty\) at the second time then he changes his status to old bachelor, and finishes. Starting from this new \(f_{m}\) he makes a new dequeue the same way as above (calculating \(P_{m}\) meanwhile), and adjust his pointer \(n_{m}\). Then he processes the new dequeue as before. From this local algorithm the linear time global algorithm also follows easily, only we have to get rid of our assumptions. This can be done using the famous linear time radix sort, as follows. First we sort triplets of form \((\mathrm{pri}(m,w),m,w)\) for all acceptable pairs \(mw\) (this set of triplets can be collected from men). After sorting we scan this list, and build up the sorted arrays \(W_{m}\) of men easily. Next every woman \(w\) subscribe each quadruplet \((m,w,0,i)\) to the central authority, where \(i\) is the index of man \(m\) in \(w\)'s list.