Test for the Clique Problem
In this task, you are given a solution for the problem Cliques.
This solution does not achieve an Accepted status, but it operates with a time complexity of O(2^N).
"'cpp // i - current vertex, p - current set of vertices long long go(int i, long long p) if (p == 0) // if the set p is empty return 1; counter++; // program execution time while (((p » i) 1) == 0) // whether vertex i is in set p i++; p ^= 1LL « i; // exclude vertex i from set p if ((p c[i]) == p) // c[i] - set of vertices connected with vertex i by an edge return 2 * go(i, p); // p c[i] - intersection of sets p and c[i] return go(i, p) + go(i, p c[i]); counter = 0; // reset program execution time result = go(0, (1LL « n) - 1); // start from the set of all vertices "'
Your task is to create a test where this solution will not complete within the Time Limit. The runtime of the program is determined by the value of the variable counter.
Input
The number N — the number of vertices in the graph you need to construct.
There are a total of 2 tests in this task.
The first test has N = 20. In this test, the variable counter at the end of the program should be at least 5000.
The second test has N = 40. In this test, the variable counter at the end of the program should be at least 50000000.
Output
Output the test. The test should conform to the input data format of the problem Cliques.