Hardstone and Erdos-Gallai

Revision en3, by dfsof, 2023-10-16 06:44:44

Orz.hardstone gives me four problems. However, I am so dumb that can only solve the easist one:

First, we define $$$A$$$ as a non-negative integer array $$$A:=\{a_i\}$$$. We call $$$A$$$ is valid if $$$A$$$ is a [degree sequence](https://en.wikipedia.org/wiki/Degree_(graph_theory)) of a simple undirected graph.

P1: Give $$$A$$$, decide whether $$$A$$$ is valid. (Solved using Erdos-Gallai, $$$O(n)$$$);

P2: Give $$$A$$$ and $$$q$$$ independent queries $$$(l, r)$$$, decide whether $$$A[l...r]$$$ is valid.

P3: Give $$$A$$$, count how many continuous subarrays of $$$A$$$ are valid.

P4: Solve $$$P2$$$ if modification on $$$A$$$ is allowed.

Tags data structures, graph, hardstone

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English dfsof 2023-10-16 06:46:43 1 Tiny change: 'e the easist one:\n\' -> 'e the easiest one:\n\'
en4 English dfsof 2023-10-16 06:44:59 0 (published)
en3 English dfsof 2023-10-16 06:44:44 0 (saved to drafts)
en2 English dfsof 2023-10-16 06:44:00 16 Tiny change: 'ph_theory)#Degree_sequence) of a sim' -> 'ph_theory)) of a sim'
en1 English dfsof 2023-10-16 06:43:17 727 Initial revision (published)