TSECJC05 - Editorial

Problem Link:

Practice

Contest

Author: tseccodecell

DIFFICULTY:

Medium

PRE-REQUISITES:

Basic Combinatorics, Lucas Theorem

PROBLEM:

Find the number of graphs possible N vertices and M edges.

All vertices and edges must be used for a graph and at least one graph will be possible for every input.

QUICK EXPLANATION:

The answer for each input is given by :- {^{^nC_2}C_m} % 2713
this can be easily computed using lucas theorem, preprocess some values for faster computation

Explanation:

The number of different simple undirected graphs with n vertices and m edges is {^{^nC_2}C_m}.

Let us prove this:

No. of ways to choose any two vertices : {^nC_2} as it is undirected so arrangement dosen’t matter

This can be thought of as having {^nC_2} edges to choose from

Now, we have to choose ‘m’ edges from {^nC_2} possible edges, which is given by {^{^nC_2}C_m}

Alternative proof:

Let us consider the adjacency matrix of the graph

Total cells = n^2

As the graph is simple, there are no self loops, so we eliminate the diagonal cells.

So, now we’re left with n^2 - n cells

Since the graph is undirected, mat[i][j] = mat[j][i], so we’ll only have to choose from one half(bottom or top) as other half cell will be automatically filled

Therefore, cells to fill = (n^2 - n)/2

Since we have ‘m’ edges, we have to fill ‘m’ cells among these cells

So ways to fill it is ^{(n^2 - n)/2}C_m

Okay, so now we know that we have to find {^{^nC_2}C_m} % 2713,

but if we go about finding {^{^nC_2}C_m} directly and then do modulus, it will take too much time(time complexity will be huge) for the given constraints. see here for more information on such topics

If we analyze the modulus value, we come to know that it is a prime and a small one
So the best way to find our answer is to use Lucas Theorem(Link 1 , Link 2)

Basically you need to convert the numbers in base 2713 and then multiply the successive combinations

If we preprocess the combinations, time complexity for each test case would be: O(log_pn)

Pitfalls:
The assumption that {^{^nC_2}C_m} \bmod 2713 can be written as ^{(nC2 \bmod 2713)} C_{(m \bmod 2713)} \bmod 2713 is incorrect especially for large values

Some test cases with answers:

Input:

13
1000000000 11543263
1000000000 153126357391543263
37889434 334278564736253
99335555 417333344
1837 741
8242 2914
24191 19337
9219 3957
10 44
16347 5200
8385 8335
21132 7180
156600 1378774

Output:

0
0
471
0
2340
1838
874
2605
45
0
1808
0
1735

Time Complexity: O(p^2 + log_pn)

Space Complexity: O(p^2)

SOLUTION:

Author’s Solution

Tester’s Solution


If any one need to practice more upon lucas theorem,then this can be helpful, though it has some weak test cases,but question was a nice one.

I am not able to solve this problem TSECJC04 - Water Filling in Containers.
Problem link- https://www.codechef.com/problems/TSECJC04
What is the purpose of using Binary search to find the value of K?
I request you to give editorial of this question or help me in understanding it.

I am really thankful to you.

Editorials for all contest problems were posted yesterday, but not linked to contest problems.
You can find them all here : https://discuss.codechef.com/tags/tjcn2019/

//