Bài tập Chiến lược thi

Bài 1Điểm chuẩn hóa

Mỗi bài trong một kỳ thi đo bằng một thước đo riêng: bài này F1 (càng cao càng tốt), bài kia RMSE (càng thấp càng tốt). Để so hay cộng điểm giữa các bài, kỳ thi USA-NA-AIO quy mọi kết quả về một thang chung bằng điểm của baseline và điểm của bài làm tốt nhất.

Với mỗi bài, gọi $X$ là kết quả của em, $X_b$ của baseline, $X^*$ của bài làm tốt nhất:

Thước đo càng cao càng tốt: $r=\dfrac{X-X_b}{X^*-X_b}$ .
Thước đo càng thấp càng tốt: $r=\dfrac{X_b-X}{X_b-X^*}$ .
Kém hơn baseline thì $r=0$ (không có điểm âm).

Điểm của bài là $r$ nhân số điểm tối đa của bài. Báo $r$ , điểm từng bài và tổng điểm.

Dữ liệu vào

Một đối tượng JSON gồm problems: mỗi bài là {"score", "baseline", "best", "higher_is_better", "points"}.

Kết quả

Một đối tượng JSON gồm problems (mỗi bài là {"ratio", "points"}) và total.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "problems": [
    {
      "score": 0.82,
      "baseline": 0.0,
      "best": 0.91,
      "higher_is_better": true,
      "points": 40
    },
    {
      "score": 1.9,
      "baseline": 2.5,
      "best": 1.2,
      "higher_is_better": false,
      "points": 50
    },
    {
      "score": 2.8,
      "baseline": 2.5,
      "best": 1.2,
      "higher_is_better": false,
      "points": 50
    },
    {
      "score": 0.91,
      "baseline": 0.0,
      "best": 0.91,
      "higher_is_better": true,
      "points": 40
    }
  ]
}

Output mẫu

{
  "problems": [
    {"ratio": 0.9010989010989011, "points": 36.043956043956044},
    {"ratio": 0.46153846153846156, "points": 23.076923076923077},
    {"ratio": 0.0, "points": 0.0},
    {"ratio": 1.0, "points": 40.0}
  ],
  "total": 99.12087912087912
}

Bài 2Bài nộp còn hiệu lực

Đề bài Dữ liệu

Trong kỳ thi, bài được chấm là bài nộp hợp lệ gần nhất. Một bài nộp hỏng định dạng không xóa được bài hợp lệ trước đó, nhưng cũng không tính điểm. Bài này cho biết: nếu kỳ thi dừng ở từng thời điểm, em được bao nhiêu điểm?

Mỗi lần nộp có id, time (phút), valid và private (điểm private, chỉ biết sau kỳ thi). Danh sách không theo thứ tự thời gian, và không có hai lần nộp cùng phút.

Với mỗi thời điểm $t$ trong checkpoints: bài được chấm là bài hợp lệ có time $\le t$ lớn nhất; báo id và điểm của nó, hoặc null và $0$ nếu chưa có bài hợp lệ nào. Báo thêm điểm private cao nhất trong mọi bài hợp lệ.

Dữ liệu vào

Một đối tượng JSON gồm submissions và checkpoints.

Kết quả

Một đối tượng JSON gồm final (với mỗi thời điểm là {"time", "id", "score"}) và best_private_ever.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "submissions": [
    {"id": "baseline", "time": 20, "valid": true, "private": 0.61},
    {"id": "cnn-v1", "time": 95, "valid": true, "private": 0.78},
    {"id": "cnn-v2", "time": 160, "valid": false, "private": 0.84},
    {"id": "ensemble", "time": 175, "valid": true, "private": 0.8}
  ],
  "checkpoints": [10, 60, 170, 180]
}

Output mẫu

{
  "final": [
    {"time": 10, "id": null, "score": 0.0},
    {"time": 60, "id": "baseline", "score": 0.61},
    {"time": 170, "id": "cnn-v1", "score": 0.78},
    {"time": 180, "id": "ensemble", "score": 0.8}
  ],
  "best_private_ever": 0.8
}

Bài 3Public và private

Đề bài Dữ liệu

