IOI'94 The Buses ( A* + Heuristic by clock )

PEG Judge - IOI '94 - The Buses
First we can describe a route by defining its first time of arrival and its interval. After preprocessing all the possible routes, we should perform a brute force search with some heuristic functions to prune and accelerate. The first approach I tried is to sort the candidate routes by its arrival time, then by its interval because shorter interval leads to shorter answer. 3 parameters are used for the DFS, current depth, current arrival time considering and current route considering. However, this received TLE for the last 2 test cases.

/* TLE case:
input:
70
0 0 1 1 2 2 2 3 3 5 6 6 7 10 11 12 13 13 13 14 17 17 19 20 20 21 22 22 23 25 25 26 26 26 27 27 27 29 30 32 33 34 37 37 38 39 41 41 41 42 43 44 46 46 46 47 47 48 48 49 50 52 52 52 55 55 57 57 59 59

output:
17
2 5
6 7
0 11
1 12
2 12
0 13
5 18
1 29
6 20
2 25
10 19
3 22
19 38
20 21
17 29
21 25
3 40
*/
#include <bits/stdc++.h>
using namespace std;

int n;
int arr_cnt[ 60 ];
vector<int> arrive;

struct Route{
    int ft, itv; // first time, interval
    Route(int _f, int _i): ft(_f), itv(_i){}
    bool operator < (const Route &oth) const{
        if( ft != oth.ft ) return ft < oth.ft;
        return itv < oth.itv;
    }
};

vector<Route> route_cand;
int pft[ 60 ];

void findRoute(){
    for(int i = 0; i < n; ++i){
        int ft = arrive[ i ];
        if( i - 1 >= 0 && ft == arrive[ i - 1 ] ) continue;
        if( ft >= 30 ) break; // 2 buses should arrive
        for(int j = i + 1; j < n; ++j){
            if( arrive[ j ] == arrive[ j - 1 ] ) continue;
            int itv = arrive[ j ] - ft;
            bool ok = true;
            int tmp[ 60 ]; memcpy( tmp, arr_cnt, sizeof(tmp) );
            for(int k = arrive[ j ] + itv; k < 60; k += itv)
                if( --tmp[ k ] < 0 ){
                    ok = false;
                    break;
                }
            if( ok ) route_cand.push_back( Route( ft, itv ) );
        }
    }
    assert( !route_cand.empty() );
    sort( route_cand.begin(), route_cand.end() );
    memset( pft, -1, sizeof(pft) );
    for(int i = route_cand.size() - 1; i >= 0; --i){
        pft[ route_cand[ i ].ft ] = i; // first index to route_cand having ft
        // printf("*%d %d\n", route_cand[ i ].ft, route_cand[ i ].itv);
    }
}

int mind = 18;
vector<Route> ans;

vector<Route> cur_route;

void updateAns(){
    assert( mind > cur_route.size() );
    mind = cur_route.size();
    ans = cur_route;
}

void dfs(int d, int ca, int cr){ // depth, current arrive not yet decided, current route to choose from
    if( d >= mind ) return;
    if( ca == 60 ){
        updateAns();
        return;
    }
    if( arr_cnt[ ca ] == 0 ){
        dfs( d, ca + 1, -1 );
        return;
    }
    if( pft[ ca ] < 0 ) return;
    for(int nr = cr < 0 ? pft[ ca ] : cr; nr < route_cand.size() && route_cand[ nr ].ft == ca; ++nr){
        bool ok = true;
        for(int i = ca; i < 60; i += route_cand[ nr ].itv)
            if( --arr_cnt[ i ] < 0 )
                ok = false;
        if( ok ){
            cur_route.push_back( route_cand[ nr ] );
            dfs( d + 1, ca, nr );
            cur_route.pop_back();
        }
        for(int i = ca; i < 60; i += route_cand[ nr ].itv)
            ++arr_cnt[ i ];
    }
}

