477 Challenge

Background

https://validator.w3.org/ : 是一个由万维网联盟（W3C）提供的在线工具，用于检查网页的 HTML、XHTML 或其他标记语言是否符合相关标准和规范。它可以帮助开发者提高网页的质量和兼容性，确保网页在不同浏览器和设备上正确显示。

作为实习生你需要完成网站开发，要求如下(不重要)

During the next few hours you are explained in details all the requirements you have to match. Among
the most emphasized points you learn that you must (i) use the last version of Microsoft Front Page
Express to write the websites; (ii) include as many buttons as possible (even if one is enough); (iii) when a
hidden box is expanded, do so as high as possible above the button which opened it and do not notify the
user; (iv) as much as possible do not disable or hide irrelevant information, simply include it the middle
of the useful content; (v) use and abuse pop ups; (vi) feel free to include Chinese text in the middle of
an English text; (vii) if a page includes videos, ensure they are all fully downloaded before the user can
do anything; You also learn that they pay much attention to the quality of their product, and as such
you should never forget to test your website, IE 6 being recommended.
在接下来的几个小时里，我们会详细解释您需要满足的所有要求。其中最受关注的要点是：您必须 (i) 使用最新版本的 Microsoft Front Page Express 来编写网站；(ii) 包含尽可能多的按钮（即使一个按钮就足够了）；(iii) 展开隐藏框时，尽可能将其展开到打开它的按钮上方，并且不要通知用户；(iv) 尽可能不要禁用或隐藏不相关的信息，只需将其包含在有用内容的中间；(v) 使用和滥用弹出窗口；(vi) 可以在英文文本中间随意添加中文文本；(vii) 如果页面包含视频，请确保在用户执行任何操作之前，它们都已完全下载；您还了解到他们非常重视产品质量，因此您永远不要忘记测试您的网站，建议使用 IE 6.

大概是马牛特有的讽刺。。。总之就是总结了一堆网站开发的禁止事项。
因为这些要求的存在（特别是网页开发环境只能在windows下使用），我们作为一位只有一台双系统电脑的实习生遇到了障碍：

每次开发网页我们都需要切换到windows系统并暂停linux系统下的任务。然而在linux下我们需要跑一些任务，需要尽可能早去完成。

针对这些linux任务，马牛貌似将其分成了T个独立的任务，根据output推测，每个任务也可以被暂停，然后切换到windows进行开发。

可以通过把任务转交给朋友的方式来从schedule中移除部分网页开发的任务，至多两个网页。每个网页有对应的用于交易的作业量，作业量加起来不能超过HC的触发阈值。

标识

需要注意的是，计算任务需要的时间 $t_i$ 和网页完成的deadline $t_i$ 不是一个东西，建议区分标记。

输入

计算任务，网页开发以及外援的信息

P H
s_0 t_0 h_0 # info for each page
... # omit P-1 lines
T # number of tasks
t_0
... # omit T-1 lines

### 输出 我们并不需要在规划中完成所有的计算任务。针对每个计算任务，计算其**最早能完成的时间点**即可。针对不同时长的计算任务，**使用的分配策略可能不同**。

以下纯来自AI的solution

To solve this problem, you need to combine optimization, scheduling, and greedy strategies. Here’s a step-by-step guide:

---

1. Parse the Input

• Read:
  • P,H: Number of webpages and maximum allowable exercises for delegation.
  • Details for each webpage (s_i, t_i, h_i): Start time, deadline, and exercise cost.
  • T: Number of computational tasks and their durations (t_i).

---

2. Determine Delegation Strategy

Key Idea:

• Delegate up to 2 webpages to the friend such that the total exercise cost (h_i) is minimized and ≤H.

Steps:

1. Sort webpages by their exercise cost (h_i).
2. Select up to 2 webpages to delegate:
   • Choose pages with the smallest h_i that satisfy h_1+h_2≤H.
3. Remove these pages from your schedule, as they are handled by the friend.

---

3. Calculate Free Time Intervals

Key Idea:

• After delegating pages, compute the blocked time intervals caused by the remaining webpages.

Steps:

1. For all non-delegated webpages, construct intervals [s_i, t_i).
2. Merge overlapping intervals to avoid double-counting blocked time.
3. Identify the free intervals:
   • Initially, it is [0,∞).
   • Subtract merged blocked intervals to get the free time slots.

---

4. Schedule Computational Tasks

Key Idea:

• Fit each computational task into the free intervals to minimize its completion time.

Steps:

1. Sort computational tasks by their required time (t_i).
2. Iterate over each task:
   • Start placing the task in the earliest available free interval.
   • If the task fits, calculate its completion time and reduce the interval size.
   • If it doesn’t fit, move to the next free interval.
3. Store the completion time for each task.

---

5. Output Results

For each computational task, output the minimum completion time determined in the previous step.

---

Algorithm Complexity

1. Input Parsing: O(P+T)
2. Delegation:
   • Sorting webpages: O(P \log P)
   • Selecting 2 webpages: O(1)
