JOIN
 Match Editorials
TCHS SRM 63
Tuesday, December 2, 2008

## 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

SimpleCardGame
Used as: Division One - Level One:
 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.

Telltale
Used as: Division One - Level Two:
 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.

SoccerFan
Used as: Division One - Level Three:
 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;

}

}

```

DecreasingNumbers
Used as: Division One - Level Three:
 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) {
}
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);
}
}
```

By ivan_metelsky
TopCoder Member