|
|
| Show all threads Hide all threads Show all messages Hide all messages | | WA4 | reshke'` | 2060. Subpalindrome pairs | 15 May 2020 15:38 | 2 | WA4 reshke'` 12 Mar 2018 20:58 Does anyone know what this could be related to? Re: WA4 Alikhan Zimanov 15 May 2020 15:38 I found the following test when got WA4:
INPUT: aaa
OUTPUT: 4 | | Spoiler (don't even open if u want to solve by yourself) | jk_qq | 2060. Subpalindrome pairs | 22 May 2017 20:39 | 1 | Use Manacher's algo for comprehensive list of palindroms and try to calc 2 arrays:
beg[i] - number of palindroms begins at position i,
end[i] - number of palindroms ends at position i.
after that ans = beg[i + 1] * end[i] for every i.
To calc arrays you can use either O(n) offline (+=cnt at beg -= cnt after end; then sum) or efficient data structures.
Edited by author 22.05.2017 20:40 | | WA1 | Felix_Mate | 2060. Subpalindrome pairs | 19 Aug 2016 12:07 | 1 | WA1 Felix_Mate 19 Aug 2016 12:07 My algo is right. Now i have AC. My problem is input string. I rewrite my program on Pascal (i use ANSISTRING) and got AC.
Edited by author 21.08.2016 18:31 | | Please Help. | Spyro | 2060. Subpalindrome pairs | 4 Nov 2015 11:26 | 3 | Sorry to blunt, but I don't understand the meaning of the task.
Explain what needs to be done. Examples of chewing the tasks:
abaa
1. i = 1, j = 1, k = 2; ' a ' and ' b ' palindromes
2. i = 1, j = 3, k = 4; ' aba ' and ' a ' palindromes
3. i = 2, j = 2, k = 3; ' b ' and ' a ' palindromes
4. i = 2, j = 2, k = 4; ' b ' and ' aa ' palindromes
5. i = 3, j = 3, k = 4; ' a ' and ' a ' palindromes
Russian text:
Разжевывание примера из задачи:
abaa
1. i=1, j=1, k=2; 'a' и 'b' палиндромы
2. i=1, j=3, k=4; 'aba' и 'a' палиндромы
3. i=2, j=2, k=3; 'b' и 'a' палиндромы
4. i=2, j=2, k=4; 'b' и 'aa' палиндромы
5. i=3, j=3, k=4; 'a' и 'a' палиндромы you can use Manacher's algorithm. |
|
|
|
