Modifying TZTester

TZTester is one of a great plugin for TopCoder SRM. It adds sample test cases of problem statements into the local code automatically (which is generated by CodeProcessor plugin, normally). This function encourages us to write the code as test-first, this is quite helpful to find bugs and fix it quickly. How to introduce these plugins is described here:

How to install The Arena plug-ins – TopCoder Wiki

However, I had little two dissatisfaction about generated test cases of TZTester.

1. There are no enough new lines in test cases. This makes little hard to add new own test cases.
2. I’d like to put more two cases into the tail of test cases. This intends that it enforce me to think about another tests for considering corner cases or worst cases.

So I’ve tried to modify my TZTester.

How to modify

TZTester is written in Java. I’ve had a little experience for java development. So I’ve confused several times for modification. Because of this, this section is maybe so dully for java programmer.

Step 1: Extract .jar file

TZTester is distributed as .jar file format. “.jar” file is just a zip file. I don’t know about the difference between jar and zip. So don’t be afraid.If Java development environment has been set up on your system, perhaps there are “jar” command. In my case (Mac OSX), the command seems to be bundled. You can extract and compress jar file by this command. The interface of jar command is quite similar to tar command:

// extracting
% jar -xvf foo.jar

// compressing
% jar -cvf foo.jar foo bar baz/

If you don’t have a jar command, try unzip command since jar file is just a zip file, again.Now let’s extract a TZTester.jar. If you type this command:

% jar -xvf TZTester.jar

Then you will get these files:

• tangentz/
  • TZTester.java
  • TZTester.class
  • TZTester.html
• META-INF/

The only important file is TZTester.java. This is a source code of TZTester. TZTester.class is a compiled file of TZTester.java, and TZTester.html is just a manual file.

Step 2: Editting TZTester.java

Now we could get a source code of TZTester. So only you have to do is editing this code. For instance, you’d like to modify test cases, these are generated by generate_test_case() or generate_parameter() method.

Step 3: Compiling TZTester.java, and make TZTester.jar

Before compiling, TZTester requires ContestApplet.jar file, so you need to get this jar. ContestApplet.jar could be downloaded from here. And then put the downloaded ContestApplet.jar file to same directory with tangentz/. ContestApplet.jar contains classes, which is used by TZTester. Also you need to pay attention to the directories, put the source code in tangetz/ directory, ContestApplet.jar and Makefile (describe later) in same directory with tangentz/ itself.

your_working_dir/
| -- ContestApplet.jar
| -- Makefile
` -- tangentz/
     |-- TZTester.java
     `-- (TZTester.class)

For compiling, firstly just type this commands in “your_working_dir”:

% javac -classpath ContestApplet.jar tangentz/TZTester.java

Then TZTester.class is generated. Next step, make jar file from .class file.

% jar cvf TZTester.jar tangentz/TZTester.class

It’s convenient to make such Makefile and put it in “yoru_working_dir”:

jar: class
        jar cvf TZTester.jar tangentz/TZTester.class
class:
        javac -classpath ContestApplet.jar tangentz/TZTester.java

The final step is just replacing your existing TZTester.jar by this new modified one.

My modification

I’ve pushed my TZTester.java code to my github repository.

plugin/modify_TZTester/build/tangentz/TZTester.java at master from cou929’s topcoder – GitHub

I’ve modified these two points.

• Add new lines to test cases. Append “\t” to argument of Code.appen() in generate_test_code(), generate_test_case() and generate_parameter()
• Append additional two test cases which contents are same to test case #0. Call generate_test_case() method two times more.

Other modifications

There are another modifications. Petr displays his TZTester:

Algorithm problems for dummies: Petr Mitrichev’s blog: Screencast and challenging

The TZTester.jar file itself is here. This is modified for C# code generation.

cafelier also shows his modification (in Japanese).

TZTester をどうにかする – cafelier@SRM – TopCoder部

The zipped file itself is here. He did a lot of changes such as put the test codes in global, measure processing time and so on.

SRM 405 div2 (practice)

Easy – FallingFactorialPower

For implementing quickly, consider conditions (k 0), and calculate the answer respectively using the for loop.

class FallingFactorialPower {
public:
  double compute(int n, int k) {
    double ret = 1;

    if (k < 0)
      for (int i=1; i<=abs(k); i++)
        ret /= (double)(n + i);
    else if (k > 0)
      for (int i=0; i<k; i++)
        ret *= (double)(n - i);

    return ret;
  }
};

Medium – RelativePath

Took a quick string processing-like approach. First of all, divide the two strings by “/” and store into two vectors. Check the vectors simultaneously to find an index that the first time two element of vectors are differ. Then append “../” to reach such index, and also append paths behind from such index.

class RelativePath {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  string makeRelative(string path, string currentDir) {
    string ret;

