góc học tập nhỏ xíu của bạn zon béo ú

Tuesday, September 12, 2017

Giải thuật Manacher - Tìm xâu con đối xứng dài nhất với độ phức tạp tuyến tính

Bài gốc:

http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

Longest Palindromic String – Xâu con Đối xứng Dài nhất | Phần 1

Bài toán: Cho một xâu, hãy tìm xâu con đối xứng dài nhất (LPS).

Ví dụ: Với xâu “forgeeksskeegfor” thì LPS là “geeksskeeg”

Cách 1 (Brute Force – Duyệt trâu bò)

Cách này chỉ đơn giản là xét từng xâu con có đối xứng hay không.

Chạy 3 vòng lặp với 2 vòng là tìm (từng bước một) chỉ số đầu và cuối của xâu con và 1 vòng là xét xâu con có đối xứng không.

Độ phức tạp thời gian: O(n^3)

Độ phức tạp phụ: O(1)

Code Java

Cách 2 (Dynamic Programning – Quy hoạch động)

Giảm độ phức tạp bằng cách chứa các kết quả phụ.

Bảng boolean table[n][n] được đổ dần từ dưới lên.

table[i][j]=true nếu xâu con từ i đến j đối xứng, và ngược lại

Thuật toán:

Gọi k là độ dài xâu con đối xứng đang xét

+ table[i][i]=true với mọi i (k=1)

+ check các vị trí table[i][i+1] (k=2)

+ với k=3:

- nếu table[i+1][j-1]==true và s[i]==s[j] thì table[i][j]=true.

- và ngược lại

Độ phức tạp thời gian: O(n^2)

Không gian nhớ phụ: O(n^2)

Code Java

Cách 3: Sinh ra tất cả các xâu đối xứng và lưu vết LPS

+ Sinh PS độ dài lẻ: từ tâm khai triển ra hai hướng để tìm LPS

+ Sinh PS độ dài chẵn: từ hai tâm khai triển ra hai hướng để tìm LPS

Độ phức tạp thời gian: O(n^2)

Không gian nhớ phụ: O(1)

Code Java

Thuật toán Manacher – Tìm LPS với thời gian tuyến tính | Phần 1

Như đã nói, có thể tìm PS bằng cách khai triển ra hai hướng từ tâm.

+ Với PS độ dài lẻ:

Ví dụ, với xâu “abababa”

ở đây tâm là ký tự thứ 4 (chữ “b” màu đỏ). Các kí tự bên trái và phải cách tâm cùng độ dài tương ứng nhau nên xâu này đối xứng

(các kí tự tưong ứng nhau có cùng màu)

+ Với PS độ dài chẵn:

Ví dụ, với xâu “abaaba”

ở đây coi vị trí giữa hai ký tự là tâm (dấy gạch màu đỏ). Các kí tự bên trái và phải cách tâm cùng độ dài tương ứng nhau nên xâu này đối xứng

(các kí tự tưong ứng nhau có cùng màu)

Để tìm LPS của xâu s có độ dài N, có một cách là lấy 2*N+1 tâm (với N ký tự, N-1 vị trí giữa hai kí tự và 2 vị trí ngoài cùng). Với mỗi vị trí, ta giả sử nó là tâm rồi xét từng cặp ký tự theo hai hướng trái phải với từng tâm ấy, có lưu vết để tìm LPS

Wednesday, October 12, 2016

Hướng dẫn nộp bài bằng JAVA trên SPOJ

Chào các bạn! Hôm qua có bạn hỏi mình một số vấn đề khi nộp bài bằng Java trên SPOJ, mình đoán cũng nhiều bạn mới bắt đầu nên còn khá bỡ ngỡ, trước mình cũng loay hoay mãi mới sub được bài Hello World, nên chia sẻ chút mong là bài viết này giúp được phần nào cho các bạn.

Trang chủ SPOJ: http://www.spoj.com/
Trang SPOJ trường mình: http://www.spoj.com/PTIT/
Để sub được bài trên SPOJ thì cần đăng ký nick: http://www.spoj.com/register/ và đăng nhập vào account đã nhé.

Ok, giờ bắt đầu sub các bài basic của trường mình nhé: http://www.spoj.com/PTIT/problems/basic/ những bài này thì thuật toán cũng khá dễ học :D

Trước hết sub bài Hello PTIT nhé: http://www.spoj.com/PTIT/problems/HELLOPOJ/
Bài này chỉ cần in ra dòng chữ "Hello PTIT OJ." là được :D
Bấm nộp bài

Ở trang này:

Chọn ngôn ngữ là Java (Java SE 8u51)
Paste code của bạn vào ô mã nguồn hoặc bấm chọn tệp để chọn file code của bạn. Lưu ý: Sub code ở đây cũng như ở trang http://ideone.com/. Bạn không được để ~~package~~ ở đây, không được để class là ~~public~~ nếu không nộp sẽ bị lỗi! (chỉ riêng tên class là Main thì mới được để public thôi)
Bấm nộp bài

Giờ ngồi chờ kết quả thôi :D

Nếu có kết quả xanh là bạn đã code đúng yêu cầu đề bài rồi :D chúc mừng nhé!

Còn nếu sub cam thì có thể rơi vào những trường hợp sau đây:

Biên dịch gặp lỗi: Bạn chọn ngôn ngữ sai hoặc do thiếu thư viện
SIGSEGV: Khai báo bị tràn mảng. Không được khai báo mảng quá lớn

