PROGRAMMING.IN.TH

สำหรับโจทย์ข้อนี้ มี string $S$ ที่ประกอบด้วยตัวอักษร a หรือ b $n$ ตัว ต้องการหา substring $S[i..j]$ ลำดับที่ $k$ ตาม lexicographical order (ลำดับพจนานุกรม) ที่ตรงตามเงื่อนไข: $S_i = S_{n-i+1}$ สำหรับทุกจำนวนเต็ม $i$ ที่เป็นเลขคี่และ $1 \leq i \leq \frac{n+1}{2}$

เพื่อความสะดวกในการอธิบาย จะ

เรียกแต่ละ substring $S[i..j]$ ที่ตรงเงื่อนไขข้างต้นว่า semi-palindrome substring ของ $S$
เรียกคำตอบที่เป็นไปได้ลำดับที่ $i$ เมื่อเรียงตามพจนานุกรมว่า "สตริงคำตอบ index $i$ " โดยจะเริ่มนับจาก $i=0$ (เนื่องจากในโจทย์เริ่มนับจาก $i=1$ ดังนั้นจะต้องลดค่า $k$ ที่ได้จากข้อมูลนำเข้าไป $1$ ก่อนที่จะเริ่มคำนวณตามขั้นตอนวิธีที่จะอธิบาย)
สมมุติว่ามีสตริงคำตอบที่เป็นไปได้ทั้งหมด $m$ แบบ

แนวคิดพื้นฐาน

การแก้โจทย์ประเภท $k$ -th lexicographic string โดยทั่วไปแล้วสามารถทำได้โดยสร้าง prefix ของคำตอบขึ้นมาทีละตัวอักษร พร้อมบันทึกว่า prefix นั้นสามารถเป็นคำตอบในลำดับที่เท่าใดได้บ้างตามพจนานุกรม

สมมุติว่าตอนนี้ prefix ที่เราสร้างไว้แล้วคือ $T$ และเราทราบว่า $T$ เป็น prefix ของคำตอบ index ช่วง $[p,q)$ เราสามารถจัดการกับ $T$ ได้สามแบบคือ

ไม่เติมตัวอักษรใด ๆ แล้วนำ $T$ ไปตอบ
เติมตัวอักษร a
เติมตัวอักษร b

สามวิธีการจัดการนี้ทำให้ขอบเขตช่วง index คำตอบแบ่งเป็นสามส่วนคือ $[p,a)$ , $[a,b)$ , $[b,q)$ ตามลำดับ โดย $a$ คือ index แรกที่คำตอบทั้งหมดที่เป็นไปได้มี $T+\verb|"a"|$ เป็น prefix และ $b$ คือ index แรกที่คำตอบทั้งหมดที่เป็นไปได้มี $T+\verb|"b"|$ เป็น prefix (เป็นไปได้ที่บางช่วงอาจจะว่าง)

ในตอนแรก หากกำหนดให้ $T$ เป็นสตริงเปล่า เราจะได้ช่วง index ของคำตอบเราเป็น $[0,m)$ และเมื่อเราเลือกจัดการกับ $T$ ไปเรื่อย ๆ โดยเลือกเฉพาะช่วงที่มี index $k$ ที่เราต้องการ เราจะได้ $T$ สุดท้ายเป็นคำตอบที่เราสามารถนำไปแสดงผลได้

การที่จะนำแนวคิดที่กล่าวมามาใช้แก้โจทย์ข้อนี้ได้นั้น เราจำเป็นต้องหาได้อย่างรวดเร็วว่า ถ้าเติมตัวอักษรต่อท้าย $T$ ไปแล้ว ช่วง index ใหม่ที่ได้คือช่วงใด (จะกล่าวในหัวข้อถัดไป) เพราะเราไม่สามารถแจกแจงรูปแบบคำตอบทั้งหมดที่เป็นไปได้ภายในระยะเวลาอันสั้น

ตัวอย่างแนวคิด

หาก $S$ คือ abaababab และเราต้องการคำตอบ index $k=9$

คำตอบทั้งหมดที่เป็นไปได้ $22$ แบบ เรียงตามลำดับพจนานุกรมได้ดังนี้

0.  a        
1.  a        
2.  a        
3.  a        
4.  a        
5.  aa       
6.  aaba     
7.  aba      
8.  aba      
9.  aba      
10. abaa    
11. abaaba  
12. abaababa
13. ababa   
14. b
15. b
16. b
17. b
18. baab
19. bab
20. bab
21. babab

ตอนแรก ให้ $T$ เป็นสตริงเปล่า ช่วง index คำตอบคือ $[0,22)$

