JOIN
 Match Editorials
TCHS SRM 47
Tuesday, December 4, 2007

## Match summary

130 students participated the match, 22 of them newcomers. They faced a set of problems somewhat brute-force solvable and not so tricky. Finally 7 people successfully solved all problems.

donalexey took the first place with a pretty high score in coding phase, thanks to his so fast 1000 solution. The second and third places were occupied by exod40 and Zuza, respectively. Challenge phase didn't play an important role in this match. They all took their places by scores in coding phase.

# The Problems

CardsShuffle
Used as: Division One - Level One:
 Value 250 Submission Rate 114 / 116 (98.28%) Success Rate 111 / 114 (97.37%) High Score Zuza for 249.07 points (1 mins 44 secs) Average Score 214.30 (for 111 correct submissions)

This was a straightforward problem. A simple string simulation will work. See donalexey's clear simulation solution.
In fact, the specified cards shuffle is just a circular left shift for the first last cards and nothing changes by a successive last times shuffles. So we can get a more efficient solution like below (Java code).

```public String shuffle(String cards,int first,int last,int times)
{
for(int i=0;i<(times%last);i++)
{
cards=cards.substring(first-1,end)+
cards.substring(0,first-1)+cards.substring(last);
}
return cards;
}
```

GraphClique
Used as: Division One - Level Two:
 Value 500 Submission Rate 70 / 116 (60.34%) Success Rate 57 / 70 (81.43%) High Score LittlePig for 493.82 points (3 mins 11 secs) Average Score 364.23 (for 57 correct submissions)

The writer posted this problem with maximum number of vertices in graph 22, and it was lowered down to 18 in final test. So many pure brute-force solutions passed system test in the contest.
Enumeration of all vertex subsets is necessary, so the tricky part is to check whether a subset is a clique. A O(N^2) inefficient brute-force check is avoidable. A simple dynamic programming method is sufficient. Say checking a nonempty subset S, we pick an arbitrary vertex v from S, and check whether a edge exists between v and every one of all other vertices in S and the subset S-{v} is a clique by memorized states. This leads to a O(N) check and O(N*2^N) solution.
Furthermore, using some bitwise tricky, it can be improved to O(2^N). Below is a Java solution.

```public int[] allClique(String[] graph)
{
final int n=graph.length;
int res[]=new int[n];
int edge[]=new int[1 << n];
boolean can[]=new boolean[1 << n];
int bcnt[]=new int[1 << n];
can[0]=true;bcnt[0]=0;
for(int i=0;i < n;i++)
{
int b=1 << i;
for(int j=0;j < n;j++)
if(graph[i].charAt(j)=='1')
b^=(1 << j);
edge[1 << i]=b;
}
for(int t=1;t < (1 << n);t++)
{
int low=(t^(t-1))&t;
bcnt[t]=1+bcnt[t^low];
can[t]=false;
if(can[t^low]&&(edge[low]&t)==t)
{
can[t]=true;
res[bcnt[t]-1]++;
}
}
return res;
}
```
Note that "low=(t^(t-1))&t" in the code is to get the lowest bit with 1 in t's binary representation.

RandomShuffle
Used as: Division One - Level Three:
 Value 1000 Submission Rate 13 / 116 (11.21%) Success Rate 7 / 13 (53.85%) High Score donalexey for 916.91 points (8 mins 42 secs) Average Score 594.02 (for 7 correct submissions)

At the first glance, one can easily come up with a simple recursive solution like this(Java code).

```int solve(int[] cur,int pos)
{
if(pos==cur.length)
{
for(int i=0;i < cur.length;i++)
if(cur[i]!=outputArray[i])
return 0;
return 1;
}
int res=0;
for(int i=0;i < cur.length;i++)
{
int tmp=cur[pos];
cur[pos]=cur[i];
cur[i]=tmp;
res+=solve(cur,pos+1);
tmp=cur[pos];
cur[pos]=cur[i];
cur[i]=tmp;
}
return res;
}
```
But unfortunately, it will run out of time when the length of outputArray is 10. How to improve it?
One observation is that it searches too many unnecessary states, because some states during search procedure have deviated the goal outputArray so much that it's impossible to yield the goal. So we can prune some search branches by some "heuristic". One of that is the number of mismatched positions, namely a number not lying in right position. Note that a swap operation can only put at most 2 numbers into right positions.
Say we encounter a state with m mismatched positions and w swaps remaining, if m>2*w, we needn't recursive down. This leads to a solution efficient enough to pass system test. Below is one of the problem testers ivan_metelsky's Java code.
```int N;
int cnt = 0;
int[] res, cur;
void solve(int pos, int cNeq)
{
if (cNeq > 2 * (N - pos)) return;
if (pos == N)
{
cnt++;
return;
}
solve(pos+1, cNeq);
for (int i=0; i < N; i++) if (i != pos)
{
int was = cNeq;
if (cur[pos] == res[pos]) cNeq++;
if (cur[i] == res[i]) cNeq++;
if (cur[pos] == res[i]) cNeq--;
if (cur[i] == res[pos]) cNeq--;
int tmp = cur[pos]; cur[pos] = cur[i]; cur[i] = tmp;
solve(pos+1, cNeq);
cNeq = was;
tmp = cur[pos]; cur[pos] = cur[i]; cur[i] = tmp;
}
}
public double probability(int[] outputArray)
{
N = outputArray.length;
cur = new int[N];
for (int i=0; i < N; i++) cur[i] = i+1;
res = outputArray;
int cNeq = 0;
for (int i=0; i < N; i++) if (cur[i] != res[i]) cNeq++;
solve(0, cNeq);
double ret = cnt;
for (int i=0; i < N; i++) ret /= 1.0*N;
return ret;
}
```
Note that the calculation of heuristic in this solution is optimized.
The writer's solution is somewhat complicated and uses a search technique called "meet in the middle". It ensures a predictable running time. Interested reader can see writer's code in practice room.

By stone
TopCoder Member