SRM 462 div1

Submitted 250 problem but challenged. The result was 0pt and rating was 1257. The rating slightly gained but I’m not satisfied the result. Also the result of the SRM had been 0pt in which recent 3 matches.

Easy – AgeEncoding

The algorithm for this problem is not so hard, this is just a problem for searching the solution with binary search. However, the most difficult point is consideration for corner cases. According to problem statement, we should return -1 if there is no solution and -2 if there are multiple solution. And it was very hard to notice all cases of such conditions. Many coders had been challenged or failed system test. It seems that almost of them hadn’t noticed the case whose input are, for instance, age = 1 and candlesLine = “11111″. In this case the correct answer is -1, not 0, since return value must be “strictly positive”.

class AgeEncoding {
public:
  double getRadix(int age, string candlesLine) {
    double ret = 0;
    int i, j;
    int n = candlesLine.size();
    int one_num = count(candlesLine.begin(), candlesLine.end(), '1');

    if (one_num == 0) return -1;
    if (candlesLine[n-1] == '1')
      if (age == 1)
        if (one_num == 1) return -2;
        else return -1;
      else
        if (one_num == 1) return -1;
    
    double left = 0, right = 100;
    for (i=0; i<1000; i++) {
      ret = (left + right) * 0.5;
      double ans = 0;
      double B = 1;

      for (j=n-1; j>=0; j--) {
        ans += (candlesLine[j] - '0') * B;
        B *= ret;
      }

      if (ans > age)
        right = ret;
      else
        left = ret;
    }

    return ret;
  }
};

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;
  }
};