Bảng xếp hạng public chỉ chấm trên một phần nhỏ của test. Điểm public vì thế là một phép đo có nhiễu: bài cao nhất trên public chưa chắc cao nhất trên phần còn lại (private).

Có nhãn thật labels, tập chỉ số public public_indices (phần còn lại là private) và dự đoán của vài bài nộp.

Với mỗi bài: độ chính xác trên public, trên private, và sai số chuẩn của độ chính xác public $\sqrt{p(1-p)/n}$ , với $p$ là độ chính xác public và $n$ là số mẫu public.
Xếp hạng các bài theo public và theo private (cao trước; bằng nhau thì tên nhỏ hơn).

Dữ liệu vào

Một đối tượng JSON gồm labels, public_indices và predictions (từ tên bài tới danh sách dự đoán).

Kết quả

Một đối tượng JSON gồm submissions (mỗi bài là {"name", "public", "private", "public_se"}, theo thứ tự trong predictions), public_ranking và private_ranking.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "labels": [
    1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1,
    1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1,
    1, 1, 1, 1, 0, 1, 0, 0, 1, 1
  ],
  "public_indices": [2, 23, 32, 44, 49],
  "predictions": {
    "tuned": [
      1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0,
      1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1,
      1, 1, 0, 1, 0, 1, 1, 0, 0, 1
    ],
    "ensemble": [
      1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
      1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1,
      1, 1, 0, 1, 1, 1, 0, 0, 1, 1
    ],
    "cnn_seed2": [
      1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1,
      1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1,
      0, 1, 1, 1, 0, 0, 0, 0, 1, 1
    ]
  }
}

Output mẫu

{
  "submissions": [
    {
      "name": "tuned",
      "public": 0.8,
      "private": 0.8775510204081632,
      "public_se": 0.17888543819998315
    },
    {
      "name": "ensemble",
      "public": 1.0,
      "private": 0.6938775510204082,
      "public_se": 0.0
    },
    {
      "name": "cnn_seed2",
      "public": 0.6,
      "private": 0.7551020408163265,
      "public_se": 0.21908902300206645
    }
  ],
  "public_ranking": ["ensemble", "tuned", "cnn_seed2"],
  "private_ranking": ["tuned", "cnn_seed2", "ensemble"]
}

Bài 4Chia thời gian

Đề bài Dữ liệu

Còn minutes phút cho vài bài. Mỗi bài có một chuỗi bước phải làm theo thứ tự (ví dụ: dựng pipeline, rồi huấn luyện, rồi tinh chỉnh); làm xong bước thứ $k$ thì kết quả của bài đạt metric của bước ấy. Điểm của một bài tính theo công thức chuẩn hóa của USA-NA-AIO:

càng cao càng tốt: $r=\max\!\big(0,\frac{X-X_b}{X^*-X_b}\big)$ ; càng thấp càng tốt: $r=\max\!\big(0,\frac{X_b-X}{X_b-X^*}\big)$ ;
điểm bài $=r\cdot$ points; chưa làm bước nào thì $0$ điểm.

Một kế hoạch chọn cho mỗi bài số bước $k_i$ làm được (luôn là các bước đầu), với tổng thời gian không quá minutes.

Kế hoạch tối ưu: tổng điểm lớn nhất; bằng nhau thì ít phút hơn; vẫn bằng nhau thì vector $(k_1,k_2,\dots)$ nhỏ hơn theo thứ tự từ điển.
Kế hoạch tham lam: bắt đầu từ $k_i=0$ ; mỗi lượt, xét các bài còn bước tiếp theo và còn đủ thời gian cho bước ấy, chọn bước có (điểm tăng thêm)/(số phút) lớn nhất (bằng nhau thì bài đứng trước); dừng khi không còn bước nào hoặc mức tăng lớn nhất không dương.

Báo số bước, tổng điểm và số phút của cả hai kế hoạch.

Dữ liệu vào

Một đối tượng JSON gồm minutes và problems: mỗi bài là {"name", "points", "higher_is_better", "baseline", "best", "steps"}, mỗi bước là {"minutes", "metric"}.

Kết quả

Một đối tượng JSON gồm optimal và greedy, mỗi cái là {"steps", "points", "minutes"}.

Giới hạn

