Register
|
Login
Home
News
Competitions
Practice
How to
Rankings
Calendar
Arena
CodeFu 2007
CodeFu'07 Highlights
Jazoon'07 Highlights
Schedule
Rules
Prizes
Results
Competitions
»
Main CodeFu Competitons
»
CodeFu 2007
»
Results
CodeFu 2007 Results
CodeFu Final Round Results
aleksovski's solution for 200: Consecutive Numbers, written in Java
import java.util.LinkedList; public class ConsecutiveNumbers { LinkedList<My> grupi = new LinkedList<My>(); int [] num = new int[1000002]; public int longestSequence(int[] numbers) { for (int i=0;i<numbers.length;i++) num[ numbers[i] ]=1; int s=-1; for (int i=1;i<1000002;i++) { if (s==-1) { if (num[i]>0) { s=i; } else { } } else { // s != -1 if (num[i]==0) { grupi.add(new My(s,i-1)); System.out.println("dodav gr"+ s+ " " + (i-1)); s=-1; } else { } } } return greedy(); } private int greedy() { int num0 = num[0]; int maxg=-1; int max = 0; for (int i=0;i<grupi.size();i++) { My t = grupi.get(i); if (maxg < t.end-t.start+1) { maxg = t.end-t.start+1; max = i; } } int leftIndex = max , rightIndex=max, distLeft=0, distRight=0; int res=maxg; while (num0>0) { int sizeLeft=0, sizeRight=0; My tLeft1 = grupi.get(leftIndex); My tRight1 = grupi.get(rightIndex); My tLeft = null; My tRight= null; if (leftIndex>0) { tLeft = grupi.get(leftIndex-1); sizeLeft = tLeft.end-tLeft.start+1; distLeft = tLeft1.start - tLeft.end -1; } if (rightIndex < grupi.size()-1 ) { tRight = grupi.get(rightIndex+1); sizeRight = tRight.end-tRight.start+1; distRight = tRight.start - tRight1.end -1; } if (sizeLeft+sizeRight==0) return (res + num0); if (num0 > distLeft + distRight) { leftIndex--; rightIndex++; res += tLeft.end-tLeft.start+1; num0-=distLeft; res += tRight.end-tRight.start+1; num0-=distRight; } else if ((sizeLeft>0) && (sizeRight>0) && (num0 >= distLeft) && (num0 >= distRight)) { // i dvete moze if (sizeLeft>sizeRight) { leftIndex--; res += tLeft.end-tLeft.start+1 + distLeft; num0-=distLeft; } else { rightIndex++; res += tRight.end-tRight.start+1 + distRight; num0-=distRight; } } else if ((sizeLeft>0) && (num0 >=distLeft)) { // samo levbo leftIndex--; res += tLeft.end-tLeft.start+1+distLeft; num0-=distLeft; } else if ((sizeRight>0) && (num0 >=distRight)) { // samo desno rightIndex++; res += tRight.end-tRight.start+1+ distRight; num0-=distRight; } else { return res + num0; } } return res; } } class My { int start; int end; public My(int start, int end) { this.start=start; this.end=end; } }