Match summary

By now, HS SRMs are well underway, with incredibly gifted high schoolers from around the world competing regularly, and HS SRM 20 was no exception. The easy and medium were pretty easy but, despite scaling down the input on the hard, it remained fairly difficult. Still, Loner, ahyangyi, SpaceFlyer, gopa_1999999, psir and wefgef successfully submitted all 3 problems, so hats off to them.

The Problems

Surname

Used as: Division One - Level One:

Value 250

Submission Rate 106 / 111 (95.50%)

Success Rate 102 / 106 (96.23%)

High Score msg555 for 249.35 points (1 mins 27 secs)

Average Score 233.40 (for 102 correct submissions)

This problem asks for the index of the surname with the highest score. The score of a surname is the ASCII value of all its characters summed. My code is below:

    private int getScore(String s)
    {
        int i = 0;
        int r = 0;
        for (i = 0; i < s.length(); i++)
            r += s.charAt(i);
        return r;
    }

    public int bestSurname(String surnames[])
    {
        int i = 0;
        int r = 0;
        for (i = 1; i < surnames.length; i++)
            if (getScore(surnames[r]) < getScore(surnames[i]))
                r = i;
        return r;
    }

Postnet

Used as: Division One - Level Two:

Value 500

Submission Rate 102 / 111 (91.89%)

Success Rate 84 / 102 (82.35%)

High Score msg555 for 486.65 points (4 mins 43 secs)

Average Score 392.98 (for 84 correct submissions)

Years ago I wrote code for highspeed barcode sort machines, and that was the inspiration for this problem. You are given a valid postal zip code of 5, 9 or 11 digits and asked to return its Postnet barcode. You must realize that each Postnet barcode begins and ends with a high bar and that each barcode has a checksum digit appended to the end of the zip code digits. The bars were given for the numbers [0, 9] so solving this problem was reduced to following the directions. My code is shown below:

    public String barcode(String zipCode)
    {
        int    index           = 0;
        int    sum             = 0;
	String barcodeDigits[] =
	{
            "HHLLL", "LLLHH", "LLHLH", "LLHHL", "LHLLH",
            "LHLHL", "LHHLL", "HLLLH", "HLLHL", "HLHLL"
	};
        String returnCode      = "H";

        for (index = 0; index < zipCode.length(); index++)
        {
            returnCode += barcodeDigits[zipCode.charAt(index) - '0'];
            sum        += zipCode.charAt(index) - '0';
        }
	
        returnCode += barcodeDigits[(10 - sum % 10)% 10];
        returnCode += "H";


        return returnCode;
    }

Touchdown

Used as: Division One - Level Three:

Value 1000

Submission Rate 42 / 111 (37.84%)

Success Rate 7 / 42 (16.67%)

High Score Loner for 684.02 points (21 mins 31 secs)

Average Score 575.73 (for 7 correct submissions)

This problem asked you to take on the role of a coach in the final minutes of an American football game in which you must make a touchdown to win the game. The key things to realize in this problem are that you must be able to move the football [yardsToGo, yardsToGo + 10] yards to make a touchdown; if this is not possible, it is not possible to make a touchdown. You also have to realize that you have a set of 4 downs, during which you must continue to get first downs where needed to keep the drive alive. Its easy to see that any number of plays that are 3 yards or more will continue to get 1st downs (a fresh set of 4 downs). The only thing that makes this problem difficult is when you must carefully select 1 and 2 yard plays in order to make a touchdown. Example: {4, 3, 2, 1, 1, 1, 2, 2, 3, 3, 4, 4, 3, 2, 4}, it is easy to see that to continue making 1st downs, one should choose subsets of these 4 plays {1, 2, 3, 4}.

I won't post my code because there were better shorter solutions to this problem, but I will provide an understanding of how I solved it. My solution used dynamic programming with a 7 dimensional array as follows: [yardsToGo + 11][maximumDowns + 1][numberOf1YardPlays + 1][numberOf2YardPlays + 1][numberOf3YardPlays + 1][numberOf4YardPlays + 1][2].

I then counted the total number of 1, 2, 3 and 4 yard plays. I sorted the list of plays in descending order and worked from biggest play to smallest. I worked from the maximum number of yards to 0 and added each play where others had left off; that is, the first time through, I simply added the first play to the table. When adding a play to the table, I also added every allowable combination of 1, 2, 3 and 4 yard plays to it. In hindsight, this approach seems kind of ugly, but it runs 20 plays in a 3rd of a second and I believe it could run 40 plays in under 2 seconds. To see a nice DP solution that uses recursion and memoization check out StevieT's solution below:

#define INF 1000000000
#define FILL(x,y) memset(&x,y,sizeof(x))
#define FORVECTOR(i,v) for (int i=0;i<(v).size();++i);
  
class Touchdown{
  public:
      int mem[1 << 15][4][11];
      int howMany(int yardsToGo, vector <int> plays)
      {
          FILL(mem,-1);
          int ret=rec(0,3,10,yardsToGo,plays);
          return ret >= INF ? -1 : ret;
      }
      int rec(int bm,int dns,int ytd,int ytg,const vector <int> &plays)
      {
          if (ytg<-10) return INF;
          if (ytg<=0) return 0;
          if (ytd<=0) {dns=3;ytd=10;}
          if (dns<0) return INF;
          if (mem[bm][dns][ytd]>-1) return mem[bm][dns][ytd];
          int ret=INF;
          FORVECTOR(i,plays)
              if (!(bm & (1<<i))
            {
                ret<?=1+rec(bm | (1 << i),dns-1,ytd-plays[i],ytg-plays[i],plays);
              }
          return mem[bm][dns][ytd]=ret;
      }
};

By Uranium-235
TopCoder Member