E. Рудольф и квазирегулярный граф

Codeforces

IDCF10132E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Для своих научных изысканий Рудольф часто штудирует книги по теории графов и находит в них интересные определения: например, недавно он узнал, что неориентированный граф, у которого все вершины имеют равное количество рёбер-соседей, называют регулярным. Иногда Рудольф вводит собственные термины, если имеющиеся ему чем-то не угодили. Например, ему не понравилось, что понятие регулярности характерно только для неориентированных графов. Кроме того, ограничение, согласно которому из каждой вершины исходит строго одинаковое количество рёбер, показалось ему слишком скучным. Поэтому Рудольф придумал определение квазирегулярного графа. Ориентированный граф является квазирегулярным, если он обладает следующими свойствами: Рудольф остался очень доволен своим новым определением и тут же начал рисовать различные квазирегулярные графы. Спустя некоторое время он обратил внимание на то, что некоторые из нарисованных им графов содержали циклы, тогда как другие — нет. Из книг Рудольф знал, что ациклические графы — это очень здорово, поэтому он принялся подробнее изучать (и рисовать) именно ациклические квазирегулярные графы. Сейчас Рудольф нарисовал на бумаге n точек-вершин. Ему интересно, какое максимальное количество стрелок-рёбер он может дорисовать, чтобы получившийся граф был квазирегулярным и не содержал циклов. Помогите ему найти ответ на этот вопрос. Ввод содержит целое число n (1 ≤ n ≤ 109) — количество вершин графа. Выведите одно целое число — максимальное количество рёбер ациклического квазирегулярного графа, содержащего n вершин. Искомый ациклический квазирегулярный граф для первого примера показан на рисунке. ## Входные Данные Ввод содержит целое число n (1 ≤ n ≤ 109) — количество вершин графа. ## Выходные Данные Выведите одно целое число — максимальное количество рёбер ациклического квазирегулярного графа, содержащего n вершин. ## Примеры Входные данные3Выходные данные2Входные данные6Выходные данные12 ## Примечание Искомый ациклический квазирегулярный граф для первого примера показан на рисунке. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of vertices, with $ 1 \leq n \leq 10^9 $. A *quasiregular directed graph* is a directed graph where for every vertex, the out-degree is either $ d $ or $ d+1 $ for some fixed $ d \in \mathbb{Z}_{\geq 0} $, and all in-degrees are equal to some fixed $ k \in \mathbb{Z}_{\geq 0} $. **Constraints** 1. The graph is acyclic (no directed cycles). 2. Each vertex has out-degree $ d $ or $ d+1 $ for some integer $ d \geq 0 $. 3. All vertices have the same in-degree $ k $. **Objective** Maximize the total number of edges in such a graph with $ n $ vertices. **Solution** In an acyclic directed graph, vertices can be topologically ordered. To maximize edges under quasiregularity and acyclicity: - All in-degrees must be equal: $ k $. - Out-degrees differ by at most 1. - Maximum edges occur when the graph is a complete DAG with balanced out-degrees. The maximum number of edges in an acyclic directed graph on $ n $ vertices is achieved when the out-degrees are as balanced as possible and in-degrees are uniform. This is achieved by assigning out-degrees: - $ r $ vertices have out-degree $ \left\lfloor \frac{n-1}{2} \right\rfloor + 1 $, - $ n - r $ vertices have out-degree $ \left\lfloor \frac{n-1}{2} \right\rfloor $, but due to the constraint that *in-degrees are all equal*, and the graph is acyclic, the only way to satisfy both is to have a **complete bipartite DAG** with partitions as equal as possible. Let $ a = \left\lceil \frac{n}{2} \right\rceil $, $ b = \left\lfloor \frac{n}{2} \right\rfloor $. Then maximum edges = $ a \cdot b $. Thus: $$ \boxed{\left\lfloor \frac{n^2}{4} \right\rfloor} $$

API Response (JSON)

{
  "problem": {
    "name": "E. Рудольф и квазирегулярный граф",
    "description": {
      "content": "Для своих научных изысканий Рудольф часто штудирует книги по теории графов и находит в них интересные определения: например, недавно он узнал, что неориентированный граф, у которого все вершины имеют ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10132E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Для своих научных изысканий Рудольф часто штудирует книги по теории графов и находит в них интересные определения: например, недавно он узнал, что неориентированный граф, у которого все вершины имеют ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices, with $ 1 \\leq n \\leq 10^9 $.  \nA *quasiregular directed graph* is a directed graph where for every vertex, the out-degree is eithe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments