Statistics

Problem Statement for "MinDegreeSubgraph"

Problem Statement

All graphs in this problem are undirected simple graphs. (I.e., each pair of vertices is connected by at most one edge, and there are no loops.)

Let G=(V,E) be a graph. We call a graph H=(V',E') a subgraph of a graph G if the following conditions hold:

  • V' is a nonempty subset of V
  • E' is a subset of E
  • for each edge in E', both its endpoints are in V'
In other words, a subgraph can be constructed by first removing some vertices (possibly none, but not all of them) together with all their edges, and then removing some of the remaining edges (possibly none or all of them).

The mindegree of a graph is the minimum of the degrees of its vertices.

A graph is locally k-dense if it contains a subgraph with mindegree k.

You are given an int n, a long m, and an int k. Consider all graphs on n vertices with exactly m edges. Determine whether all, some, or none of these graphs are locally k-dense. Return "ALL", "SOME", or "NONE", respectively.

Definition

Class:
MinDegreeSubgraph
Method:
exists
Parameters:
int, long, int
Returns:
String
Method signature:
String exists(int n, long m, int k)
(be sure your method is public)

Notes

  • Given the constraints of the problem, there always exists at least one graph with n vertices and m edges.
  • Given a graph, the degree of a vertex is the number of edges incident with this vertex.
  • The return value "SOME" means that there exists a graph with the desired property and also a graph without the desired property.

Constraints

  • n will be between 1 and 109, inclusive.
  • m will be between 0 and n(n-1)/2, inclusive.
  • k will be between 0 and 109, inclusive.

