JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums 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 : 12 Length : 33 Length : 94 Length : 335 Length : 1536 Length : 8737 Length : 59138 Length : 462339 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 : 12 Length : 33 Length : 94 Length : 335 Length : 1536 Length : 8737 Length : 59138 Length : 462339 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 : 12 Length : 33 Length : 94 Length : 335 Length : 1536 Length : 8737 Length : 59138 Length : 462339 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 found = new HashSet();   boolean more = true; while(more){ found.add(perm); more = false; for(i=1;!more && i