Match Editorials

Match summary

The last but one High School SRM in Season 3 attracted 96 competitors and featured 3 problems of moderate difficulty. Despite the lack of significant algorithm competitions experience (it was his only second HS match), meret won the round with solid 1600.78 points. All his 3 submissions were very fast with 600-pointer submission being the fastest overall. anastasov.bg had very close submission times to meret on easy and hard, but lost about 40 points on medium problem. He won 25 points back during the challenge phase, but that was not enough, so he placed second. DaViDeX, author of the fastest submission on 900-pointer, took third place because of relatively slow 600-pointer and lack of challenges. The rest of competitors were significantly behind the Top 3 (the difference between 3rd and 4th places is more than 100 points). Still, many other participants showed very good perfomance with 23 people scoring more than 1000.

The Problems

Value	250
Submission Rate	92 / 96 (95.83%)
Success Rate	80 / 92 (86.96%)
High Score	Tavo92 for 248.75 points (2 mins 1 secs)
Average Score	228.32 (for 80 correct submissions)

This problem asked to determine the winner in a round of Blackjack game. Since the round has actually ended and the points are known for each player, getting the winner is not hard at all. The problem statement gives us 2 rules that must be followed. Using them, one can come with the following algorithm to solve the problem:

1. Determine if there is at least one player with 21 or fewer points. If there are none, return -1 (there is no winner).
2. Find the maximum number of points M scored by players who has 21 or fewer points.
3. Find the number C of players who scored exactly M points. If C is greater than 1, return -1 (many winners).
4. Return the index of the only one player who scored M points.

Below is a Java implementation that follows exactly these 4 simple steps:

public class SimpleCardGame {

  public int whoIsTheWinner(int[] points) {

    // step 1

    boolean have = false;

    for (int i=0; i < points.length; i++)

      if (points[i] <= 21)

        have = true;

    if (!have) return -1;



    // step 2

    int M = 0;

    for (int i=0; i < points.length; i++)

      if (points[i] <= 21 && points[i] > M)

        M = points[i];



    // step 3

    int C = 0;

      for (int i=0; i < points.length; i++)

        if (points[i] == M)

          C++;

    if (C > 1) return -1;



    // step 4

    for (int i=0; i < points.length; i++)

      if (points[i] == M)

        return i;



    // this line is never executed

    return -2;

  }

}

Of course, the provided implementation is far from being short. Look at the fastest submission on this problem by Tavo92 for an example of short and clean implementation.

Value	600
Submission Rate	74 / 96 (77.08%)
Success Rate	48 / 74 (64.86%)
High Score	meret for 577.30 points (5 mins 40 secs)
Average Score	398.62 (for 48 correct submissions)

Your friend wants to tell a cool sounding exaggerated variant of a story at many parties and at the same time he doesn't want to be caught as a liar. To help him, we first assume that he tells the exaggerated variant everywhere, and than exclude all situations when he can be caught as a liar. There are two kinds of such situations:

1. When somebody already knows the true variant of the story and hears the exaggerated variant at some party, he can tell that your friend is a liar. So, for all parties where at least one such person is present, we exclude these parties from those where the exaggerated variant can be told.
2. If somebody hears different variants of the story at different parties, he can also justify that your friend is a liar. To prevent this, we iterate through all pairs of parties A and B. If there is at least one person that visits both parties and we already know that true variant of the story must be told at party A, then party B must also be excluded from those where the exaggerated variant can be told.

We've prevented both kinds of situations where the friend can be caught as a liar, so we're done, right? Actually, not. When we applied step 2, we've possibly deduced that true variant of the story must be told instead of exaggerated one at some parties. Therefore, it's possible that more people are now able to hear the true variant at some party, and some of these people may be able to detect the lie at other parties. Consider an example n=4, a={0}, parties={"2 3", "0 1", "1 2"}. First, we deduce that the friend should tell the true variant at party 1, because person 0 is present there and she knows the true variant. Than, person 1 is present at both parties 1 and 2. Since he tells the true variant at party 1, he must tell it at party 2 as well. But this is not enough to prevent the friend from being detected. Now person 2 knows the true variant. She is present at parties 0 and 2, so she's able to catch the friend.

So, one application of step 2 is not enough to solve the problem. However, the fix is easy - we must apply this step several times, until there are no more changes in the list of parties where the true variant of the story must be told. Alternatively, we can repeat step 2 exactly m times, where m is the number of parties. Since at each repeat we deduce that true variant of the story must be told at least at some party and the number of such deducements is bounded by the number of parties, m repeats is always enough.

Java implementation of this approach is given below:

public class Telltale {

  public int doNotTellTheTruth(int n, int[] a, String[] parties) {

    int m = parties.length;



    // parse parties to determine which people attend each party

    boolean[][] visit = new boolean[m][n];

    for (int i=0; i<m; i++) {

      String[] toks = parties[i].split(" ");

      for (int j=0; j<toks.length; j++)

        visit[i][Integer.parseInt(toks[j])-1] = true;

    }



    // apply step 1

    boolean[] tellTrue = new boolean[m];

    for (int i=0; i<m; i++)

      for (int j=0; j<n; j++)

        for (int k=0; k<a.length; k++)

          if (a[k]-1==j && visit[i][j])

            tellTrue[i] = true;



    // apply m times step 2

    for (int x=0; x<m; x++)

      for (int i=0; i<m; i++)

        for (int j=0; j<m; j++)

          for (int k=0; k<n; k++)

            if (tellTrue[i] && visit[i][k] && visit[j][k])

              tellTrue[j] = true;



    // calculate and return result

    int res = 0;

    for (int i=0; i<m; i++)

      if (!tellTrue[i]) res++;

    return res;

  }

}

