JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Algorithm Discussions General Algorithm Discussions Re: Turkish Informatics Olympiad problem Revision History (2 edits)
Re: Turkish Informatics Olympiad problem (response to post by rlblaster)
A bit promising to see similar result :)) Any proof why the greedy works ? (if it works :P) Here's the lengths found by my greedy algorithms:
1 Length : 1
2 Length : 3
3 Length : 9
4 Length : 33
5 Length : 153
6 Length : 873
7 Length : 5913
8 Length : 46233
9 Length : 409113
Code on edit: has a bug, not in determining the order, but on combining the result.
res.append(perm.substring(0,i-1));
Should have been :
res.append(next.substring(N-i+1));
Re: Turkish Informatics Olympiad problem (response to post by rlblaster)
A bit promising to see similar result :)) Any proof why the greedy works ? (if it works :P) Here's the lengths found by my greedy algorithms:
1 Length : 1
2 Length : 3
3 Length : 9
4 Length : 33
5 Length : 153
6 Length : 873
7 Length : 5913
8 Length : 46233
9 Length : 409113
Code on edit
Re: Turkish Informatics Olympiad problem (response to post by rlblaster)
A bit promising to see similar result :)) Any proof why the greedy works ? (if it works :P) Here's the lengths found by my greedy algorithms:
1 Length : 1
2 Length : 3
3 Length : 9
4 Length : 33
5 Length : 153
6 Length : 873
7 Length : 5913
8 Length : 46233
9 Length : 409113

import java.util.*;
public class Coba {
 
	static String roll(String x, int start){
		char [] last = x.substring(0,start).toCharArray(); 
		Arrays.sort(last);
		return x.substring(start) + new String(last);
	}
 
	public static void main(String [] args){
		int N = 4;
		if(args.length == 1) N = new Integer(args[0]);
 
		String perm = "";
		for(int i=1;i<=N;i++) perm += i;
 
		int i=0;
		String next="";
		StringBuffer res = new StringBuffer(perm);
		HashSet<String> found = new HashSet<String>();
 
		boolean more = true;
		while(more){
			found.add(perm);
			more = false;
			for(i=1;!more && i<N;i++){
				next = roll(perm,i);
				more = !found.contains(next);
			}
			if(more) {
				res.append(perm.substring(0,i-1));
				perm = next; 
			}
		}
 
		System.out.println(res);
		System.out.println("Length : " + res.length());
	}
}