Killever's blog

String to Palindrome
By Killever, 13 years ago, In English

First click HERE to see the problem

my solution get TLE in some testcases click HERE to see my code
any one can tell me how to solve this problem :)
Thanks.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You'd better describe your solution verbally if you want to receive answer sooner. Not many people are interested in attempting to read your "code".
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    let me trace my code on example "ABBYY"
    i make function take the string s and int i ,j
    i-->start
    j-->end
    so first i will send to it "ABBYY",0,4
    check s[0]==s[4]
    if this true no need to swap
    case not true
    i loop in two direction
    first direction is right
    ------>
    if i found value equal to s[4] then i can make
    swaps untill s[0]=s[4]
    second direction
    <------
    the same idea
    then i make my string equal to min swaps string
    so in this case
    the string will convert from ABBYY to YABBY 
    throw this sequence   ABBYY-> ABYBY-->AYBBY-->YABBY
    so first and last letter the same and so on i will send to function
    YABBY , 1 , 3
    and so on untill  i>j then i will break
    finally i think the algorithm results is true but  i get TLE 
    note: max string length is 1000000 
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You mean that if length of the string is L, then your algorithm for each of ~L symbols would loop through ~L other symbols.

      That means your algorithm is "quadratic" in the meaning of how time of work depends on the amount of incoming data.

      Since max string length is about 1e6, max number of operations of your algorithm is (roughly) about 1e12. But 1-2 seconds of running example is sufficient (very roughly) only for about 1e7 operations (surely it depends on used language and judge hardware etc).

      Therefore I suspect that this problem requires very different solution (maybe almost "linear" in the meaning of time spent).

      I could not invent such a solution right now, but it should exist (according to limit of 1000000). Could you find it yourself?

      However I did not regard that there are very few different symbols (26)... However you did not check if string could be "palindromed" at all before working with it...
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
An O(n) solution exists. Let me give you a hint for start:
Classify the letters into three groups:
1. The left side letters in the palindrome
2. The middle letter
3. The right side letters
If it's not enough I can give you more hints!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    more hints :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Now you have an string like 1132313 from some string like ABABBCC. Calculate the minimum number of swaps needed to sort the string like 1112333 to get something like CABBCA (this is not optimal). The order of letters in their group is not important. Try to solve this sub-problem yourself. If you couldn't then read the next line:
      An inversion in a1, ..., an is a pair of indices i, j (i < j) such that ai > aj . Count the number of inversions in and unsorted sequence and see what happens when you swap two adjacent elements like what bubble sort does. Then try two figure out how to calculate the number of inversions in a sequence of 1,2,3 in O(n). This is the minimum number of swaps needed!
      Now we get to the next step to solve the problem. Tell me when you're done with this step to give you some hints on the next step (If you needed!). What we did in this step was to take the elements to their final zone (but not exact place).
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        (you have an string like 1132313 from some string like ABABBCC )
        I can't understand what you mean :)
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          You should work more thoroughly on "hints". He mean that for each letter of the string you could define whether it is "left" letter of the pair (1), "right" (3) or the lonely middle letter (2). That is how you get string like "1132313". The way in which you should obtain such a string is a simple exercise.
          → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          At first we wanted to classify the letters. First half of occurrences of a specific letter would be in group 1 and the second half would be in group 3. the middle one (if exists) would be in group 2.
          The example string and the group number is A1 B1 A3 B2 B3 C1 C3.
          This means that the first C should be finally in the first half. Or the second B should be in the middle. It says for each letter what half of the final string (the palindrome) it belongs to.
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
sorry , i know number of B's is 3 so you have to put one B in the middle and so you classified second B-->2
so your algorithm must know the numbers of each character before classification ?
how to calculate the number of inversions in a sequence of 1,2,3 in O(n). 
and what's the next step ?
i'm sorry if my questions Bother you , but i'm still beginner so, sorry for that 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes. You need the count of each letter. The classification is doable in O(n).
    Did you count the number of inversions in O(n)? You can do this by counting for each element the number of elements with a greater value than the current element. For example the number of inversions in 321213 is 0+1+2+1+3+0 = 7.
    If you're done with this tell me to continue.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      OK continue :)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Now you have a string of form X O Y. where O has length at most 1. X is the first half, O middle and Y is the second half. In CABBBCA we have X = "CAB", O = "B" and Y = "BCA". To make this string a palindrome we should find an string Z and swap elements of X to obtain Z and swap elements of Y to obtain reverse of Z. define d(P, Q) for two strings P and Q the minimum number of swaps needed to obtain Q from P. Prove the triangle inequality for function d(P, Q). I mean prove that for any three string P, Q and R we have d(P, R) + d(R, Q) >= d(P, Q). Let Y' be the reverse of Y. Suppose we have found Z with minimum number of swaps necessary to make the string a palindrome. We know that d(X, Z) + d(Z, Y') >= d(X, Y'). This means that we need at least d(X, Y') swaps. So it's sufficient to build a palindrome with d(X, Y`) swaps. Consider Z = X. In this way we have to obtain XOX' from XOY. And only d(X, Y') swaps are needed. So to find the overall minimum number of swaps you have to compute d(X, Y')+(Number of swaps we did when we wanted to sort classes 1,2,3). This is the answer. DONE! You can compute d(P, Q) in O(n). It's like counting inversion. Consider P a sorted version of Q. Now count the inversions in Q according to P. Like the way we did before.
        Good Luck!
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks,finally got it :)
→ Reply