PROBLEM LINK:
Setter- Denis Anishchenko
Tester- Hasan Jaddouh
Editorialist- Click here to find out.
DIFFICULTY:
MEDIUM
(This problem is MEDIUM w.r.t. thinking and wit required, while implementation is EASY and simple)
PRE-REQUISITES:
Graph Theory, DFS. Knowledge of mathematics in Graph theory will help you understand the editorial to its fullest 
PROBLEM:
You are given 2 problems out of which you have to solve only one of them. The problems are-
- Partition the graph into set of 2 vertices, such that number of edges from one set to another is < K
- Find a cycle of length at least K
- If both of above are unsolvable, print “NO ANSWER”
QUICK EXPLANATION:
Key to Success- The interrelation between the 2 problems was the factor which drew line between AC and “giving up”/WA.
At first glance, it looks a very complicated problem where we might have to “work for” both the problems if one of them has no answer. However, on analyzing the first problem of “CUT” in a little more detail, we see that it says about size of cut, but has no constraints on size of sets! (Hint: What if we put only 1 node in set A?). Hence, we do a check to find a node with degree < K. We put this node in set A and all other nodes in set B, solving the first problem.
For second problem, we require a little more coding - we need to do a DFS. Note that, if we cannot solve first problem, we know for sure that each node has degree \ge K. Hence, we keep traversing until we find a node with all of its neighbors visited. Now, on finding such a node, we “close” the cycle by putting an edge between that node and the neighbor which was visited the earliest to get the longest possible cycle which visits at least that node, and all of its neighbors. Since number of neighbors is \ge K, the cycle is at least of length K.
EXPLANATION:
I think a lot of fun part is over since you guys read the Quick Explanation Section 
. Nevertheless, lets have as much fun as we can :). I know many of you would be having questions like “How? How to prove that? Why is it correct?” (especially for second problem), and all of those will be answered here.
This editorial is divided into 3 parts. The first part deals with solving problem of CUT, the second part deals with solving the CYCLE problem. The third part is a general conclusion, compilation and inference of our assumptions which arent done in other two parts.
Please note, that the way I will explain the solution, is more related to the given problem (i.e. when we have to solve either CUT or CYCLE) than when we have to solve both the problems individually. Also, the answer to hand exercises, i.e. all the “(Why?)” is in Chef Vijju’s Corner.
1. Problem CUT-
(Refer to the Quick explanation if you havent.)
We open up a problem statement, with a fancy name resembling “Solve whatever you want” and are quite happy that FINALLY we have a choice in solving problems. And the very next thing done by setter is to dump 2 NP hard problems on our face. To top it off, he says that “If one of the problem has no solution, solve the other.”. Not really a “Solve whatever you want,” eh? XD
But as it turns out, solving both these problems when they are together (with the given choice of “Either this or that”) is much, much easier than solving them both individually! The interrelation between these 2 problems was not evident at first sight, which is the reason why so easy and simple problems had very less successful submissions during the contest.
Lets focus on this problem CUT first. Think like a lazy-man. “What is the cheapest, and easiest way by which I can solve this problem reasonably well?” It turns out that there is a very basic method after all!
Note that the problem only stresses on the size of the cut, not the size of the sets A and B!! So, this means, sets of size 1 are very much allowed . What we do is, after taking the input and storing the graph, we check for the degree of nodes. If we find any node with degree < K,the voila! We solved the problem!
Say we found a node with degree < K, then that means there are < K edges from that node to other nodes of the graph. Lets call this node X. We put this node in set A , and all other nodes in set B. Note that size of cut is nothing but number of edges between nodes in set A and nodes in set B. In other words, size of cut is nothing but number of edges from X to other nodes (i.e.its immediate neighbors). Size of cut, is hence, nothing but degree of X, which is < K.
If we fail to find any node with degree < K, then there isn’t any “cheap” solution to this problem . We, like lazy-men, will cry that this problem is “too hard” and try moving on to the second problem.
2. Problem CYCLE-
(Pssst!!)
(Psssssst!!)
(Before reading anything, check out Question 5 b) here. DONT TELL HASAN OR HE’LL KILL ME.)
(PS- For those who don’t understand, \delta (G) \ge K means “degree of all nodes is \ge K.”)
I will not explain the above proof in detail here. I will however, give hints and links for reference so that you can derive the result yourself. This argument and method of proof is not uncommon in questions of competitive coding, and they often appear in harder ones like this question. I will, however, give an alternate intuition/informal-proof to the claim.
By above, we (at least now) know that, if we have a graph where degree of each node is at least K, then there will be a cycle of length at least K (or K+1 to be more accurate). Let me highlight the interrelation of problems here. If we start by attempting to solve problem CUT, then there are two outcomes-
- We may find a node with degree < K and solve it. No need to worry about problem CYCLE then.
- We may not be able to find a node with degree < K. This implies that, all the nodes have degree \ge K !!. Hence, the cycle problem is trivially solvable under these assumptions.
First I will describe how to solve CYCLE under the assumption that all nodes have degree \ge K (or that we first tried solving CUT but failed to find an appropriate node).
What we will do is, a simple DFS of the graph. We use an array, say time[], to mark which node we visited first, which node we visited second &etc. More precisely, if time[a]=b, then that means “Starting from the chosen root, Node a is the b'th node we visited.” As simple as a cake.
Now, we keep on traversing till we find a node whose all neighbors are already visited. Note that we are bound to find such a node (Why? Q-1). Once we find such a node, we “close” the cycle by going back to the neighbor which was visited earliest (Why? Q-2). All that is left to be done, is to retrace the path backwards until we reach to the same node again. Implementation wise, we can easily do that using a stack (or vector or any suitable data structure). You can refer to editorialist’s commented solution to see how the idea is implemented.
Now, why is this correct? Why does our claim hold, that a cycle of length K+1 will definitely exist if all nodes have a degree \ge K? Formal proof, is left to readers as an exercise. I will provide you with sufficient hints (well, I have provided you with the solution itself xD) so that you guys can derive it on your own- this is so that the concept can be used by you for solving future hard problems. But its obvious that not many go for pen and paper and derive using countless pages the claim above. There is something called a “killer-instinct” or intuition. Lets try to prove this intuition-wise, with an informal proof.
Lets say, we are doing DFS of a graph, and node X is the last node left which we haven’t visited. On visiting X, we see all the neighbors are visited as well, and that X has edges going to them which means a cycle definitely exists. If we chose the earliest visited nodes, we can get a cycle which contains, at least, all the neighbors of X (i.e. the largest possible cycle). Since number of neighbors of X is \ge K, the cycle must have a length of at least K+1. We can very easily generalize this to any node of graph whose all neighbors are visited, instead of “last node” as I took.
3.Conclusion
Not much to say. During contest, I think \approx 21 people solved the question during the contest (counting from both divisions combined). The reason for this is not hard to see. At first, lot of people simply got scared on seeing 2 NP-Hard problems. Then, the interrelation of the 2 problems was clearly not obvious from first sight. However, lets appreciate the sheer beauty and concept of the problem, and how the setter interrelated 2 NP-Hard problems into such a beautiful one. And well, in the end, it didnt quite turn out to be “Solve whatever you want” exactly, unless you have the ability solve NP-Hard problems in linear time. (Pssst, if you have that, just teach me that so I can claim a few million dollars XD).
SOLUTIONS:
The solutions are also copied in the tabs, so that you guys dont have to wait for @admin to upload them etc. and can immediately access them. Copy the solutions from here and paste anywhere you are comfortable reading them.
Click to view
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int> g[N];
bool vis[N];
int tVis[N];
int main() {
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
int cases;
cin >> cases;
while (cases--) {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
g[i].clear();
vis[i] = false;
}
for (int i = 1; i <= m; ++i) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
int x = -1;
for (int i = 1; i <= n; ++i) {
if (int(g[i].size()) < k) {
x = i;
break;
}
}
if (x != -1) {
cout << "CUT\n";
cout << "1\n" << x;
} else {
vector<int> st;
int v = 1;
int timer = 0;
while (!vis[v]) {
vis[v] = true;
st.push_back(v);
tVis[v] = ++timer;
int notVisU = -1, minVisU = -1;
for (size_t j = 0; j < g[v].size(); ++j) {
int u = g[v][j];
if (!vis[u]) {
notVisU = u;
break;
} else {
if (minVisU == -1 || tVis[minVisU] > tVis[u]) {
minVisU = u;
}
}
}
if (notVisU != -1) {
v = notVisU;
} else {
cout << "CYCLE\n";
vector<int> cycle;
while (st.back() != minVisU) {
cycle.push_back(st.back());
st.pop_back();
}
cycle.push_back(st.back());
cout << cycle.size() << "\n";
for (size_t i = 0; i < cycle.size(); ++i) {
cout << cycle[i] << " ";
}
break;
}
}
}
cout << "\n";
}
return 0;
}
Click to view
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <string>
#include <vector>
#include <set>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,m,k;
vector<int> adj[200200];
vector<int> ind[200200];
set<pair<int,int>> gg;
int sm_n=0,sm_m=0;
int order[200200];
bool vis[200200];
int bef[200200];
void dfs(int nd){
vis[nd]=true;
for(int i=0;i<adj[nd].size();i++){
int ch=adj[nd][i];
if(vis[ch])continue;
dfs(ch);
}
}
int main(){
T=readIntLn(1,100);
while(T--){
n=readIntSp(2,200000);
m=readIntSp(2,200000);
k=readIntLn(2,n);
sm_n += n;
sm_m += m;
gg.clear();
assert(sm_n<= 200000);
assert(sm_m<= 200000);
for(int i=1;i<=n;i++){
order[i]=-1;
vis[i]=false;
adj[i].clear();
ind[i].clear();
}
for(int i=1;i<=m;i++){
int a,b;
a=readIntSp(1,n);
b=readIntLn(1,n);
assert(a!=b);
assert(gg.count(make_pair(a,b)) == 0);
assert(gg.count(make_pair(b,a)) == 0);
gg.insert(make_pair(a,b));
adj[a].push_back(b);
adj[b].push_back(a);
ind[a].push_back(i);
ind[b].push_back(i);
}
dfs(1);
for(int i=1;i<=n;i++){
assert(vis[i]);
}
int cut=-1;
for(int i=1;i<=n;i++){
if(adj[i].size() < k){
cut = i;
break;
}
}
if(cut != -1){
printf("CUT\n");
printf("%d\n",1);
printf("%d\n",cut);
continue;
}
vector<int> cycle;
int cur = 1;
int c=0;
bool found=false;
while(true){
order[cur]=c++;
for(int i=0;i<adj[cur].size();i++){
int ch=adj[cur][i];
if(ch==bef[cur])continue;
if(order[ch] == -1){
bef[ch]=cur;
cur=ch;
break;
} else if(c- order[ch] >= k ){
found=true;
while(cur != ch){
cycle.push_back(cur);
cur=bef[cur];
}
cycle.push_back(ch);
break;
}
}
if(found){
break;
}
}
printf("CYCLE %d\n",cycle.size());
for(int i=0;i<cycle.size();i++){
printf("%d ",cycle[i]);
}
}
assert(getchar()==-1);
}
Click to view
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> arr[300000];
bool endDFS=false;
int timer=0;//Time and timer variables are used in Euler tour of the graph. Go ahead an have a look at the concept after this!!
void DFS(int u,int v,int time[],stack<int> &st)//Stack passed by reference. "&" operator represents passing
//memory address instead of copying the entire value.
{
if(time[u]>0 or endDFS==true)
return; //Already visited.
time[u]=timer++;
st.push(u);
bool noNodeVisited=true;
int earliestVisitedNode=10000,minTime=10000000;
for(auto i:arr[u])
{
if(i!=v and time[i]==0)//Simple DFS
{
noNodeVisited=false;
DFS(i,u,time,st);
} else if(time[i]<minTime)//Earliest visited vertex calculation goes on simultaneously. (So we dont have to do it
//inside the if(noNodeVisited==true) condition. Lazy me :3
{
minTime=time[i];
earliestVisitedNode=i;
}
}
if(noNodeVisited==true)
{
endDFS=true;
vector<int> cycle;//Store cycle in an array
while(st.top()!=earliestVisitedNode)
{
cycle.push_back(st.top());
st.pop();
}
cycle.push_back(earliestVisitedNode);
assert(earliestVisitedNode==st.top());
cout<<"CYCLE\n"<<cycle.size()<<"\n";
for(auto i:cycle)
cout<<i<<" ";
cout<<"\n";
return;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
//Input Taking
cin>>n>>m>>k;
int i,u,v;
for(i=0;i<=n;i++)
{
arr[i].clear();
}
for(i=0;i<m;i++)
{
cin>>u>>v;
arr[u].push_back(v);
arr[v].push_back(u);
}
//Mindegree= Minimum Degree, minU = vertex U with minimum degree
int minDegree=n,minU=-1;
for(i=1;i<=n;i++)
{
if(arr[i].size()<minDegree)
{
minDegree=arr[i].size();
minU=i;
}
}
if(minDegree<k)
{
//Note that cut problem never says about size of sets A and B!! Hence, we make size of set A as 1,
//It will contain only vertex u, found above.
assert(minU!=-1);
cout<<"CUT\n"<<1<<"\n"<<minU<<"\n";
}
else
{
//Each vertex has a degree >=k ==>A cycle of length atleast k (or actually, k+1) MUST exist.
//We will do as described in editorial. DFS until we find a node whose every neighbour is visited.
//Close the cycle by placing edge between that node and the node visited earliest for largest cycle length.
//Setter's solution used iterative DFS for that, I will do recursive as its intuitive.
int time[200100]={0};
timer=0;
endDFS=false;
stack< int > st;
DFS(1,0,time,st);
}
}
return 0;
}
CHEF VIJJU’S CORNER:
1. Answer of Q-1-
“Now, we keep on traversing till we find a node whose all neighbors are already visited. Note that we are bound to find such a node (Why? Q-1).”
Click to view
Refer to the example I gave there on lines of last node. Each node has a degree of K , and they are all finite. At the end of the day, there has to be one last node which we visit, and for that last node, all of its neighbors must be already visited, else that node isnt the last node.
Hence, we proved this by existence, saying that the last node will always fit in the description.
2. Answer for Q-2-
“Once we find such a node, we “close” the cycle by going back to the neighbor which was visited earliest”
Click to view
This is done to get cycle of largest possible length, which guarantees that this cycle will be of length at least K. Else, we may end up with a smaller cycle. Some hand made examples will do good to you.
3. Setter’s Notes-
Click to view
Let’s consider vertex v with minimal degree (degree is number of neighbors). If degree(v) < k, than we have found a good cut: we can choose A = \{v\}. Otherwise, for all vertices v is true that degree(v) \geq k. Let’s go from vertex v in neighbor u, if it’s not visited earlier, after that, go from u to not visited vertex w and so on. In some moment we will have the situation that all neighbors of some vertex f is visited earlier, let’s consider neighbor which we have visited earlier than another ones (u). It’s clear that path between u and f through visited vertices and edge (u, v) forms a correct simple cycle.
4. Tester’s Notes-
Click to view
Brief Solution for NPORP: If there’s one node with degree less than K,
then we have found a cut, we can cut all edges connected to that node.
Now let’s assume the degree of all nodes is at least K and try to find a cycle of length K. Let’s start at arbitrary node and continue walk to arbitrary unvisited node, each time we visit a node we write a number on it starting from 1 for the first node and 2 for second node we visit and so on (Editorialist’s Note- He is referring to the time array I mentioned).
When we reach a node where all adjacent nodes are already visited now we choose the node having the least number on it (Editorialist’s Note- i.e. earliest visited node) and close the cycle there. Since we know the degree of the current
node is at least K and all numbers on all nodes are distinct we know
our cycle will have length at least K.
5. The time array, which I mentioned is frequently used in defining time of entry, and exit in a subtree ,assuming visiting a node takes unit (or W_i, depending on the question) time. You can try learning about Euler Path and Tour, and then Heavy Light Decomposition.
6. Test Case Bank-
Click to view
Currently Empty. There were no test cases which proved tricky or edgy. The implementation also had very little scope of error. If, however, you got WA and cant find the failing case, feel free to comment on the editorial with link to your solution. I request the community to help in maintaining it by editing and adding the test cases themselves in case I miss updating the editorial.
7. Common Errors-
Click to view
1. Not interrelating the problems leading to a difficult and wrong implementation/idea. Eg- Trying to solve CYCLE problem first without condition of “Degree of all nodes is \ge K”
2. Not resetting global variables and not clearing the graph after each test case.
Aside from that, most solutions had unique errors in implementation. Some did not follow constraint that cycle must be of length at least K and printed any cycle. There were many avoidable errors committed, perhaps due to panic as the problem seemed tough. Lets try to avoid that hence forth
8. The crux of the question was how deeply you know the theorems in Graph Theory. For instance, if you already knew or induced that “If graph has all nodes of degree at least K, then problem CYCLE is easily solvable”. Remember that, under certain assumptions and given conditions, the NP-Hard problems do have an easy solution. They are NP-Hard for a general scenario where none of the assumptions may hold. If you knew the above claim for CYCLE problem, you can work out the rest for CUT problem to get an easy AC.
9. Links and Hints for formal proof mentioned in problem CYCLE-
Click to view
Full Solution - The one I gave earlier.
StackOverflow Answer - Uses the path argument. Similar to my last node argument/case.