    vector <string> p = split(path, "/");
    vector <string> c = split(currentDir, "/");

    int i = 0, n = min(p.size(), c.size());
    for (i=0; i<n; i++)
      if (p[i] != c[i]) break;

    for (int j=0; j<c.size() - i; j++)
      ret += "../";
    for (int j=i; j<p.size(); j++)
      ret += p[j] + "/";

    ret.erase(ret.end()-1);

    return ret;
  }
};

SRM 431 div1 (practice)

Easy – LaserShooting

Calculate expected numbers for each obstacles, and then sum up these numbers. The way to calculate the expected number for the obstacle is that (the angle of laser to hit the obstacle) / (pi). In this problem the position (x, y) of obstacle is given, so we can calculate the angle using arc tangent.

class LaserShooting {
public:
  double numberOfHits(vector <int> x, vector <int> y1, vector <int> y2) {
    double ret = 0;

    for (int i=0; i<x.size(); i++) {
      double ang1 = atan((double)y1[i] / (double)x[i]);
      double ang2 = atan((double)y2[i] / (double)x[i]);
      ret += abs(ang1 - ang2) / M_PI;
    }

    return ret;
  }
};

SRM 433 div1 (practice)

Easy – MagicWords

According to “Constrains”, S contains up to 8 element and maximum length of each elements are 20. So there is 8! * 20 * 8 = 6451200 steps in the largest input case. This is seems that we can solve this problem simply searching all permutations. I’ve coded as such, but in the largest case (such as test case #6), it has took too long time, therefore introduced memorization using std::map. Then the code is optimized, passed system test.

class MagicWords {
public:
  map <string, int> memo;

  bool isMagic(string &str, int pos) {
    int len = str.size();
    for (int i=0; i<len; i++)
      if (str[i] != str[(i+pos)%len])
        return false;
    return true;
  }

  int count(vector <string> S, int K) {
    int ret = 0;
    vector <int> pos;
    for (int i=0; i<S.size(); i++) pos.push_back(i);

    do {
      string str;
      int magic = 0;
      for (int i=0; i<S.size(); i++) str += S[pos[i]];
      if (memo.find(str) != memo.end())
        magic = memo[str];
      else
        for (int i=0; i<str.size(); i++) if (isMagic(str, i)) magic++;
      memo[str] = magic;
      if (magic == K) ret++;
    } while (next_permutation(pos.begin(), pos.end()));

    return ret;
  }
};

SRM 435 div1 (practice)

Easy – CellRemoval

Easy problem. First of all, find leaf nodes from array ‘parent’. Leaf node is the node that no element refer it. And then traverse a tree from each leaf node to root node. During traversing, stop traverse if encounters ‘deletedCell’. If the leaf node can reach root node, count up return value.

The size of parent array is up to 50. This is very small tree. So you need not to implement memorization or other techniques. Number of nodes is small enough for execution time.

class CellRemoval {
public:
  int ret;
  vector <int> parent;
  int deletedCell;

  int r(int pos) {
    if (pos == -1) {
      ret++;
      return 0;
    } else if (pos == deletedCell) {
      return 0;
    }

    r(parent[pos]);
    return 0;
  }

  int cellsLeft(vector <int> _parent, int _deletedCell) {
    ret = 0;
    parent = _parent;
    deletedCell = _deletedCell;
    int leafs[parent.size()];
    memset(leafs, 0, sizeof(leafs));

    for (int i=0; i<parent.size(); i++)
      if (parent[i] != -1)
        leafs[parent[i]]++;

    for (int i=0; i<parent.size(); i++)
      if (leafs[i] == 0)
        r(i);

    return ret;
  }
};

SRM 436 div1 (practice)

Easy – BestView

Just search all skyscrapers. To determine skyscraper A is visible from skyscraper B, check all skyscrapers between A and B. So complexity is, at worst case, about 50 * (1 + 2 + … + 50), is equal to about 60,000. Completely no problem to search all skyscrapers.

class BestView {
public:
  int numberOfBuildings(vector <int> heights) {
    int ret = 0;

    for (int i=0; i<heights.size(); i++) {
      int counter = 0;
      for (int j=0; j<heights.size(); j++) if (i != j) {
          int left = min(i, j), right = max(i, j);
          double ratio = (double)(heights[left] - heights[right]) / (double)(left - right);
          bool visible = true;
          for (int k=left+1; k<right; k++)
            if (heights[k] >= heights[left] + ratio * (k - left)) {
              visible = false;
              break;
            }
          if (visible) counter++;
        }
      ret = max(ret, counter);
    }

    return ret;
  }
};

SRM 459 div1

Cannot attend this srm because I’ve overslept. Took a nap before srm but woken up after it started :( So first of all I’ve solved div1 easy in practice room.

Easy – Inequalities

Input is an array of “X (<= | | >=) C”. And C is an integer which range is [0, 1000]. So we need to check only [-0.5, 1000.5] by 0.5 interval. This is small enough for brute-force approach.

class Inequalities {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

  int maximumSubset(vector <string> inequalities) {
    int ret = 0;

    for (double i=-1; i<=1001; i+=0.5) {
      int satisfy = 0;
      for (int j=0; j<inequalities.size(); j++) {
        vector <string> res = split(inequalities[j], " ");
        double num = (double)toInt(res[2]);
        if (res[1] == "=") {
          if (i != num) continue;
        } else if (res[1] == "<") {
          if (i >= num) continue;
        } else if (res[1] == "<=") {
          if (i > num) continue;
        } else if (res[1] == ">") {
          if (i <= num) continue;
        } else if (res[1] == ">=") {
          if (i < num) continue;
        }
        satisfy++;
      }
      ret = max(ret, satisfy);
    }

    return ret;
  }
};

Member SRM 458 div1 (practice)

Medium – NewCoins

Solved with refering top submission by UdH-WiNGeR. This is a dp approach. An array dp[i] stores “number of coins which is needed when smallest coin value is equal to i”. Suppose i is a smallest coin value and j is a multiple i, number of coin needed is dp[j] + price % j / i. Calculate in this way from 10000 to 1.

class NewCoins {
public:
  int minCoins(vector <int> price) {
    int dp[100001];
    memset(dp, 0, sizeof(dp));

    for (int i=100000; i>=1; i--) {
      for (int j=0; j<price.size(); j++)
        dp[i] += price[j] / i;

      for (int j = i+i; j<=100000; j+=i) {
        int tmp = dp[j];
        for (int k=0; k<price.size(); k++)
          tmp += price[k] % j / i;
        dp[i] = min(dp[i], tmp);
      }
    }

    return dp[1];
  }
};

Member SRM 458 div1

Passed 250 point problem, cannot solve 500 point one, 1000 point was unopened. 367 place at div1, rating is now 1286 point from 1230 (+56).

Easy – BouncingBalls

A key point is all balls are moving constant speed. So collision and no collision are same meaning. Due to this condition, we can get this fact: Suppose that there are ball A and B, A’s position is smaller than B, and A moves to right and B moves to left. If the distance between A and B are less than or equal to 2T, these two balls will collide certainly, even if there are any balls between A and B.
Additionally the number of balls are up to 12, so the number of calculation we have to do is 2 ^ 12 = 4096. This is small enough to search all conditions.

class BouncingBalls {
public:
  double expectedBounces(vector <int> x, int T) {
    double ret = 0;
    sort(x.begin(), x.end());

    for (long long i=0; i<(1 << x.size()); i++) {
      long long tmp = i;
      for (int j=0; j<x.size(); j++)
        if ((tmp >> j) & 1)
          for (int k=j+1; k<x.size(); k++)
            if (!((tmp >> k) & 1))
              if ((double)(x[k] - x[j]) / 2.0 <= (double)T)
                ret++;
    }

    ret /= (1 << x.size());
    return ret;
  }
};

Medium – NewCoins

Cannot solve.

Hard – ModuloFourDivisor

Unopened.

SRM 440 div1 (practice)

Easy – IncredibleMachine

Make a equation which takes gravity acceleration ‘g’ and calculate time that a ball reaches the final vertex. Then search ‘g’ using this equation with binary search. To make this equation, it seems good enough that you can remember about basics of dynamics and quadratic formula.

class IncredibleMachine {
public:
  vector <vector <double> > planes;  // length, sin(alpha)
  double calcTimes(double g) {
    double ret = 0;
    double initial_velocity = 0;
    double acceleration = 0;
    double time = 0;

    for (int i=0; i<planes.size(); i++) {
      acceleration = g * planes[i][1];
      time = (-initial_velocity + sqrt(initial_velocity*initial_velocity + 2 * acceleration * planes[i][0])) / acceleration;
      initial_velocity = initial_velocity + acceleration * time;
      ret += time;
    }

    return ret;
  }

  double gravitationalAcceleration(vector <int> x, vector <int> y, int T) {
    double ret = 0;
    double left = 0, right = 1e20, mid = 0;
    planes.clear();

    for (int i=0; i<x.size()-1; i++) {
      vector <double> tmp(2, 0);
      tmp[0] = sqrt((x[i] - x[i+1]) * (x[i] - x[i+1]) + (y[i] - y[i+1]) * (y[i] - y[i+1]));
      tmp[1] = abs(y[i] - y[i+1]) / tmp[0];
      planes.push_back(tmp);
    }

    for (int i=0; i<1000; i++) {
      mid = (left + right) / 2;
      double t = calcTimes(mid);
      if (t < T)
        right = mid;
      else
        left = mid;
    }

    ret = mid;
    return ret;
  }
};