หากเราไม่เติมตัวอักษรสักตัวจะได้ช่วงใหม่เป็น $[0,0)$ (ช่วงว่าง)
หากเลือกเติม a จะได้ช่วงใหม่เป็น $[0,14)$ เลือกตัวเลือกนี้
หากเลือกเติม b จะได้ช่วงใหม่เป็น $[14,22)$

ถัดมา $T$ คือ a และช่วง index คำตอบคือ $[0,14)$

หากเราไม่เติมตัวอักษรสักตัวจะได้ช่วงใหม่เป็น $[0,5)$
หากเลือกเติม a จะได้ช่วงใหม่เป็น $[5,7)$
หากเลือกเติม b จะได้ช่วงใหม่เป็น $[7,14)$ เลือกตัวเลือกนี้

$T$ เป็น ab และช่วงใหม่เป็น $[7,14)$ โดย

หากเราไม่เติมตัวอักษรสักตัวจะได้ช่วงใหม่เป็น $[7,7)$ (ช่วงว่าง)
หากเลือกเติม a จะได้ช่วงใหม่เป็น $[7,10)$ เลือกตัวเลือกนี้
หากเลือกเติม b จะได้ช่วงใหม่เป็น $[10,14)$ (ช่วงว่าง)

สุดท้ายแล้วเราจึงได้ $T$ เป็น aba ซึ่งมีช่วง $[7,10)$ ครอบคลุม index $k=9$ ที่เราต้องการพอดี ดังนั้นจึงแสดงผลคำตอบเป็น aba

ขั้นตอนวิธีสำหรับการแก้ปัญหา

ก่อนอื่น ให้หาว่า สำหรับทุก $1 \leq i \leq j \leq n$ มี $S[i..j]$ เป็น semi-palindrome substring หรือไม่ เราสามารถใช้เทคนิค dynamic programming หาตาราง $dp[i][j]$ ได้ด้วยวิธีการคล้ายกับการตรวจสอบ palindrome substring ปกติ ดังนี้

// this code is guaranteed to always compute smaller ranges before larger ones
for (int i = n; i >= 1; --i) {
  for (int j = i; j <= n; ++j)
    dp[i][j] = (S[i] == S[j] && (i + 2 > j - 2 || dp[i + 2][j - 2]));
}

นิยามให้ $cnt[i][j]$ หมายถึง จำนวนคำตอบ (semi-palindrome substring) ทั้งหมดที่เป็นไปได้ที่เริ่มต้นด้วย $S[i..j]$ กล่าวคือ $cnt[i][j] = dp[i][j]+dp[i][j+1]+dp[i][j+2]+\cdots+dp[i][n]$

เราสามารถ $cnt[i][j]$ ได้อย่างรวดเร็วด้วย postfix sum ดังนี้

for (int i = 1; i <= n; ++i) {
  for (int j = n; j >= 1; --j)
    cnt[i][j] = cnt[i][j + 1] + (dp[i][j] ? 1 : 0);
}

เมื่อคำนวณ $dp$ และ $cnt$ เสร็จแล้ว เราสามารถ implement แนวคิดที่กล่าวไว้ในหัวข้อก่อนหน้าได้ โดยโปรแกรมจะทำงานตามลำดับดังต่อไปนี้

กำหนดให้ $T$ เป็นสตริงเปล่าความยาว $l=0$ และ $p=0$ (ไม่จำเป็นต้องเก็บค่า $q$ )
นับว่ามีกี่ substring ใน $S$ ที่ตรงกับ $T$ พอดีและเป็น semi-palindrome substring (ใช้ตาราง $dp$ ในการเช็ค)
- หากนับได้ $x$ จะได้ว่า $a=p+x$ ดังนั้น เรากล่าวได้ว่าหากไม่เติมอักษรต่อท้าย $T$ จะได้ช่วง index เป็น $[p,a)$
- หาก $k \in [p,a)$ สามารถแสดงผล $T$ เป็นคำตอบแล้วจบการทำงานของโปรแกรมได้เลย
นับจำนวน semi-palindrome substring ของ $S$ ทั้งหมดที่มี $T+\verb|"a"|$ เป็น prefix
- ทำได้โดยหาผลรวมของ $cnt[i][j]$ ที่ $1 \leq i, j \leq n$ , $j = i+l$ , $S[i..j-1] = T$ และ $S[j]=\verb|"a"|$
- หากนับได้ $y$ จะได้ว่า $b=a+x$ ดังนั้น เรากล่าวได้ว่าหากเติมตัวอักษร a ต่อท้าย $T$ จะได้ช่วง index เป็น $[a,b)$
- หากเข้ากรณีดังกล่าว ให้ย้อนกลับไปพิจารณาตั้งแต่ขั้นตอนที่ 2 ใหม่โดยกำหนดให้ $T$ มีตัวอักษร a ต่อท้าย, $l$ มีค่าเพิ่มขึ้น 1, และ $p = a$
หากไม่เข้าสองกรณีข้างต้น แสดงว่าจะต้องเอาตัวอักษร b ต่อท้าย $T$ ดังนั้น ให้กลับไปพิจารณาขั้นตอนที่ 2 โดยกำหนดให้ $T$ มีตัวอักษร b ต่อท้าย, $l$ มีค่าเพิ่มขึ้น 1, และ $p = b$ (นั่นคือได้ช่วง index เป็น $[b,q)$ )

