meirbekbolatbekov002's blog

How can I optimize Palindrome Reorder problem's solution on CSES.fi?
By meirbekbolatbekov002, history, 5 years ago, In English

This code passes majority of testcases on CSES.fi except the ones from 6-9 for which I keep getting TLE. Tried many times, but could not fix it. Any hints?

Link to the problem

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

SOLVED! But anyway, I want to know on which part you'd possibly make optimizations.. In case your method differs with mine it might be a pretty useful insight to know ^_^

→ Reply
  • »
    »
    5 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    String concatenation may take a lot of time, as it copies the whole string a, add a char, then write the resulting string to a (This actually depends on some factor, such as the language, compiler, etc, I dont really understand about that too). Instead of building the string ans, you can decide whether an answer exist (the d value in your code) and if it does, print the output as you go through the array cnt[] twice, one for the first half of the answer, and the other for the second half.

    Relevant blog : https://mirror.codeforces.com/blog/entry/94701

    Edit : Added a link to relevant blog

    → Reply