There is also an approach to this problem that uses graphs. We can build a graph where each vertex corresponds to a party. Two parties that share at least one person are connected by an edge, which means that at both parties we must tell the same variant of the story. In each connected component of this graph the same variant of the story should be told. If at least one party in a component is visited by a person who already knows the true variant, we must tell the true variant, otherwise the exaggerated one can be told everywhere in the component. To get the connected components, DFS or BFS traversal can be used.

Value	900
Submission Rate	33 / 96 (34.38%)
Success Rate	24 / 33 (72.73%)
High Score	DaViDeX for 781.73 points (11 mins 24 secs)
Average Score	567.09 (for 24 correct submissions)

This problem is mostly implementational, because getting the solution idea is not hard. Note that by changing the number of goals scored by one team we can change match result to absolutely any other result (to get the victory of one team under another, set the number of goals for this team to sufficiently large value; to get draw set one team's number of goals equal to the number of goals scored by the other team). So the problem can be solved using the following pseudocode:

If team winner is the winner according to results

  Return -2



For each match M (in increasing order of index)

  For each possible outcome O in {victory, draw, defeat}

    Let team T is the winner according to

      results where the outcome of match M is changed to O

    If T = winner

      Return the index of M



Return -1

What's left is to transform this pseudocode into the code in real programming language. In Java it can be done as follows:

import java.util.*;



public class SoccerFan {

  // maps team name to integer team identifier

  Map teams = new HashMap();



  // PNT[i][j] is the number of points scored by i-th

  // team in case of outcome j out of {win, draw, defeat}

  int[][] PNT = new int[][] {{3, 1, 0}, {0, 1, 3}};



  // t1 - identifier of team1 in the i-th match

  // t2 - identifier of team2 in the i-th match

  // res - the outcome of the i-th match

  int[] t1, t2, res;



  // team identifier for winner

  int winId;



  // returns the identifier for the given team

  // (if necessary, inserts the team into teams

  int getId(String team) {

    if (teams.containsKey(team)) return teams.get(team);

    teams.put(team, teams.size());

    return teams.get(team);

  }



  // checks if winner is the winner according to

  // the data in t1, t2 and res

  boolean check() {

    // calculate the number of points for each team

    int[] pnt = new int[teams.size()];

    for (int i=0; i<t1.length; i++) {

      pnt[t1[i]] += PNT[0][res[i]];

      pnt[t2[i]] += PNT[1][res[i]];

    }



    // find if there's a team that scored

    // at least as much as team winId

    for (int i=0; i<teams.size(); i++)

      if (i != winId && pnt[i] >= pnt[winId])

        return false;



    return true;

  }



  public int whereIsMistake(String[] results, String winner) {

    // initialize t1, t2 and res

    t1 = new int[results.length];

    t2 = new int[results.length];

    res = new int[results.length];



    // parse results into t1, t2 and res

    for (int i=0; i<results.length; i++) {

      StringTokenizer st = new StringTokenizer(results[i], " :");

      t1[i] = getId(st.nextToken());

      t2[i] = getId(st.nextToken());

      int a = Integer.parseInt(st.nextToken());

      int b = Integer.parseInt(st.nextToken());

      if (a>b) res[i] = 0;

      if (a==b) res[i] = 1;

      if (a<b) res[i] = 2;

    }



    // find the team identifier for winner

    winId = getId(winner);



    // check if winner is the winner according to results

    if (check()) return -2;



    // for each match

    for (int i=0; i<t1.length; i++) {

      // remember the real outcome of the match

      int was = res[i];

      // for each possible outcome of the match

      for (res[i]=0; res[i]<3; res[i]++)

        // check if it allows team winner to become the winner

        if (check()) return i;

      // restore the real outcome

      res[i] = was;

    }



    return -1;

  }

}

Value	1000
Submission Rate	68 / 125 (54.40%)
Success Rate	42 / 68 (61.76%)
High Score	niyaznigmatul for 988.30 points (3 mins 6 secs)
Average Score	625.95 (for 42 correct submissions)

First of all let's note that a one-to-one correpondance between decreasing numbers and non-empty subsets of set of digits {0..9} exists. All digits in a decreasing number are different (so they form a subset) and exactly one decreasing number can be formed from each subset (you need arrange elements of it in a decreasing order). So there exists only 2^10 - 1 = 1023 decreasing numbers. They can be easily generated. After it one need to sort them increasingly and return the answer for the problem.

Java implementation of this approach can look as follows.

public class DecreasingNumbers {
	ArrayList<Long> list; 
	void go(int pos, String s) {
		if (pos == -1) {
			if (s.length() > 0) {
				list.add(Long.parseLong(s));
			}
			return;
		}
		go(pos - 1, s + pos);
		go(pos - 1, s);
	}
	public long getNth(int n) {
		list = new ArrayList<Long>();
		go(9, "");
		Collections.sort(list);
		if (n >= list.size()) {
			return -1;
		}
		return list.get(n);
	}	
}