~~int []a = new int [100000000];~~
~~int [][]b = new int[10000][10000];~~

NZEC: Thường là truy cập đến chỉ số mảng sai (OutOfBoundsException, mảng của bạn khai báo chỉ có 3 phần tử mà bạn lại truy cập đến chỉ số thứ 4,5 chẳng hạn) hoặc do chia 0, input sai (khi nhập xâu bị rỗng chẳng hạn)...
Chạy quá thời gian: Bạn lưu ý thường thì mỗi bài có yêu cầu về thời gian chạy, thường là 1 giây (tương ứng với việc bạn có thể chạy 1 vòng for từ 1 đến 100 triệu thì vẫn được chấp nhận, nhưng đến 1 tỷ thì sẽ bị out)
Làm sai: Lỗi này khi bạn có ouput cho một test nào đó khác với yêu cầu

Một vài lưu ý khác:

Vào ra đều dạng chuẩn, tức là bằng màn hình, tức là dùng luồng System.in và System.out.

Bạn có thể tăng tốc vào ra bằng cách thay Scanner và System.out bằng các luồng khác như BufferedReader và BufferedWriter chẳng hạn (Ví dụ như bài này http://www.spoj.com/problems/TSORT/ không thể nào nhập vào bằng Scanner được, quá time ngay!) Đây là code bài này của mình

Hãy nhập input và hiển thị output đúng như yêu cầu của đề bài, tức là bạn hãy đọc kỹ đề bài và xem dạng input và output mẫu. Chỉ cần thừa dấu chấm dấu xuống dòng đều có thể nhận "Kết quả sai" đấy!

Bạn chỉ được nộp duy nhất 1 file (tức duy nhất 1 class) nên nếu bạn cần tạo 1 class nào khác, hãy để nó là inner static class (để có thể dùng trong hàm main) thì nộp mới được chấp nhận.
Ví dụ:

Lưu ý miền giá trị của input: Ví dụ trong bài xử lý số, nếu đề bài cho số <=10^9 thì các bạn có thể dùng int, còn <=10^18 thì hãy dùng long, còn lớn hơn nữa, thì nên nhập như String rồi xử lý bằng BigInteger xem sao (nếu được cho phép :v). Và cũng có thể trong quá trình tính toán của bạn, số sẽ tràn kiểu, ví dụ số int (max) nhân số int (max) sẽ ra số long chẳng hạn

Lưu ý thời gian yêu cầu: Như mình đã nói ở trên, 1 giây ứng với chạy 1 vòng for từ 1 đến 100 triệu, cho nên để không bị quá time, bạn nên tính xem code của mình chạy trong bao lâu, và nếu không thích hợp phải đổi phương án khác. Ví dụ như bài sinh xâu nhị phân độ dài n thì nếu dùng thuật toán sinh sẽ mất 2^n thao tác lặp, vậy nên nếu n=100 chẳng hạn thì không thể chạy trong vòng 1 giây được.

Cách thêm thư viện vào Android Studio

*Bài gốc: http://androidmastermind.blogspot.co.ke/2016/06/adding-library-in-android-studio-custom_22.html

Có nhiều cách để thêm thư viện ngoài vào Android Studio. Yêu cầu kết nối mạng.
Bạn chỉ cần cấu hình cho một project, lần sau bạn có thể import cùng thư viện đó vào các project khác mà không cần kết nối mạng nữa. :D

Cách 1: Dùng file gradle
+ Vào trang maven repository , trang này có rất nhiều thư viện
+ Trên thanh tìm kiếm gõ tên thư viện

+ Chọn thư viện bạn cần (thường là kết quả đầu tiên)
+ Chọn version bạn muốn import vào project của mình (thường là bản mới nhất cho nó máu :v)

+ Ở trang mới bật ra có nhiều tab như maven, gradle... mình cứ chọn gradle

+ Copy cái dòng này vào file build.gradle (của module app) là xong

+ File build.gradle sau khi thêm thư viện.

apply plugin: 'com.android.application'
android {
    compileSdkVersion 23

    buildToolsVersion "24.0.0"

    defaultConfig {
        applicationId "com.androidmastermind.glide"

        minSdkVersion 15

        targetSdkVersion 23

        versionCode 1

        versionName "1.0"    }
    buildTypes {
        release {
            minifyEnabled false

            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'        }
    }
}

dependencies {
    compile fileTree(dir: 'libs', include: ['*.jar'])
    testCompile 'junit:junit:4.12'    compile 'com.android.support:appcompat-v7:23.4.0'

    //Glide library

    compile group: 'com.github.bumptech.glide', name: 'glide', version: '3.7.0'
}

+ Nhấn tùy chọn Sync Now rồi chờ một lát là xong

Cách 2: Thêm thư viện bằng file jar
+ Vào trang maven repository và tải file jar về.
+ Chuyển về Project Mode ở thanh Project Explore rồi paste cái file jar ấy và thư mục libs

+ Chuột phải vào cái file jar đấy rồi chọn "Add As Library"

+ Chọn module để thêm thư viện

+ Xong chờ nó sync là được.

Cách 3: Thêm bằng Project Structure
+ Chọn File > Project Structure (hoặc nhấn tổ hợp phím Ctrl+Alt+Shift+S, hoắm bấm vào biểu tượng này