Debugging Tips

Debugging Tips

Helpful tips for debugging, consistently improved

1. Sample Test Case Wrong?

Most likely an "obvious" bug (rather, a "big" bug) is hiding. Add breakpoints or print logs in the most suspected points in code, and start tracing from the point that first gives wrong answers.

2. Wrong Answer?

Below 30% AC

It is oft that faulty conditional predicates or statements occur, making the conditions that the sample test case run through all correct, but making other test cases that pass other conditionals wrong. Inspect every line closely, and print logs on every faulty (or so you think) line. If none shows the error, make different test cases.

40~70% AC

Some borderline test cases twine the flow of execution, making some statements or predicates faulty. The entire program can house many of these; search every line and try test cases that would make any line fail.

Above 80% AC

Contest mode: Skip it.
Learning mode: Construct various types of borderline test cases. If all are correct, attempt the test data.

3. Time Limit Exceeded?

Below 10% AC

There's an infinite loop. Search all "while" and "do-while" loop predicates for constantly True answers.

20% ~ 50% AC

Check for array bounds. Also, make slight optimizations like "ios_base::sync_with_stdio(false);" or lowering a few limits.

Above 60% AC

Revamp the algorithm.

4. Runtime Error?

Check limits and array boundaries.

USACO Silver Division March 2007, Monthly Expense

Description

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input Line 1: Two space-separated integers: N and M Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input 7 5 100 400 300 100 500 101 400 Sample Output

500

Hint If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.

Simple Interpretation

Given N numbers, group them into M groups such that the maximum of the sums of the numbers in each group is minimal. However, numbers e.cannot be swapped of position, (e.g. if there are 4 numbers, 1 2 3 4, and M=2, a grouping "1 4" "2 3" would be invalid, but "1 2 3" "4" would be valid and optimal).

The Algorithm

At first sight this may look like a set partitioning problem, which is NP-Complete. But upon further inspection, we realize that days cannot be swapped, so we can do a simple binary search on the possible monthly limits. Because we are searching for the monthly LIMIT, any number X that satisfies the limit will imply that X+1 also satisfies the limit. Grouping the numbers with an upper bound of X per group is an O(N) computation, iterating over all numbers. This computation is our predicate; if we can form a grouping X becomes our upper bound, if not X+1 becomes our lower bound.

The Code Itself

#include <cstdio>
using namespace std;

int r[100005];
int days, periods;
int low;

bool attempt(int n)
{
    int now=0, p=periods;
    for(int i=0;i<days;i++)
    {
        if(n<r[i]) return false;
        now += r[i];
        if(now>n)
        {
            now=r[i];
            p--;
        }
    }
    if(p<1) return 0;
    return 1;
}

int main()
{
    scanf("%d%d", &days, &periods);
    for(int i=0;i<days;i++)
    {
        scanf("%d",&r[i]);
        low += r[i];
    }
    int lb=0,ub=low,c;
    while(lb<ub)
    {
        c=(lb+ub)/2;
        if(attempt(c)) ub=c;
        else lb=c+1;
    }
    printf("%d\n",ub);
    return 0;
}

USACO Gold Division December 2016, Lasers and Mirrors

USACO Gold December 2016 "Lasers and Mirrors"

Problem Statement (Original)

For some reason, Farmer John's cows always seem to be running laser light shows. For their latest show, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move it easily from the location where it was delivered. They would like to somehow send the light from the laser to the barn on the other side of FJ's property. Both the laser and the barn can be considered to be located at points in the 2D plane on a map of FJ's farm. The cows plan to point the laser so that it sends a beam of light out either horizontally or vertically (i.e., aligned with the x or y axes). They will then bounce this beam off a number of mirrors to direct it to the barn.

On the farm there are N fence posts (1≤N≤100,000) located at distinct 2D points (also distinct from the laser and the barn) at which the cows can mount mirrors. The cows can choose not to mount a mirror on a fence post, in which case the laser would simply pass straight over the top of the post without changing direction. If the cows do mount a mirror on a fence post, they align it diagonally like / or so that it will re-direct a horizontal beam of light in a vertical direction or vice versa.