Examples

  1. 3

    3

    2

    Returns: "ALL"

    Up to isomorphism, there is only one graph on 3 vertices and 3 edges: the triangle. It does have a subgraph with mindegree 2: itself. (Note that each graph is its own subgraph.)

  2. 4

    3

    2

    Returns: "SOME"

    Two of the graphs with 4 vertices and 3 edges are trees. Obviously, a tree cannot be locally 2-dense, because each subgraph of a tree is a forest, and each forest contains a vertex of degree at most 1. Another graph with 4 vertices and 3 edges is a graph that consists of a triangle and an isolated vertex. This graph is locally 2-dense because it contains a subgraph with mindegree 2: the triangle.

  3. 6

    10

    3

    Returns: "ALL"

    There are many graphs with 6 vertices and 10 edges. No matter which one of them we choose, it will always contain some subgraph with mindegree exactly 3.

  4. 6

    15

    4

    Returns: "ALL"

    There is only one such graph: the complete graph K6. It contains many mindegree-4 subgraphs. For instance, we can construct such a subgraph by removing any one vertex, and we can also construct a different mindegree-4 subgraph by removing any one edge.

  5. 17

    53

    11

    Returns: "NONE"

  6. 100

    1710

    20

    Returns: "SOME"

  7. 100

    1711

    20

    Returns: "ALL"

  8. 100

    1712

    20

    Returns: "ALL"

  9. 10000

    19997

    3

    Returns: "SOME"

  10. 10000

    5

    3

    Returns: "NONE"

  11. 10000

    19998

    3

    Returns: "ALL"

  12. 10000

    6

    3

    Returns: "SOME"

  13. 10000

    19999

    3

    Returns: "ALL"

  14. 10000

    7

    3

    Returns: "SOME"

  15. 123233232

    1521114822468

    12345

    Returns: "SOME"

  16. 123233232

    76205684

    12345

    Returns: "NONE"

  17. 123233232

    1521114822469

    12345

    Returns: "ALL"

  18. 123233232

    76205685

    12345

    Returns: "SOME"

  19. 123233232

    1521114822470

    12345

    Returns: "ALL"

  20. 123233232

    76205686

    12345

    Returns: "SOME"

  21. 18000

    53994

    4

    Returns: "SOME"

  22. 18000

    9

    4

    Returns: "NONE"

  23. 18000

    53995

    4

    Returns: "ALL"

  24. 18000

    10

    4

    Returns: "SOME"

  25. 18000

    53996

    4

    Returns: "ALL"

  26. 18000

    11

    4

    Returns: "SOME"

  27. 10

    9

    2

    Returns: "SOME"

  28. 10

    2

    2

    Returns: "NONE"

  29. 10

    10

    2

    Returns: "ALL"

  30. 10

    3

    2

    Returns: "SOME"

  31. 10

    11

    2

    Returns: "ALL"

  32. 10

    4

    2

    Returns: "SOME"

  33. 999

    0

    1

    Returns: "NONE"

  34. 999

    0

    1

    Returns: "NONE"

  35. 999

    1

    1

    Returns: "ALL"

  36. 999

    1

    1

    Returns: "ALL"

  37. 999

    2

    1

    Returns: "ALL"

  38. 999

    2

    1

    Returns: "ALL"

  39. 17

    0

    0

    Returns: "ALL"

  40. 17

    1

    0

    Returns: "ALL"

  41. 1000000000

    499999999499999999

    999999999

    Returns: "NONE"

  42. 1000000000

    499999999500000000

    999999999

    Returns: "ALL"

  43. 1000000000

    499999999500000000

    1000000000

    Returns: "NONE"

  44. 1000000000

    2999999994

    4

    Returns: "SOME"

  45. 1000000000

    9

    4

    Returns: "NONE"

  46. 1000000000

    2999999995

    4

    Returns: "ALL"

  47. 1000000000

    10

    4

    Returns: "SOME"

  48. 1000000000

    2999999996

    4

    Returns: "ALL"

  49. 1000000000

    11

    4

    Returns: "SOME"

  50. 56

    594

    100

    Returns: "NONE"

  51. 56

    595

    100

    Returns: "NONE"

  52. 56

    596

    100

    Returns: "NONE"

  53. 56

    1540

    100

    Returns: "NONE"

  54. 6

    0

    12

    Returns: "NONE"

  55. 6

    15

    12

    Returns: "NONE"

  56. 6

    1

    12

    Returns: "NONE"

  57. 6

    2

    12

    Returns: "NONE"

  58. 987654321

    114311840811614082

    123456789

    Returns: "SOME"

  59. 987654321

    7620789436823654

    123456789

    Returns: "NONE"

  60. 987654321

    114311840811614083

    123456789

    Returns: "ALL"

  61. 987654321

    7620789436823655

    123456789

    Returns: "SOME"

  62. 987654321

    114311840811614084

    123456789

    Returns: "ALL"

  63. 987654321

    7620789436823656

    123456789

    Returns: "SOME"

  64. 6

    9

    3

    Returns: "SOME"

  65. 8

    13

    3

    Returns: "SOME"

  66. 100

    2800

    50

    Returns: "SOME"

  67. 3

    1

    0

    Returns: "ALL"

  68. 2

    0

    1

    Returns: "NONE"

  69. 9

    14

    3

    Returns: "SOME"

  70. 3

    1

    1

    Returns: "ALL"

  71. 10

    44

    5

    Returns: "ALL"

  72. 5

    2

    2

    Returns: "NONE"

  73. 1000000000

    9998950005000

    10000

    Returns: "SOME"

  74. 7

    2

    1

    Returns: "ALL"

  75. 10

    10

    50

    Returns: "NONE"

  76. 3

    2

    2

    Returns: "NONE"

  77. 13

    33

    5

    Returns: "SOME"

  78. 3

    3

    3

    Returns: "NONE"

  79. 1000000000

    5000000000000000

    100000000

    Returns: "NONE"

  80. 5

    7

    3

    Returns: "SOME"

  81. 4

    1

    1

    Returns: "ALL"

  82. 8

    14

    3

    Returns: "ALL"

  83. 100

    5

    1

    Returns: "ALL"

  84. 100

    855

    10

    Returns: "SOME"

  85. 99999998

    1158359798841643

    12345678

    Returns: "SOME"

  86. 15

    20

    0

    Returns: "ALL"

  87. 17

    115

    11

    Returns: "SOME"

  88. 1000000000

    250000000000000000

    500000000

    Returns: "SOME"

  89. 10

    11

    5

    Returns: "NONE"

  90. 1000000000

    94999999050000000

    100000000

    Returns: "SOME"

  91. 1000000000

    499999999499999096

    999999958

    Returns: "SOME"

  92. 100

    3000

    50

    Returns: "SOME"

  93. 20

    101

    10

    Returns: "SOME"

  94. 1000

    250000

    498

    Returns: "SOME"

  95. 1000

    250000

    480

    Returns: "SOME"

  96. 1000000000

    1000000000

    999999999

    Returns: "NONE"

  97. 100

    0

    1

    Returns: "NONE"

  98. 10

    24

    4

    Returns: "SOME"

  99. 100

    856

    10

    Returns: "ALL"

  100. 18

    12

    5

    Returns: "NONE"

  101. 15

    41

    9

    Returns: "NONE"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: