ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1322. Spy

How to solve this problem?
Posted by Garbage Collection 16 Apr 2004 17:41
Who can give me some hint ?
Re: How to solve this problem?
Posted by Gheorghe Stefan 16 Apr 2004 20:05
it's a linear algorithm, although classic I think. You can search the web for Burrows Wheeler algorithm, that's it's name. The solution is something like this: the first column contains the letters sorted. You have the last one (column). You start from the given position (line) in the first column. you see the element in the last one and also it's counter from its type: example: if it is an 'a' and in the last column, upwards, it was another 'a', than its id is 2. Now you go to the position in the first column for this 'a', the second. And so on...
Re: How to solve this problem?
Posted by Alone alone ! 19 Apr 2004 02:04
 input_seq----sorted_seq
 1---------------10
 2----------------9
 3>>start1-------1
 4---------------11-<<match3-"abr"
 5---------------8
 6---------------2
 7>>start2------3<<--match1-"a"
 8---------------4
 9---------------5
 10--------------6
 11>>start3-----7-<<-match2-"ab"


and so on.



Edited by author 19.04.2004 02:16
Re: How to solve this problem?
Posted by vvvvvv 20 Apr 2004 00:37
More About Burrows-Wheels visit
http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/burrows.html
   To this problem, I think the kernel is how to make the next-element array of the INPUT data but not to get the result step by step.
   As an example,
0  a a b r a c a d a b r   2
1  a b r a a b r a c a d   5
*2 a b r a c a d a b r a   6
3  a c a d a b r a a b r   7
4  a d a b r a a b r a c   8
5  b r a a b r a c a d a   9
6  b r a c a d a b r a a   10
7  c a d a b r a a b r a   4
8  d a b r a a b r a c a   1
9  r a a b r a c a d a b   0
10 r a c a d a b r a a b   3
    To get the no.2 string,and we have got the last column.If we start with this original,the most easy way is to use the squence of the string array:
    the end of row 2 = a
    next to seek the suffix of 'a' in row 2:
    You may sort the whole to form the head of each row.And the head is just the suffix for each end of row.
    But if the input is special Your sort program would run out of the time.(Only 1/4 sec)

    Changing the way of thinking may useful why not start with prefix.please watch row 0 and row 9, it's easy to find difference. r in 0 row is end but is head in 9 row.
    In row 9 the suffix of end 'b' is r,right?
    And how about the num of row 9 comes from?
    9=3<four as >+2<2 bs>+1<1 c>+1<1 d>+0<0 r before this 'r'>
    And the suffix of b is just 'r'<row 0>.
    So when construct the next array,input[i],we may proceed as follow:
    next[s[i]+p[i]]=i
    <s[i] is the array that record the number of sign  before each kind of letter appereance in the head in the sorted array (as 4a 2b 1c 1d in example)
     p[i] is the array that recored the number of same sign before this sign appreance(as 0 r in example)>
    if the data structure is all right, you may be accepted in only 0.04 sec.

Edited by author 20.04.2004 00:39