Please compute the minimum possible number of mirrors the cows need to use in order to re-direct the laser to the barn.

INPUT FORMAT (file lasers.in):

The first line of input contains 5 space-separated integers: N,xL,yL,xB,yB, where (xL,yL) is the location of the laser and (xB,yB) is the location of the barn. All coordinates are between 0 and 1,000,000,000

The next N lines each contain the x and y locations of a fence post, both integers in the range 0...1,000,000,000.

OUTPUT FORMAT (file lasers.out):

Please output the minimum number of mirrors needed to direct the laser to the barn, or -1 if this is impossible to do. SAMPLE INPUT: 4 0 0 7 2 3 2 0 2 1 6 3 0 SAMPLE OUTPUT: 1 Problem credits: Brian Dean

Simple Interpretation

A train is on an infinite grid tiled with unit squares. The unit squares have edges of tracks. No edge comprises of two tracks. The train starts at location (xL,yL), and its destination is (xB, yB). However, the train conductor, being incredibly idiotic, ambles the train forward in the same direction until he runs into one of the N signal posts. He turns the train left or right depending on the direction of the arrow electronically displayed. Then, he continues. The Department of Railways change the displays on the signal posts. Please help the Department of Railways compute the minimum amount of displays they need to turn on given the N locations, or return -1 if the conductor needs to be fired (he cannot reach the destination, no matter what signs are turned on.)

The Algorithm

We can first generate an Edge List given the N vertexes. For each vertex, we search the other N-1 vertexes to see if pairings can be made. Pairings can be made IFF N and M (the child) share one X or Y value. Then, after creating the edge list, a standard SPFA can be done. Alternatively, we can use path compression (NOT the DSDS one) to quicken up the SPFA by removing empty rows and columns. This also removes the requirement for Edge List since it shrinks the graph so much.

My Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> G[500000];
vector<int> U[500000];
int Gv[500000];
int Uv[500000];
int que[5000000];
bool in[500000];
int dist[500000];
int Ginput[500000];
int Uinput[500000];
int n;

void comp(int* start, int* buf, vector<int>* pipe)
{
    int* prcopy = new int[n];
    for(int i=0;i<n;i++)
        prcopy[i]=start[i];
    sort(prcopy, prcopy+n);
    long d = unique(prcopy,prcopy+n)-prcopy;
    for(int i=0;i<n;i++)
    {
        buf[i]=lower_bound(prcopy, prcopy+d, start[i])-prcopy;
        pipe[buf[i]].push_back(i);
    }
}

int bfs()
{
    int h=0,t=0;
    que[t++]=0;
    in[0]=1;
    memset(dist, 127, 500000);
    dist[0]=0;
    while(h!=t)
    {
        int pop=que[h++];
        for(int i=0;i<G[Gv[pop]].size();i++)
        {
            int x = G[Gv[pop]][i];
            if(!in[x] && dist[pop]+1<dist[x])
            {
                    dist[x]=dist[pop]+1;
                    if(x==1)
                        return dist[1];
                    que[t++]=x;
                    in[x]=1;
            }
        }
        for(int i=0;i<U[Uv[pop]].size();i++)
        {
            int x = U[Uv[pop]][i];
            if(!in[x] && dist[pop]+1<dist[x])
            {
                    dist[x]=dist[pop]+1;
                    if(x==1)
                        return dist[1];
                    que[t++]=x;
                    in[x]=1;
            }
        }
        in[pop]=0;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    freopen("lasers.in","r",stdin);
    freopen("lasers.out","w",stdout);
    scanf("%d %d %d %d %d", &n, &Ginput[0], &Uinput[0], &Ginput[1], &Uinput[1]);
    for(int i=0;i<n;i++)
        scanf("%d %d",&Ginput[i+2],&Uinput[i+2]);
    n+=2;
    comp(Ginput, Gv, G);
    comp(Uinput, Uv, U);
    printf("%d\n",bfs()-1);
}

GitHub – testitem

Darren Li

New York City