Không quá $3$ bài, mỗi bài không quá $3$ bước.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "minutes": 120,
  "problems": [
    {
      "name": "text",
      "points": 40,
      "higher_is_better": true,
      "baseline": 0.5,
      "best": 0.9,
      "steps": [
        {"minutes": 30, "metric": 0.7},
        {"minutes": 40, "metric": 0.8},
        {"minutes": 40, "metric": 0.85}
      ]
    },
    {
      "name": "image",
      "points": 50,
      "higher_is_better": true,
      "baseline": 0.4,
      "best": 0.95,
      "steps": [{"minutes": 50, "metric": 0.45}, {"minutes": 40, "metric": 0.9}]
    },
    {
      "name": "search",
      "points": 30,
      "higher_is_better": false,
      "baseline": 20.0,
      "best": 5.0,
      "steps": [{"minutes": 20, "metric": 12.0}, {"minutes": 30, "metric": 8.0}]
    }
  ]
}

Output mẫu

{
  "optimal": {"steps": [1, 2, 0], "points": 65.45454545454545, "minutes": 120},
  "greedy": {"steps": [2, 0, 2], "points": 54.0, "minutes": 120}
}

Bài 5Lợi ích và rủi ro

Đề bài Dữ liệu

Kế hoạch trên giấy giả sử mọi bước đều thành công. Thực tế, một bước có thể hỏng (mô hình không hội tụ, hết thời gian, lỗi định dạng), và khi một bước hỏng thì các bước sau của cùng việc ấy cũng không làm được. Bài này so vài kế hoạch theo điểm kỳ vọng và theo rủi ro không có bài nộp hợp lệ nào.

Mỗi kế hoạch gồm vài việc độc lập; mỗi việc là chuỗi bước, bước có success (xác suất thành công) và gain (điểm được thêm nếu thành công). Bước $j$ của một việc chỉ được làm khi mọi bước trước của việc ấy đã thành công; các bước thành công hay hỏng độc lập với nhau.

Điểm kỳ vọng của một việc $=\sum_j\big(\prod_{i\le j}\text{success}_i\big)\cdot\text{gain}_j$ ; của kế hoạch là tổng các việc.
Kế hoạch có bài nộp hợp lệ khi bước đầu của ít nhất một việc thành công. Xác suất không có bài hợp lệ là $\prod_{\text{việc}}(1-\text{success}_{\text{bước đầu}})$ .
Báo kế hoạch có điểm kỳ vọng cao nhất, và kế hoạch được chọn: điểm kỳ vọng cao nhất trong các kế hoạch có xác suất không hợp lệ không vượt max_risk (null nếu không có). Bằng điểm thì tên nhỏ hơn.

Dữ liệu vào

Một đối tượng JSON gồm max_risk và plans (mỗi kế hoạch là {"name", "tasks"}, mỗi việc là {"steps"}).

Kết quả

Một đối tượng JSON gồm plans (mỗi kế hoạch là {"name", "expected_points", "p_no_valid"}), best_expected và chosen.

Giới hạn

Không quá $4$ kế hoạch, mỗi kế hoạch không quá $8$ bước. Không xác suất nào sát đúng max_risk.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "max_risk": 0.1,
  "plans": [
    {
      "name": "safe",
      "tasks": [
        {
          "steps": [{"success": 0.95, "gain": 20}, {"success": 0.8, "gain": 10}]
        },
        {"steps": [{"success": 0.9, "gain": 15}]}
      ]
    },
    {
      "name": "bold",
      "tasks": [
        {
          "steps": [{"success": 0.6, "gain": 60}, {"success": 0.7, "gain": 40}]
        }
      ]
    },
    {
      "name": "one_more_seed",
      "tasks": [
        {
          "steps": [
            {"success": 0.95, "gain": 20},
            {"success": 0.8, "gain": 10},
            {"success": 0.5, "gain": 3}
          ]
        }
      ]
    }
  ]
}

Output mẫu

{
  "plans": [
    {"name": "safe", "expected_points": 40.1, "p_no_valid": 0.005},
    {"name": "bold", "expected_points": 52.8, "p_no_valid": 0.4},
    {
      "name": "one_more_seed",
      "expected_points": 27.74,
      "p_no_valid": 0.05
    }
  ],
  "best_expected": "bold",
  "chosen": "safe"
}