Hi everyone,

I read about the SPFA a while ago and today I decided to try it out on some problems (for those who don't know about it

http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

http://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm )

Neither of the links above mentions anything about detecting negative cycles. Obviously, in the presence of a negative cycle, these implementations will never terminate. However, Steven Halim in his book says that it's sufficient to test whether a node entered the queue more than V - 1 times. Does anyone know a proof for this?

Hi everyone,

Well, I've been struggling with this problem for a while. The greedy approach is incorrect and there is a quite straightforward O(N^2) dp solution which will obviously not run in time. I gave up and tried to find solutions online but I couldn't find anything but a topcoder topic where there were some hints. If anyone can explain the solution of this problem it would be great.

Hi,

Today I was writing some recursive code and it behaved in a very weird way and I couldn't find out why this happened,

Here is the code

http://ideone.com/cDrZs8

It gives runtime error, and doesn't assign the values correctly!

However if I do it like this

http://ideone.com/z5pOul

Everything just works perfectly! I feel I'm missing something but I couldn't figure it out for over half an hour and yet the code is simple (I suppose).

It would be greatly appreciated if anyone could point out the problem.

Thanks!

Hi, I'm having a really hard time implementing a recursive descent parser for this problem http://www.spoj.com/problems/FOOL/

I made a correct CYK parser implementation for it but it always gets TLE. I'm not very familiar with recursive descent parsers as it seems! I made one that seems to be very terrible and buggy.

I dunno how to approach this problem and how to make a correct recursive descent parser implementation for it. If anyone could help it would be much appreciated!

By the way, my implementation can accept an invalid string by reading just some few characters from the start! I always had this problem with the parsers I make, if a prefix of the string is in the language, the parser may read it and stop and don't continue to the end!!

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iostream>
#include <bitset>
#include <map>
#include <ctime>
#include <set>
#include <complex>
 
using namespace std;
 
typedef long long ll;
 
char str[300];
int len, cur;
 
bool Set();
bool list();
bool Element();
bool Set();
bool Atom();
 
bool Set(){
    int save = cur;
    if(str[cur] == '{' && str[cur+1] == '}'){
        cur += 2;
        return true;
    }
    cur = save;
    if(str[cur] == '{'){
        cur++;
        if(list() && str[cur] == '}'){
            cur++;
            return true;
        }
    }
    cur = save;
    return false;
}
 
 
 
bool list(){
    int save = cur, save2;
    if(Element()){
        save2 = cur;
        if(str[cur] == ','){
            cur++;
            if(list()){
                return true;
            }
        }
        cur = save2;
        return true;
    }
    cur = save;
    return false;
}
 
bool Element(){
    int save = cur;
    if(Set()){
        return true;
    }
    cur = save;
    if(Atom()){
        return true;
    }
    cur = save;
    return false;
}
 
bool Atom(){
    if(str[cur] == '{' || str[cur] == '}' || str[cur] == ','){
        cur++;
        return true;
    }
    return false;
}
 
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    int t, c = 1;
    
    scanf("%d ", &t);
    
    
    while(t--){
        memset(str, '\0', sizeof str);
        gets(str);
        
        len = strlen(str);
        cur = 0;
        
        printf("Word #%d: ", c++);
        
        if(Set()){
            printf("Set\n");
        }else{
            printf("No Set\n");
        }
        
    }
    return 0;
}