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. The ProblemsCardsShuffleUsed as: Division One - Level One:
This was a straightforward problem. A simple string simulation will work. See donalexey's clear simulation solution. 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:
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. 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:
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.
|
|