But the runtime memory limits at codeforces are HUGE. I don't think the runtime errors are a result of memory shortages.
It's quite sad really, because the functional style that is so easy to use when you program Python is really nice.
Codeforces: 263D - Cycle in Graph, Run time error Test 12
Re: Codeforces: 263D - Cycle in Graph, Run time error Test 1
dfy wrote:But the runtime memory limits at codeforces are HUGE. I don't think the runtime errors are a result of memory shortages.
It's quite sad really, because the functional style that is so easy to use when you program Python is really nice.
Yes, I agree,
the Python programs look neat.
Re: Codeforces: 263D - Cycle in Graph, Run time error Test 1
This python solution got accepted in roughly 500ms:
The following C++ code has the same idea, but is slightly more optimized: (about 170ms)
Code: Select all
n, m, k = map(int, raw_input().split())
e = [[] for _ in xrange(n + 1)]
for i in xrange(m):
x, y = map(int, raw_input().split())
e[x].append(y)
e[y].append(x)
curr = 1
chain =[]
inchain = [0]*(n+1)
while True:
if inchain[curr] == 1:
break
chain.append(curr)
inchain[curr] = 1
for i in e[curr]:
if inchain[i] == 0:
curr = i
break
minindex = min(map(chain.index,e[curr]))
print len(chain) - minindex
print ' '.join(map(str,chain[minindex:]))
The following C++ code has the same idea, but is slightly more optimized: (about 170ms)
Code: Select all
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using std::vector;
using std::map;
int main() {
int n,m,k;
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
vector< vector<int> > edges(n+1,vector<int>());
for (int i = 0; i < m; i++) {
int a,b;
scanf("%d",&a);
scanf("%d",&b);
edges.at(a).push_back(b);
edges.at(b).push_back(a);
}
vector<int> chain;
chain.reserve(n);
map<int,int> chainpos;
int startnode = 1;
int curr = startnode;
while (true) {
if (chainpos.find(curr) != chainpos.end()) break;
chain.push_back(curr);
chainpos[curr] = chain.size() - 1;
for (auto cit = edges.at(curr).cbegin(),
citl = edges.at(curr).cend();
cit != citl; cit++) {
if (chainpos.find(*cit) == chainpos.end()) {
curr = *cit;
break;
}
}
}
int minindex = chainpos[curr];
for (auto cit = edges.at(curr).cbegin(),
citl = edges.at(curr).cend();
cit != citl; cit++) {
minindex = std::min(minindex, chainpos[*cit]);
}
printf("%d\n",chain.size() - minindex);
for (int i = minindex; i < chain.size(); i++) {
printf("%d ", chain.at(i));
}
printf("\n");
return 0;
}
Re: Codeforces: 263D - Cycle in Graph, Run time error Test 1
dfy wrote:This python solution got accepted in roughly 500ms:Code: Select all
n, m, k = map(int, raw_input().split())
e = [[] for _ in xrange(n + 1)]
for i in xrange(m):
x, y = map(int, raw_input().split())
e[x].append(y)
e[y].append(x)
curr = 1
chain =[]
inchain = [0]*(n+1)
while True:
if inchain[curr] == 1:
break
chain.append(curr)
inchain[curr] = 1
for i in e[curr]:
if inchain[i] == 0:
curr = i
break
minindex = min(map(chain.index,e[curr]))
print len(chain) - minindex
print ' '.join(map(str,chain[minindex:]))
The following C++ code has the same idea, but is slightly more optimized: (about 170ms)Code: Select all
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using std::vector;
using std::map;
int main() {
int n,m,k;
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
vector< vector<int> > edges(n+1,vector<int>());
for (int i = 0; i < m; i++) {
int a,b;
scanf("%d",&a);
scanf("%d",&b);
edges.at(a).push_back(b);
edges.at(b).push_back(a);
}
vector<int> chain;
chain.reserve(n);
map<int,int> chainpos;
int startnode = 1;
int curr = startnode;
while (true) {
if (chainpos.find(curr) != chainpos.end()) break;
chain.push_back(curr);
chainpos[curr] = chain.size() - 1;
for (auto cit = edges.at(curr).cbegin(),
citl = edges.at(curr).cend();
cit != citl; cit++) {
if (chainpos.find(*cit) == chainpos.end()) {
curr = *cit;
break;
}
}
}
int minindex = chainpos[curr];
for (auto cit = edges.at(curr).cbegin(),
citl = edges.at(curr).cend();
cit != citl; cit++) {
minindex = std::min(minindex, chainpos[*cit]);
}
printf("%d\n",chain.size() - minindex);
for (int i = minindex; i < chain.size(); i++) {
printf("%d ", chain.at(i));
}
printf("\n");
return 0;
}
This looks great, could you explain that how do you make use of the fact that 'the minimal degree is k' ?
Re: Codeforces: 263D - Cycle in Graph, Run time error Test 1
It's funny because k is not used at all in the code, but in fact it has a very crucial role: The algorithm is only guaranteed to work because you have that k.
If you have some experience in graph theory, try to prove the following: Every graph of minimal degree k has a cycle of length at least k+1. (So in fact, the test cases are not specially tailored to fit the test constraints, this holds for every such graph!) The proof is rather easy and proves that this nice construction (construct a max-length path, so that the last node has all its neighbours inside the path) really works.
edit: Ah, I just saw the notice at the top saying you don't want accepted code - sorry. I guess it's fine for finished codeforces contests though because everyone can see everyone else's code there, anyways...
If you have some experience in graph theory, try to prove the following: Every graph of minimal degree k has a cycle of length at least k+1. (So in fact, the test cases are not specially tailored to fit the test constraints, this holds for every such graph!) The proof is rather easy and proves that this nice construction (construct a max-length path, so that the last node has all its neighbours inside the path) really works.
edit: Ah, I just saw the notice at the top saying you don't want accepted code - sorry. I guess it's fine for finished codeforces contests though because everyone can see everyone else's code there, anyways...
Re: Codeforces: 263D - Cycle in Graph, Run time error Test 1
dfy wrote:It's funny because k is not used at all in the code, but in fact it has a very crucial role: The algorithm is only guaranteed to work because you have that k.
If you have some experience in graph theory, try to prove the following: Every graph of minimal degree k has a cycle of length at least k+1. (So in fact, the test cases are not specially tailored to fit the test constraints, this holds for every such graph!) The proof is rather easy and proves that this nice construction (construct a max-length path, so that the last node has all its neighbours inside the path) really works.
edit: Ah, I just saw the notice at the top saying you don't want accepted code - sorry. I guess it's fine for finished codeforces contests though because everyone can see everyone else's code there, anyways...
Thanks... this helps a lot..
No problem, hehe, I said 'recommended', but you are right, on codeforces, all code are visible.