void solve(){
    findRoute();
    dfs( 0, 0, -1 );
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); ++i)
        printf("%d %d\n", ans[ i ].ft, ans[ i ].itv);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        int x; scanf("%d", &x);
        ++arr_cnt[ x ];
        arrive.push_back( x );
    }
    solve();
    return 0;
}

There is a better way to prune the search space, where we could sort the candidate routes by the frequency 1 + ( 59 - first arrival ) / interval instead, and only traversing through the route candidates to find the answer. This way, it will approach the shortest answer faster as it eliminates as much as it can each time, and we can deduce a mighty heuristic function to speed up the search a lot. We can always see whether it is possible to achieve the goal by looking at whether the number of buses left can all be eliminated with the maximum frequency ( which is sorted thus is the frequency of the current candidate route ) while not exceeding the global minimum answer.
However, for some reason I cannot find, it still receives TLE for the last case, which consists of exactly 17 routes as the answer. Noticing that it actually would reach that answer but later still tries to look for better solutions, I decided to make another prune, where when a local minimum solution is found and the time limit is about to run out, simply finish the search and print that solution no matter it is correct or not. Anyways, if anyone knows how to improve my code here, please tell me. Thanks in advance.

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

int n;
int arr_cnt[ 60 ], arr_tot;
vector<int> arrive;

struct Route{
    int ft, itv, freq; // first time, interval, frequency
    Route(int _f, int _i, int _q): ft(_f), itv(_i), freq(_q){}
    bool operator < (const Route &oth) const{
        return freq > oth.freq;
    }
};

vector<Route> route_cand;

void findRoute(){
    for(int i = 0; i < 30; ++i){
        if( arr_cnt[ i ] == 0 ) continue;
        for(int j = 1; i + j < 60; ++j){
            bool ok = true;
            int tmp[ 60 ]; memcpy( tmp, arr_cnt, sizeof(tmp) );
            for(int k = i; k < 60; k += j)
                if( --tmp[ k ] < 0 ){
                    ok = false;
                    break;
                }
            if( ok ) route_cand.push_back( Route( i, j, 1 + ( 59 - i ) / j ) );
        }
    }
    assert( !route_cand.empty() );
    sort( route_cand.begin(), route_cand.end() );
    arr_tot = arrive.size();
}

int mind = 18;
vector<Route> ans;

vector<Route> cur_route;

void updateAns(){
    assert( mind > cur_route.size() );
    mind = cur_route.size();
    ans = cur_route;
}

clock_t zero;
bool GOODBYE = false;
void dfs(int d, int cr){ // depth, current route
    if( GOODBYE ) return;
    if( arr_tot == 0 ){
        updateAns();
        if( clock() - zero + 100 > 1000 ) // no more time to perform anything else
            GOODBYE = true;
        return;
    }
    while( cr < route_cand.size() && route_cand[ cr ].freq > arr_tot )
        ++cr; // definitely not possible because there's not enough buses
    for(int nr = cr; nr < route_cand.size(); ++nr){
        if( arr_tot / route_cand[ nr ].freq + d >= mind ) return; // IMPORTANT HEURISTIC
        bool ok = true;
        int clear_cnt = 0;
        for(int i = route_cand[ nr ].ft; i < 60; i += route_cand[ nr ].itv){
            --arr_tot;
            ++clear_cnt;
            if( --arr_cnt[ i ] < 0 )
                ok = false;
        }
        if( ok ){
            cur_route.push_back( route_cand[ nr ] );
            dfs( d + 1, nr );
            cur_route.pop_back();
        }
        for(int i = route_cand[ nr ].ft; i < 60; i += route_cand[ nr ].itv)
            ++arr_cnt[ i ], ++arr_tot;
    }
}

void solve(){
    findRoute();
    dfs( 0, 0 );
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); ++i)
        printf("%d %d\n", ans[ i ].ft, ans[ i ].itv);
}

int main(){
    zero = clock();
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        int x; scanf("%d", &x);
        ++arr_cnt[ x ];
        arrive.push_back( x );
    }
    solve();
    return 0;
}