Codeforces: 263D - Cycle in Graph, Run time error Test 12

[dfy]

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.

[doctorlai]

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.

[dfy]

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;
}

[doctorlai]

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' ?

[dfy]

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...

[doctorlai]

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.