Các tips hữu ích trong cuộc thi ACM (Phần 1)?

GÕ PHÍM NHANH HƠN

Không đùa đâu! Mặc dù mẹo này có thể không có ý nghĩa nhiều nhưng khi bạn và đối thủ cạnh tranh cùng có thể giải được một số bài nhất định, nó sẽ được quyết định bởi kỹ năng mà bạn có bao gồm khả năng viết code rõ ràng, hợp lý và ... tốc độ đánh máy.

Hãy thử bài kiểm tra đánh máy này tại

về cách cải thiện kỹ năng đánh máy của bạn.

Ngoài việc có thể nhập ký tự chữ và số một cách nhanh chóng và chính xác, bạn cũng cần phải làm quen với vị trí của các ký tự ngôn ngữ lập trình được sử dụng thường xuyên: ngoặc đơn () hoặc {} hoặc dấu ngoặc vuông [] hoặc dấu ngoặc nhọn <>, dấu chấm phẩy; và dấu hai chấm: "" cho các ký tự, dấu ngoặc kép "" cho các chuỗi, dấu hiệu &, thanh dọc |, dấu chấm than !, v.v ... Thực hiện một chút, hãy thử nhập mã nguồn C ++ dưới đây càng nhanh càng tốt:

#include <stdio.h>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 100005

#define f1(i,n) for (int i=1; i<=n; i++)

int n, m, cnt;

vector<int> a[N];

int Visited[N], Parent[N];

void visit(int u){

   cout << "Visiting " << u << endl;

   Visited[u]=++cnt; // travesal time

   for (int i=0,v; v=a[u][i]; i++)

   if (v!=Parent[u]){

       if (!Visited[v]){

           Parent[v]=u;

           visit(v);

       }

   }

}

main(){

   cin >> n >> m;

   f1(i,m) {

       int p, q;

       cin >> p >> q;

       /*do {

           p=rand()%n+1;

           q=rand()%n+1;

       } while (p==q);

       cout << p << " " << q << endl;*/

       a[p].push_back(q);

       a[q].push_back(p);

   }

   f1(i,n) a[i].push_back(0);

   f1(i,n) if (!Visited[i]) visit(i);

   cout << "Travesal time: " << endl;

   f1(i,n) cout << Visited[i] << " ";

   cout << endl;

   cin.ignore(2);

}

XÁC ĐỊNH NHANH LOẠI BÀI TOÁN

Trước khi bắt đầu code, điều đầu tiên chúng ta cần phải làm được là xác định được loại bài toán để tìm ra thuật toán giải quyết tương ứng. Các dạng bài toán mà chúng ta có thể gặp là

- Tham lam

- Chia để trị

- Quy hoạch động

- Đồ thị

- Toán học

- Xử lý xâu

- …

PHÂN TÍCH THUẬT TOÁN

Khi bạn thiết kế thuật toán để giải quyết một vấn đề nào đó trong một cuộc thi lập trình, bạn phải tự hỏi mình rằng: Với các giá trị input đạt tới lớn nhất thì thuật toán hiện tại, với độ phức tạp về thời gian và không gian như vậy, có đảm bảo bài code của bạn không vượt qua giới hạn mà đề bài đã cho hay không?

Đôi khi, có nhiều cách để tiếp cận một vấn đề. Một số cách tiếp cận có thể không chính xác, những cách khác lại không đủ nhanh, và còn có những cách 'overkill'. Một chiến lược tốt là suy nghĩ các thuật toán có thể sử dụng và sau đó chọn giải pháp đơn giản nhất có hiệu quả tốt hơn cả (nghĩa là phải nhanh đủ để vượt qua giới hạn thời gian, bộ nhớ và vẫn đưa ra câu trả lời chính xác)

Máy tính hiện đại khá nhanh và có thể xử lý đến 2x10^8 phép tính trong 1 giây. Bạn có thể sử dụng thông tin này để xác định xem thuật toán của bạn sẽ chạy trong thời gian bao lâu. Ví dụ: nếu kích thước đầu vào tối đa là 10^5 và thuật toán hiện tại của bạn có một phức tạp thời gian O (n^2), như vậy nó sẽ thực hiện khoảng 10^10 phép tính, một con số rất lớn và chắc chắn thuật toán của bạn sẽ bị gặp vấn đề về quá time với những bài ACM khi thường cho giới hạn 1-5 s. Vì vậy, bạn sẽ cần phải đưa ra một thuật toán nhanh hơn (và cũng chính xác) để giải quyết vấn đề.

#CodeBattle2018