3. Free Interval Calculation:
   • Merging intervals: O(P \log P)
4. Task Scheduling:
   • Sorting tasks: O(T \log T)
   • Scheduling: O(T×free intervals), typically O(T + P).

Overall complexity: O((P + T) \log (P + T)).
this complexity is acceptable regarding the given input range.

---

OCaml Implementation

Here’s a high-level pseudocode that can be adapted into OCaml:

(* Input Parsing *)
let read_input () =
  let p, h = read_line () in
  let webpages = List.init p (fun _ -> read_line ()) in
  let t = read_int () in
  let tasks = List.init t (fun _ -> read_int ()) in
  (p, h, webpages, tasks)

(* Delegate webpages *)
let delegate_webpages webpages h =
  let sorted_pages = List.sort (fun (_, _, h1) (_, _, h2) -> compare h1 h2) webpages in
  let rec select_delegation remaining_pages acc h_left =
    match remaining_pages with
    | [] -> acc, remaining_pages
    | (s, t, h)::tl when h <= h_left -> select_delegation tl ((s, t, h)::acc) (h_left - h)
    | _ -> acc, remaining_pages
  in
  select_delegation sorted_pages [] h

(* Compute free intervals *)
let compute_free_intervals remaining_pages =
  let intervals = List.map (fun (s, t, _) -> (s, t)) remaining_pages in
  let merged_intervals = merge_intervals intervals in
  calculate_free_time_slots merged_intervals

(* Schedule tasks *)
let schedule_tasks free_intervals tasks =
  List.map (fun task ->
    find_earliest_completion free_intervals task
  ) tasks

(* Main function *)
let () =
  let p, h, webpages, tasks = read_input () in
  let delegated_pages, remaining_pages = delegate_webpages webpages h in
  let free_intervals = compute_free_intervals remaining_pages in
  let task_completions = schedule_tasks free_intervals tasks in
  List.iter print_int task_completions

以下纯来自AI的proof

Proof of Correctness for the Algorithm

The algorithm is designed to solve the problem of scheduling computational tasks on a single computer while meeting constraints related to webpage deadlines and delegation. Below is a formal proof of its correctness.

---

1. Problem Understanding

The problem involves:

1. Allocating time for webpage writing (either by handling them yourself or delegating to a friend).
2. Maximizing free intervals for computational tasks.
3. Minimizing the completion times of computational tasks.

To ensure correctness, we need to prove:

• Webpage constraints are respected.
• Free time intervals are accurately calculated.
• Computational tasks are scheduled optimally.

---

2. Proof Components

2.1 Webpage Delegation

• Key Idea: Delegate up to 2 webpages with the smallest exercise costs such that the total cost does not exceed H.
• Proof:
  • By sorting webpages by h_i (exercise cost) and selecting the top 2 that satisfy h1+h2≤H, the algorithm guarantees that:
    • The delegation respects the maximum exercise limit H.
    • The webpages with the least impact on constraints are delegated, maximizing the remaining free time.

---

2.2 Free Interval Calculation

• Key Idea: Compute free intervals by merging blocked intervals caused by non-delegated webpages.
• Proof:
  • Non-delegated webpages define intervals [s_i, t_i) that block the computer.
  • Merging overlapping intervals ensures no double-counting of blocked time, leaving only valid free intervals.
  • The algorithm iteratively merges intervals by sorting them by s_i and combining overlapping or adjacent intervals, which is a standard and proven approach.

---

2.3 Task Scheduling

• Key Idea: Fit each computational task into the earliest available free interval to minimize its completion time.
• Proof:
  • Tasks are processed in increasing order of required time (t_i), ensuring that smaller tasks are scheduled earlier, leaving larger free intervals for longer tasks.
  • For each task:
    • The algorithm scans free intervals and places the task in the earliest slot where it fits.
    • This greedy approach guarantees the earliest possible completion time for each task because:
      • Free intervals are disjoint and sorted.
      • A task placed in an earlier slot cannot complete earlier in any other configuration without violating disjointness.

---

2.4 Overall Algorithm

• Correctness Statement: The algorithm produces the earliest possible completion times for all tasks while satisfying webpage constraints and delegation limits.
• Proof:
  • Webpages: Constraints are respected by delegating up to 2 pages within H exercises and blocking the necessary intervals for non-delegated pages.
  • Free Intervals: Accurate calculation ensures no overlap or error in available time slots.
  • Task Scheduling: Greedy placement in the earliest available interval ensures optimal completion times.

---

4. Edge Cases

• P=0,T=0: No webpages or tasks, trivial solution.
• H=0: No delegation possible, all webpages must be handled by the user.
• Overlapping webpage intervals: Correctly merged to avoid double-counting.
• Tasks larger than any free interval: Scheduled in the earliest free interval where they fit.

---

5. Conclusion

The algorithm is correct as it:

1. Adheres to all constraints (webpage deadlines, delegation limits, task requirements).
2. Ensures optimal scheduling of computational tasks.
3. Handles edge cases gracefully.

Would you like a detailed explanation for a specific part of this proof or assistance implementing it?