_shanky's blog

By _shanky, history, 5 years ago, In English

In yesterday's Div2 E I was stuck at finding the shortest cycle. I was using dfs and each time a backedge (x,y) occurred I was keeping the minimum of level[x]-level[y]+1 only to realize it was wrong. The answer would depend on the order of dfs traversal. So I randomly shuffled adjacency lists few times and used dfs each time while keeping the minimum. I managed to pass all test cases. Is there any proof that the correct answer will be found with high probability with this approach or I just managed to be lucky?

Link to the submission

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

I used the example I found yesterday here : https://stackoverflow.com/questions/20847463/finding-length-of-shortest-cycle-in-undirected-graph

Instead of one chain from A to C, I used 8 horizontal chains between B to D.

Gave 8 as the input to the following :

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define vi vector<int>

const int N = 1000;
vi isprime(N,1);
vi primes;

void sieve()
{
    isprime[1] = isprime[0] = 0;
    
    for(int i=2;i<N;i++)
        if(isprime[i])
          for(int j=i*i;j<N;j+=i) isprime[j] =0;
      
    for(int i=2;i<N;i++)
        if(isprime[i]) primes.pb(i);
}

void solve()
{
   int line;
    cin >> line;
    
   int len = (2*line);
   int cn = 0;
    
    random_shuffle(primes.begin(),primes.end());
    
    int extra[2];     
    int head[line]; 
    int tail[line]; 
    int between[line][len];
    
    extra[0] = primes[cn++];
    extra[1] = primes[cn++];
    f(i,line) head[i] = primes[cn++];
    f(i,line) tail[i] = primes[cn++];
    f(i,line) f(j,len) between[i][j] = primes[cn++];
   
    vi res;
    
    f(i,line) f(j,len-1) res.pb(between[i][j]*between[i][j+1]);
    f(i,line) res.pb(head[i]*between[i][0]);
    f(i,line) res.pb(tail[i]*between[i][len-1]);
    f(i,line-1) res.pb(head[i]*head[i+1]);
    f(i,line-1) res.pb(tail[i]*tail[i+1]);
    res.pb(extra[0]*head[0]);
    res.pb(extra[0]*tail[0]);
    res.pb(extra[1]*head[line-1]);
    res.pb(extra[1]*tail[line-1]);
    
    cout << res.size() << '\n';
    for(auto x : res) cout << x <<" ";
}

signed main()
{
    sieve();
    solve();
}
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah. So that was probably due to weak test cases. Thank you.