Match Editorials

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

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;
}

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;
}

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;
}

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;
}