Nov 232009
 

B – Menghitung Palindrom

Author: Suhendry Effendy
Problem: klik di sini

Dengan panjang string tidak lebih dari 100, solusi O(n3) dengan cara bruteforce sudah cukup untuk menyelesaikan soal ini. Yang perlu kita lakukan hanya menguji semua substring yang bisa dibentuk.

Bagaimana jika panjang string tidak lebih dari 1000? Untuk ini kita perlu mengoptimasi solusi kita menjadi O(n2). Hal ini bisa dilakukan dengan melakukan bruteforce hanya pada titik tengah palindrom, kemudian diuji seberapa banyak palindrom yang bisa dibentuk dengan titik tengah tersebut (ekspansi ke kiri dan kanan).

36 peserta berhasil menyelesaikan soal ini.

Solusi C/C++
oleh Suhendry Effendy

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

bool ispalin(char s[], int a, int b) {
  while ( a <= b ) {
    if ( s[a] != s[b] ) return false;
    a++, b--;
  }
  return true;
}

int main()
{
  int T;
  scanf( "%d", &T );

  while ( T-- ) {
    char s[105];
    scanf( "%s", s );
    int len = strlen(s);
    int ans = 0;
    for ( int i = 0; i < len; i++ )
      for ( int j = i; j < len; j++ )
        if ( ispalin(s,i,j) ) ans++;
    printf( "%d\n", ans );
  }

  return 0;
}

Solusi PASCAL
oleh Eko Wibowo

function ispalin(s:string; a, b:longint): boolean;
  begin
  while ( a <= b ) do
  begin
    if ( s[a] <> s[b] ) then
    begin
      ispalin := false;
    exit;
    end;
    a := a + 1;
    b := b - 1;
  end;
  ispalin := true;
end;

var
  T, i, j, len, ans: longint;
  s: string;
begin
  readln(T);
  while ( T > 0 ) do
  begin
    T := T - 1;
    readln(s);
    len := length(s);
    for i := 1 to len do
      for j := i to len do
        if ( ispalin(s,i,j) ) then ans := ans + 1;
    writeln(ans);
  end;
end.


  6 Responses to “BNPCHS 2009 – Qualification Round”

  1. saya kecewa 🙁

  2. Gw pas liat di Google Reader nongol “Suhendry’s Blog (1)” wah udah kesenengan gw akhirnya blog entah INC atawa ICPC nongol… Gak taunyaaaaa…… >>>>>>.<<<<<<<

    Hmm… jangan2 blog INC/ICPC teralu susah yah shu ;)) jadi ditunda2 mulu. Kalo HS aja langsung nongol ;))

  3. oh iya, ada ilham juga… doh, kabur dolo ah xD

  4. wkkwkwkwkwkw… gile shu… BNPCHS kluar dluan…. event belakangan, writeup keluar dluan….

  5. su…..where r u know???????

  6. hehe…mas shu lagi jd tersangka…:)

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)