Tuesday, December 2, 2008 Match summaryThe 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 600pointer 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 900pointer, took third place because of relatively slow 600pointer 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 ProblemsSimpleCardGameUsed as: Division One  Level One:
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:
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. TelltaleUsed as: Division One  Level Two:
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:
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. SoccerFanUsed as: Division One  Level Three:
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 ith // 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 ith match // t2  identifier of team2 in the ith match // res  the outcome of the ith 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; } }DecreasingNumbers Used as: Division One  Level Three:
First of all let's note that a onetoone correpondance between decreasing numbers and nonempty 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); } } 