สังเกตว่าในขั้นตอนที่ 2 และ 3 เกิดการตรวจสอบว่าแต่ละ substring ของ $S$ ตรงกับ $T$ หรือไม่ต้องใช้เวลามากถึง $O(n)$ ต่อ 1 substring

เราสามารถลดเวลาในส่วนนี้เหลือ $O(1)$ ได้โดยการเก็บ vector ของตำแหน่งเริ่มต้น substring ของ $S$ ( $i$ ) ที่ $S[i..i+l-1] = T$ ไว้ใช้ในรอบถัด ๆ ไป ทำให้ขั้นตอนที่ 2 เราสามารถดูจาก vector นี้ได้เลยว่ามีกี่ substring โดยไม่ต้องไล่นับใหม่ ส่วนขั้นที่ 3 จำเป็นต้องตรวจสอบเฉพาะ substring ที่เริ่มตาม vector นี้ว่า $S[j]=\verb|"a"|$ หรือไม่เท่านั้น

Complexity Analysis

การสร้างตาราง $dp$ และ $cnt$ ใช้เวลาอย่างละ $O(n^2)$

เราจะต้องสร้าง $T$ ทีละตัวอักษรซึ่งไม่เกิน $n$ ตัวอักษรแน่นอน แต่ละครั้งจะต้อง

พิจารณาทุก substring ใน $S$ ที่มีความยาว $l$ หรือ $l+1$ ซึ่งมี $O(n)$ สตริง
แต่ละ substring ที่พิจารณา มีการตรวจสอบแค่ตัวอักษรตัวสุดท้าย และอ่านค่าจากตาราง $dp$ , $cnt$ เท่านั้น นั่นคือพิจารณา substring ละ $O(1)$

ดังนั้น Time Complexity ทั้งหมดของวิธีนี้จึงเป็น $O(n^2)$

Space Complexity เป็น $O(n^2)$ เพราะใช้ตาราง $dp$ และ $cnt$ ขนาด $n \times n$

Implementation

ในภาษา C++:

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;

char S[N], T[N];
bool dp[N][N];
int cnt[N][N];

int main() {
  int n, k;
  scanf("%s%d", S + 1, &k);
  n = strlen(S + 1);
  --k;

  // this code is guaranteed to always compute smaller ranges before larger ones
  for (int i = n; i >= 1; --i) {
    for (int j = i; j <= n; ++j)
      dp[i][j] = (S[i] == S[j] && (i + 2 > j - 2 || dp[i + 2][j - 2]));
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = n; j >= 1; --j)
      cnt[i][j] = cnt[i][j + 1] + (dp[i][j] ? 1 : 0);
  }

  // initially, our empty substrings of S can start at anywhere (i = 1,2,..,n)
  vector<int> begins;
  for (int i = 1; i <= n; ++i)
    begins.push_back(i);

  int l = 0; // current length of T
  int p = 0; // no need to keep track of q
  while (true) {
    int x = 0, y = 0; // x is always 0 when l = 0 because we can't answer with
                      // an empty string
    for (int i : begins) {
      int j = i + l - 1;
      if (dp[i][j])
        ++x;
    }
    // add no character, go to range [p, a), end
    int a = p + x;
    if (k < a) {
      printf("%s\n", T);
      break;
    }
    // add a, go to range [a, b)
    vector<int> newbegins_a, newbegins_b;
    for (int i : begins) {
      int j = i + l;
      if (j <= n && S[j] == 'a') {
        y += cnt[i][j];
        newbegins_a.push_back(i);
      } else if (j <= n && S[j] == 'b') {
        newbegins_b.push_back(i);
      }
    }
    int b = a + y; // or p+x+y
    if (k < b) {
      T[l++] = 'a';
      p = a;
      begins = newbegins_a;
    } else { // add b, go to range [b, q)
      T[l++] = 'b';
      p = b;
      begins = newbegins_b;
    }
  }

  return 0;
}