EIU Olympic Contest 2026
Bài
Tất cả bài tậpThông báo
| Thời gian | Tiêu đề | Mô tả |
|---|---|---|
| Tháng 11 12, 2026, 18:40 | Hint Subtask 5 - Problem D: Tree Path |
Khi đồ thị là một cây, giữa hai đỉnh bất kỳ chỉ tồn tại duy nhất một đường đi đơn. Hãy sử dụng DFS hoặc BFS để xác định đường đi từ 1 đến N và tổng trọng số của nó. Sau đó, đánh dấu những đỉnh thuộc đường đi này. Việc xóa một đỉnh nằm trên hoặc ngoài đường đi sẽ ảnh hưởng đến đáp án như thế nào? |
| Tháng 11 12, 2026, 18:40 | Hint Subtask 5 - Problem C: Optimized Digit DP |
Với Q lớn và R ≤ 10¹⁸, hãy tìm cách tái sử dụng những trạng thái Digit DP không phụ thuộc vào giới hạn cụ thể của từng truy vấn. Xây dựng hàm F(X) đếm số cân bằng từ 1 đến X, sau đó tính đáp án [L, R] bằng hiệu hai kết quả tiền tố. Những trạng thái nào có thể tiền xử lý một lần? |
| Tháng 11 12, 2026, 18:39 | Hint Subtask 5 - Problem B: Prime Factorization |
Với M ≤ 10¹², việc duyệt từng số đến căn bậc hai có thể mất nhiều thời gian khi xử lý nhiều truy vấn. Hãy thử phân tích M thành tích các lũy thừa nguyên tố. Từ số mũ của từng thừa số, liệu bạn có thể tính số lượng ước mà không cần liệt kê chúng? |
| Tháng 11 12, 2026, 18:39 | Hint Subtask 5 - Problem A: Top K Elements |
Vì K ≤ 10, chúng ta không nhất thiết phải lưu tất cả phần tử trong mỗi Node của Segment Tree. Hãy thử chỉ lưu tối đa 10 giá trị lớn nhất theo thứ tự giảm dần. Khi gộp hai Node, làm thế nào để tạo danh sách mới mà vẫn giữ đúng những phần tử lớn nhất, kể cả giá trị trùng nhau? |
| Tháng 11 12, 2026, 18:21 | Hint Subtask 4 - Problem D: Dijkstra Optimization |
Với N ≤ 1000 và Q ≤ 100, hãy thử chạy Dijkstra riêng cho từng truy vấn bằng Priority Queue và danh sách kề. Bạn có thể bỏ qua các cạnh dẫn đến đỉnh bị chặn mà không cần thay đổi đồ thị ban đầu. Nếu cùng một đỉnh x xuất hiện nhiều lần, liệu có thể lưu kết quả để tránh tính toán lại? |
| Tháng 11 12, 2026, 18:20 | Hint Subtask 4 - Problem C: Digit DP |
Khi R đạt 10⁹, việc duyệt từng số trở nên quá chậm. Hãy thử sử dụng Digit DP để đếm số cân bằng không vượt quá một giới hạn X. Trạng thái có thể lưu vị trí đang xét, chênh lệch số chữ số chẵn và lẻ, trạng thái giới hạn và việc số đã bắt đầu hay chưa. Đừng quên xử lý chữ số 0 ở đầu! |
| Tháng 11 12, 2026, 18:20 | Hint Subtask 4 - Problem B: Divisor Counting |
Khi M đạt 10⁵, việc tính trực tiếp Fₘ không còn phù hợp. Hãy tìm hiểu tính chất UCLN giữa hai số Fibonacci và mối liên hệ với UCLN của các chỉ số. Liệu điều kiện Fᵢ chia hết Fₘ có thể chuyển thành một bài toán đếm ước của M và giải bằng cách duyệt đến căn bậc hai? |
| Tháng 11 12, 2026, 18:19 | Hint Subtask 4 - Problem A: TreeSet Frequency Counting |
Vì giá trị phần tử không vượt quá 50, hãy sử dụng TreeSet[value] để lưu các vị trí xuất hiện của từng giá trị. Khi cập nhật, xóa vị trí khỏi TreeSet cũ và thêm vào TreeSet mới. Với truy vấn [L, R], hãy duyệt giá trị từ 50 xuống 1, sử dụng subSet() để đếm số vị trí thuộc đoạn và giảm K tương ứng cho đến khi tìm được đáp án. |
| Tháng 11 12, 2026, 18:00 | Hint Subtask 3 - Problem D: Priority Queue |
Khi N tăng lên 1000 nhưng chỉ có một truy vấn, Floyd có thể trở nên quá chậm. Hãy thử biểu diễn đồ thị bằng danh sách kề và sử dụng Dijkstra kết hợp Priority Queue. Trong quá trình duyệt, bỏ qua đỉnh x cùng các cạnh liên quan. Đừng quên sử dụng kiểu long để lưu khoảng cách. |
| Tháng 11 12, 2026, 18:00 | Hint Subtask 3 - Problem C: Combinatorics |
Với L = 1 và R = 10ᵏ, hãy nhận xét rằng số cân bằng phải có số chữ số chẵn và lẻ bằng nhau. Thử sử dụng tổ hợp để chọn vị trí cho từng loại chữ số, sau đó đếm số cách điền chữ số hợp lệ. Hãy chú ý chữ số đầu tiên không được bằng 0 và xét riêng giá trị 10ᵏ. |
| Tháng 11 12, 2026, 17:59 | Hint Subtask 3 - Problem B: BigInteger Precomputation |
Với M ≤ 500 nhưng Q có thể rất lớn, việc tính toán lại Fibonacci và kiểm tra chia hết cho từng truy vấn sẽ gây lãng phí thời gian. Hãy thử sử dụng BigInteger để tiền xử lý các số Fibonacci và tính sẵn đáp án cho mọi M từ 3 đến 500. Sau đó, mỗi truy vấn chỉ cần tra cứu kết quả. |
| Tháng 11 12, 2026, 17:59 | Hint Subtask 3 - Problem A: Minimum Query |
K = R - L + 1 nghĩa là cần tìm phần tử nhỏ nhất trong đoạn [L, R]. Hãy thử áp dụng Segment Tree tương tự Subtask 2, nhưng thay phép toán Max bằng Min. Liệu cách xây dựng cây và cập nhật phần tử có cần thay đổi nhiều không? |
| Tháng 11 12, 2026, 17:41 | Hint Subtask 2 - Problem D: Repeated Floyd |
Khi N vẫn nhỏ nhưng Q tăng lên 100, hãy thử thực hiện Floyd–Warshall riêng cho từng đỉnh bị phong tỏa. Mỗi lần xử lý, hãy khởi tạo lại ma trận khoảng cách và bỏ qua đỉnh x. Liệu sử dụng Dijkstra với danh sách kề có giúp giảm thời gian nếu số cạnh không quá lớn? |
| Tháng 11 12, 2026, 17:40 | Hint Subtask 2 - Problem C: Prefix Sum |
Khi Q tăng nhưng R ≤ 10⁶, việc duyệt lại toàn bộ đoạn cho mỗi truy vấn sẽ gây lãng phí thời gian. Hãy tiền xử lý một mảng Prefix Sum, trong đó mỗi vị trí lưu số lượng số cân bằng từ 1 đến vị trí đó. Từ mảng này, làm thế nào để trả lời truy vấn [L, R] trong O(1)? |
| Tháng 11 12, 2026, 17:40 | Hint Subtask 2 - Problem B: BigInteger |
Khi M tăng lên 500, các số Fibonacci sẽ vượt quá giới hạn của kiểu long. Hãy thử sử dụng BigInteger để biểu diễn và tính toán chính xác những số rất lớn. Tương tự Subtask 1, bạn có thể duyệt các số Fibonacci và sử dụng phép chia lấy dư để kiểm tra tính chia hết. |
| Tháng 11 12, 2026, 17:40 | Hint Subtask 2 - Problem A: Maximum Query |
K = 1 đồng nghĩa với việc chỉ cần tìm phần tử lớn nhất trong đoạn [L, R]. Thay vì duyệt toàn bộ đoạn cho mỗi truy vấn, hãy thử sử dụng Segment Tree để lưu giá trị Max. Cấu trúc này có thể hỗ trợ cả cập nhật một phần tử và truy vấn giá trị lớn nhất. |
| Tháng 11 12, 2026, 17:24 | Hint Subtask 1 - Problem D: Floyd |
Với N ≤ 100 và chỉ có một truy vấn, hãy thử xây dựng ma trận khoảng cách và sử dụng thuật toán Floyd–Warshall. Khi khu vực x bị phong tỏa, cần bỏ qua đỉnh này trong quá trình tìm đường đi. Hãy chú ý trường hợp không tồn tại đường đi, có nhiều cạnh nối cùng hai đỉnh hoặc x là đỉnh xuất phát hay đích. |
| Tháng 11 12, 2026, 17:24 | Hint Subtask 1 - Problem C: Brute Force |
Với R ≤ 1000, hãy duyệt lần lượt từng số trong đoạn [L, R]. Đối với mỗi số, tách từng chữ số và đếm xem có bao nhiêu chữ số chẵn, bao nhiêu chữ số lẻ. Nếu hai số lượng bằng nhau thì tăng đáp án. Liệu một số có độ dài lẻ có thể thỏa mãn điều kiện không? |
| Tháng 11 12, 2026, 17:23 | Hint Subtask 1 - Problem B: Brute Force |
Với M ≤ 90 và số lượng truy vấn nhỏ, hãy sinh dãy Fibonacci bằng kiểu dữ liệu long. Sau đó, duyệt qua các số Fibonacci từ F₁ đến Fₘ và kiểm tra số nào là ước của Fₘ. Đừng quên F₁ = F₂ = 1 nên hai vị trí này chỉ được tính là một giá trị phân biệt! |
| Tháng 11 12, 2026, 17:21 | Hint Subtask 1 - Problem A: Brute Force |
Với N và Q nhỏ, hãy sử dụng một mảng để lưu các phần tử và cập nhật trực tiếp khi có thay đổi. Đối với mỗi truy vấn, lấy các phần tử trong đoạn [L, R], sắp xếp theo thứ tự giảm dần và trả về phần tử tại vị trí K. Hãy chú ý những giá trị trùng nhau! |
Welcome to EIU Olympic Contest 2026
Xin chào tất cả các bạn! Tôi rất vui mừng và trân trọng sự hiện diện của các bạn tại cuộc thi ngày hôm nay. Đây chính là vòng thi cuối cùng trong hành trình tuyển chọn đội tuyển Olympic Tin học EIU, đồng thời cũng là thử thách quyết định để các bạn có cơ hội trở thành thành viên đại diện cho EIU tham dự Cuộc thi Lập trình Sinh viên Việt Nam 2026. Có thể nói, các bạn đang đứng trước chặng đường cuối cùng để chạm đến một cột mốc đáng nhớ trong hành trình chinh phục lập trình của mình.
Vòng thi lần này sẽ mang đến những bài toán đòi hỏi tư duy logic, khả năng phân tích và kỹ năng thiết kế giải thuật hợp lý. Vì vậy, hãy phát huy hết năng lực của bản thân, đọc kỹ đề bài, cân nhắc các giới hạn và lựa chọn hướng giải quyết phù hợp với từng subtest. Nếu gặp một bài toán quá khó, đừng ngần ngại chuyển sang bài khác để tối ưu hóa điểm số. Hãy nhớ rằng, chúng tôi đánh giá dựa trên kết quả cuối cùng, chứ không phải số lần các bạn kiên trì thử nghiệm trên một bài toán duy nhất. Vì thế, hãy phân bổ thời gian thật thông minh và đưa ra những quyết định sáng suốt nhé! Các bạn sẽ được nhận "Hint" của ~5~ subtest đầu của mỗi bài trong ~100~ phút đầu của kì thi, các bạn có thể dựa vào đó để thiết kế thuật toán hợp lý cho từng subtest của mỗi bài.
Lưu ý: Các bạn tuyệt đối không được mở bất kỳ tab trình duyệt hoặc ứng dụng nào khác (bao gồm Word, Excel,...) trong suốt thời gian thi. Hành động này có thể bị xem là gian lận và thí sinh vi phạm sẽ bị loại khỏi cuộc thi. Các bạn chỉ được phép sử dụng đường dẫn Contest và ứng dụng lập trình được cho phép để viết và nộp bài.
Và bây giờ, hãy cùng hướng đến phần thưởng đầy hấp dẫn đang chờ đợi phía trước! Chúc các bạn có một cuộc thi thật thú vị, đạt được số điểm ấn tượng để có cơ hội trở thành "những vị khách du lịch đặc biệt" tại thành phố biển xinh đẹp được mệnh danh là "Thành phố đáng sống nhất Việt Nam" – Đà Nẵng! Hãy tưởng tượng những khoảnh khắc đáng nhớ khi chúng ta cùng khám phá, vui chơi, gắn kết với các thành viên Olympic và tự hào khoác lên mình chiếc áo đồng phục xinh xắn, mang đậm dấu ấn của tri thức và nhiệt huyết tuổi trẻ.
Sau những giờ phút căng thẳng cùng những dòng code, chúng ta sẽ cùng nhau "bung xõa" và khám phá những địa danh tuyệt đẹp của thành phố này: check-in bên đôi bàn tay khổng lồ của Cầu Vàng giữa Bà Nà mờ sương, chiêm ngưỡng Cầu Rồng kiêu hãnh phun lửa bên dòng sông Hàn thơ mộng, hay thư giãn bên bãi biển Mỹ Khê quyến rũ. Tất cả hứa hẹn sẽ tạo nên một hành trình ngập tràn tiếng cười và những kỷ niệm khó quên. Các bạn có thể tham khảo lịch trình khám phá dự kiến tại đây.
Và đặc biệt hơn cả, đó là cảm giác đón nhận những cơn gió biển lộng từ đại dương, tận hưởng bầu không khí se se lạnh cùng làn sương mỏng nhẹ của mùa đông miền Trung. Một Đà Nẵng cuối năm vừa thơ mộng, dịu dàng, bình yên nhưng cũng đầy lãng mạn chắc chắn sẽ mang đến những trải nghiệm đáng nhớ, nơi chúng ta cùng lưu giữ những khoảnh khắc thanh xuân tươi đẹp.
Cuối cùng, chúc tất cả các bạn thật bình tĩnh, tự tin, bản lĩnh và đạt được kết quả tốt nhất! Hãy chiến đấu hết mình, chinh phục thử thách và biến cơ hội này thành một dấu ấn đáng tự hào trong hành trình của chính mình!
Chúc các bạn thành công và hẹn gặp lại tại Đà Nẵng!
A little love from a cute boy <3.
Lưu ý
- Các bạn hãy đọc toàn bộ vấn đề, sau đó chọn ra từng vấn đề dễ nhất để giải quyết, vì các vấn đề được xáo trộn độ khó để kiểm tra khả năng nhìn nhận vấn đề của các bạn.
- Nếu muốn đọc các câu chuyện thú vị thì các bạn có thể chuyển sang ngôn ngữ tiếng Việt (
) hoặc ngược lại với tiếng Anh (
).
- Để nộp các vấn đề các bạn nên sử dụng bộ đọc nhanh của từng ngôn ngữ, riêng Python hãy dùng trình chấm Pypy3 và
sys.stdin.readline().strip(). - Dưới đây là code kèm bộ đọc nhanh của ~2~ ngôn ngữ C++ và Java cho bài A plus B
C++
#include <bits/stdc++.h>
using namespace std;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// Your code
long long u, v;
cin >> u >> v;
cout << u + v << "\n";
return 0 ^ 0;
}
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
// Your code
long a = sc.nextLong();
long b = sc.nextLong();
System.out.println(a + b);
}
/*
* Don't see below
*/
static Reader sc = new Reader();
static StringBuilder sb = new StringBuilder();
static Random rd = new Random();
static class Reader {
private int BUFFER_SIZE = 1 << 16;
private byte[] buffer = new byte[BUFFER_SIZE];
private int bufferPointer = 0, bytesRead = 0;
private InputStream rd;
public Reader() {
this.rd = System.in;
}
private byte read() {
if (bufferPointer == bytesRead) {
bufferPointer = 0;
try {
bytesRead = rd.read(buffer, bufferPointer, BUFFER_SIZE);
} catch (IOException e) {
e.printStackTrace();
}
if (bytesRead == -1) {
return -1;
}
}
return buffer[bufferPointer++];
}
public boolean hasNext() {
int c = read();
while (c <= ' ' && c != -1) {
c = read();
}
if (c == -1) {
return false;
}
bufferPointer--;
return true;
}
public int nextInt() {
int number = 0;
int c = read();
while (c <= ' ') {
c = read();
}
boolean negative = (c == '-');
if (negative) {
c = read();
}
do {
number = number * 10 + (c - '0');
c = read();
} while (c >= '0' && c <= '9');
return negative ? -number : number;
}
public long nextLong() {
long number = 0L;
int c = read();
while (c <= ' ') {
c = read();
}
boolean negative = (c == '-');
if (negative) {
c = read();
}
do {
number = number * 10 + (c - '0');
c = read();
} while (c >= '0' && c <= '9');
return negative ? -number : number;
}
public String next() {
int c = read();
while (c <= ' ') {
c = read();
}
StringBuilder t = new StringBuilder();
do {
t.append((char) c);
c = read();
} while (c > ' ');
return t.toString();
}
public String nextLine() {
int c = read();
while (c == '\n' || c == '\r') {
c = read();
}
StringBuilder t = new StringBuilder();
while (c != '\n' && c != '\r' && c != -1) {
t.append((char) c);
c = read();
}
return t.toString();
}
public double nextDouble() {
return Double.parseDouble(next());
}
public char nextChar() {
int c = read();
while (c <= ' ') {
c = read();
}
return (char) c;
}
}
}
Bình luận