Competitions » Main CodeFu Competitons » CodeFu 2009 » Results

CodeFu 2009 Results

Final Round Results

vasja's solution for 500: RadarGrid, written in Java, submitted on 31.05.2009 14:07:37

import java.util.*;

public class RadarGrid {

   public  int chk(int []radars,int length)
{
int i,j,k,n;
int res=0;

n=radars.length;
for(i=0;i<n;i++)
{
if(i==0)
{if(radars[i]-0>res) res=radars[i];}
else
if(radars[i]-radars[i-1]>res) res=radars[i]-radars[i-1];

if(i==n-1)
{if(length-radars[i]>res) res=length-radars[i];}
else
if(radars[i+1]-radars[i]>res) res=radars[i+1]-radars[i];

}
return res;
} 


  public int minimalDistance(int length, int K, int[] radars) {

       int i,j,k,n;
int res=0;
int levo,desno;

Arrays.sort(radars);
n=radars.length;

int rast,rasti;
int lasti=-1;

res=chk(radars,length);


  for(i=1;i<=K;i++)
  {
  
   rast=0; rasti=0;
    for(j=0;j<n;j++)
    {
       if(j==lasti)continue;
      if(j==0) levo=radars[j];
      else levo=radars[j]-radars[j-1];
      
      if(j==n-1) desno=length-radars[j];
      else desno=radars[j+1]-radars[j];
      
      if(levo!=desno )
      {
        if(levo>rast) {rast=levo; rasti=j;}
        if(desno>rast){rast=desno; rasti=j;}
      }
    }
   lasti=rasti;
  if(rasti==0) levo=radars[rasti];
   else levo=radars[rasti]-radars[rasti-1];
   
  if(rasti==n-1) desno=length-radars[rasti];
      else desno=radars[rasti+1]-radars[rasti]; 
   
  if(levo!=desno)
  {
    if(levo>desno) radars[rasti]--;
    else radars[rasti]++;
  }
   if(chk(radars,length)<res)res=chk(radars,length);
  }



    return res;
  }
}

Test cases result

#	Test Case input	Expected	Received	Status
1.	12, 3, {2,6,8}	3	3	Correct
2.	12, 1, {2,6,8}	4	4	Correct
3.	10, 0, {0}	10	10	Correct
4.	10, 0, {10}	10	10	Correct
5.	10, 4, {0}	6	6	Correct
6.	10, 10, {0}	5	5	Correct
7.	57, 79, {40,22,28,14,49,9,15}	8	8	Correct
8.	99, 3, {48,11,53,41,94,47}	38	38	Correct
9.	34, 36, {28,17,31,13,30}	6	8	Wrong
10.	74, 209, {71,23,48,58,54,55,43,40,32,38, 16}	7	10	Wrong
11.	72, 863, {56,20,49,30,64,42,18,21,46,15, 5,4,63,18,30,11,22,51,64,32,72,51,66,16, 44,67,22,18,65,69,43,49,72,66,18,12,41}	2	3	Wrong
12.	25, 50, {21,14,22,16,7,13,1,25,14,7,6,12 ,2,1,22,6,8,13,3}	2	2	Correct
13.	23, 59, {1,20,21,23,9,10,14,18}	3	4	Wrong
14.	65, 848, {21,24,31,65,7,42,49,42,3,22,54 ,22,36,58,20,13,53,22,51,24,65,21,40,10, 19,20,60,22,32,41}	3	4	Wrong
15.	64, 427, {59,16,19,25,22,30,5,61,3,58,42 ,1,38,52,46,46,36,33,20,55,11,41,14,25,5 6,23,15,4,45,37,23,50,36}	2	3	Wrong
16.	24, 190, {14,13,10,2,16,18,3,3,9,2,14,23 ,21,11,22,22,9,24,17,2,1,24,17,24,20,21, 1,1,19,21,13,5,1,17,2,21,5,8,4,11,2,7,14 ,8}	1	1	Correct
17.	55, 96, {34,43,12,18,30}	10	10	Correct
18.	8, 44, {1,5,7,1,8,8,5,4,5,5,3,4,8,4,4,2, 4,5,8,8,8,3,2,7,2,3,3,7,5,6,2,1,2,8}	1	1	Correct
19.	8, 0, {7}	7	7	Correct
20.	93, 1245, {63,35,77,32,49,4,32,33,73,6,2 2,73,6,59,9,39,69,70,82,92,12,62,9,3,25, 24,63,47}	4	4	Correct
21.	29, 285, {15,10,24,22,18,4,27,9,3,7,18,2 4,11,10,13,27,27,21,3,4,18,20,17,5,12,16 ,19,16,6,22,28,7,4,13,10,6,20,13,21,18,1 7,15,2}	1	1	Correct
22.	86, 1230, {9,75,76,73,2,47,82,30,10,14,7 7,27,54,38,33,44,60,82,70,36,9,26,42,38, 60,28,60,49,50,85,11,9,22,83}	3	3	Correct
23.	30, 194, {8,2,17,1,27,24,20,1,28,7,9,3,2 1,27,6,18,2,21,30,15,20,11,11,9,25,19,27 ,26,18,1,30,24,24,26,18,12,19,25,11,1,15 ,14,20}	1	1	Correct
24.	88, 286, {79,14,31,55,42,73,22,11,55,59, 31,33,4,7,62,39,38,19,71}	5	5	Correct
25.	38, 253, {7,14,18,25,15,27,37,21,1,31,22 ,29,37,35,8,24,13,4,14,17,38,9,27,26,10, 12,4,20,26,35,30,18,7,15,38,22,32,19,29, 13,29,11,4,38,25}	1	1	Correct
26.	87, 935, {22,44,13,55,54,57,21,83,16,53, 52,16,7,39,59,47,9,21,83,22,70,46,9,47}	4	4	Correct
27.	35, 34, {17,25,23,1,7,16,34,29,30,28,29, 28,12,4,29,6,16,15,17,31,20,30,6,2,5,35, 22,12,2,24,20,35,10,25,23,10,35,2,24,24, 10,2,9,18,19,3,30}	1	1	Correct
28.	18, 274, {18,15,4,15,18,14,18,13,17,1,13 ,7,11,8,3,10,14,10,5,11,6,6,16,18,10,4,2 ,12,7,3,17,3,18,15,5}	1	1	Correct
29.	46, 170, {18,35,31,29,22,6,42,1,33,21,36 ,19,10,9,40,31,10,44,31,22,16,46,15,25,3 5,28,17,19,27,44,10,36,33,18,15,17,38,1, 43,9,15,23,4,29,17,41,10,41,1,16}	1	2	Wrong
30.	62, 314, {59,55,43,57,54,19,59,9,47,6,57 ,50,42,41,32,53,11,28,2,30,50,54,1,44,21 ,51,11,17,62,62,12,25,33,44,36,51,26,28, 24,28}	2	3	Wrong
31.	15, 36, {14,6,2,9,13,6,3,1,2,5,6,9,12,10 ,14,3,2,11,8,5,6,10,10,6,2,2,2,5,9,2,7,1 2,5,13,1,7,6,10,11,15,3,4,5,11,8}	1	1	Correct
32.	76, 489, {34,50,68,8,47,47,39,38,28,5,71 ,10,14,67,56,29,71,50,56,3,55,20,75,47,5 3,68,29,71,56,69,18,49,62,19,16,10,16,24 ,36,72,76,4,31,63,64}	2	3	Wrong
33.	67, 39, {65,4,15,23,24,33,37,24,12,19,18 }	9	9	Correct
34.	80, 27, {74,72,64,34,6,64,13,35,16,38,15 ,7,80,68,52,22,54,67,69,70}	6	7	Wrong
35.	80, 674, {79,72,24,12,75,77,47,49,25,61, 78,5,80,60,73,44,16,67,16,61,53,72,38,78 ,21,21,28,10,25,72,28,2,8,71,2,45,46,13, 4,45,27,53,19,48,72,66,41}	2	2	Correct
36.	43, 217, {36,6,16,29,15,3,15,17,10,10,42 ,12,15,39,42,14,37}	3	3	Correct
37.	92, 1491, {16,5,76,12,71,74,74,14,2,76,4 4,75,21,64,70,71,31,31,75,48,29,75,90,67 ,73,51,7,19,32,25,36,35,11,33,46,21,90,5 8,59,54}	3	3	Correct
38.	58, 71, {6,57,57,8,35,48,37,9,1,37,33,47 ,17,5,14}	4	5	Wrong
39.	62, 362, {23,3,28,8,7,46,35,38,24,34,46, 45,9,62,8,45}	4	4	Correct
40.	17, 142, {12,2,6,15,2,9,14,15,11,7,5,1,1 2,10,14,13,8,4,14,14,17}	1	1	Correct
41.	73, 180, {53,61,33,5,24,41,34,62,12,51,5 0,40,13,72,67,28,49,8,66,28,23,73,27,26, 60,55,64}	3	5	Wrong
42.	9, 95, {2,4,4,8,3,2,5,9,1,5,1,8,1,5,4,2, 9,7,3,9,8,1,3,8,8,5,1,4,6,7,5,5,4}	1	1	Correct
43.	100, 1365, {67,22,88,98,82,21,45,20,93,7 ,83,36,77,53,54,100,18,19,27,69,15,97,14 ,4,79,59,94,86,96,43,94,16,99,43,67,28,2 6,73,11,81,38,44}	3	4	Wrong
44.	20, 45, {2,7,2,17,15,9,13,5,6,15,8,8,5,1 9,20,11,15,3,11}	1	2	Wrong
45.	34, 4, {13,10}	17	19	Wrong
46.	12, 49, {11,8,2,2,3,6,1,10,5,11,9,12,7,6 ,4,7,2,1,3,9,7,8,3,2,8,5,4}	1	1	Correct
47.	53, 480, {16,41,30,3,46,1,47,42,23,50,13 ,11,3,26,23,6,51,52,50}	3	4	Wrong
48.	59, 655, {52,44,24,13,49,41,15,13,28,42, 7,40,39,5,22,43,24,55,2,24,36,20,20,39,5 7,35,33,59,43,47,5,40,53,15,2,57,47,34,1 6,4,20,1,19,16,28,20,3,18}	2	2	Correct
49.	87, 8, {46,73,3,41,35,82,20,71,43,70,13, 59,66,74,85,3,28,3,52,45,73,68,49,74,33, 84,39,30,10,51,68,87,44,30,17,16,14,32,4 ,71,36,76,53,51,53,85,56,30,41}	5	5	Correct
50.	46, 43, {45,37,18,46,21,10,18,28,28,42,2 ,26,11,2,24,13,9,38,2,31,37,8,38,9,43,46 }	2	3	Wrong
51.	93, 847, {38,74,36,81,8,53,93,80,26,52,3 4,88,81,78,66,81,18,78,84,24,92,74,92,34 ,12,69,48,74,73,28,82}	3	6	Wrong
52.	94, 93, {74,90,24,35,91,52,22,73,26,91,7 7,62,12,70,19,25,76,90,25,78,17,83,60,10 ,85,68}	5	5	Correct
53.	87, 130, {9,80,35,45,76,85,17,60,1,18,63 ,13,12,31}	6	7	Wrong
54.	79, 380, {54,12,15,13,60,35,77,4,47,32}	8	8	Correct
55.	25, 83, {23,7,6,24,25,5,7,14,3,13}	3	3	Correct
56.	92, 404, {60,30,92,7,87,66,2,18,48,68,72 ,83,92,26,41,87,84,36,11,66,31,63}	4	6	Wrong
57.	44, 51, {7,17,9,19,14,39}	7	7	Correct
58.	15, 306, {5,2,12,15,12,12,5,4,13,11,10,3 ,6,14,13,6,1,12,3,12,11,13,15,1,11,14,13 ,10,8,2,9,2,13,8,13,9,8,4,8,5,12,5,8,1}	1	1	Correct
59.	68, 91, {49,44,21,58,5,21,28,49,60}	7	9	Wrong
60.	8, 8, {2,6,5,4,3,7,2}	1	1	Correct
61.	24, 234, {18,11,10,3,6,8,21,20,23,21,14, 4,10,1,15,24,13,12,21,18}	2	2	Correct
62.	95, 786, {5,95,9,22,46,1,16,64,52,82,38, 42,87,22,17,8,42,92,56,81,39,83,75,23,32 ,72,63,23,56,91,40,49,47,77,78,57,93,12, 54,25,74,37,34,3,80,47}	3	3	Correct
63.	29, 32, {26,20,13,8,15}	5	5	Correct
64.	69, 868, {68,54,6,46,18,43,23,47,45,27,4 1,13,52,35,48,56,4,54,55,29,6,15,44,40,6 6,65,22,8,62,29,11,9,25,62,60,12,16,24,3 4,60,55}	2	2	Correct
65.	56, 731, {51,2,31,7,48,17,12,47,4,20,45, 38,13,37,29,34,34,48,34,32,55,24,5,43,42 ,9,38,38,42,40,51,26,4,54,52,56,17,19,39 }	2	2	Correct
66.	80, 319, {59,74,25,77,27,34,54,33,65,73, 68}	7	11	Wrong
67.	67, 21, {32,44,40,45,53,1,43,2,62,43,48, 45,63,40,24,66,36,31,1,8,38,9,66,26,60,6 0,7,60,47,59,14,44}	4	5	Wrong
68.	4, 29, {3,3,3,1,3,3,3,4,2,2,1,3,3,3,3,1, 2,3,2,2,1,4,2,4,1,3,3,4,2,4,4,2,1,4,3,1}	1	1	Correct
69.	20, 259, {16,12,1,3,10,5,9,17,16,12,17,1 0,2,18,17,15,3,8,8,1,3,1,20,16,10,14,20, 1,19,11,14,11,17,8,18,14,10,6,2,10,1,16, 18,14,6,18}	1	1	Correct
70.	39, 343, {27,28,26,31,27,11,32,30,13,7,3 7,26,27,33,3,22,26,3,2,5,14,15,38,8,26,2 4,36,6}	2	2	Correct
71.	21, 512, {21,16,14,10,3,8,8,5,5,21,14,10 ,9,5,13,7,21,7,4,7,13,19,8,12,1,16,9,9,3 ,12,13,11,11,6,7,1,5,1,10,11,9,20,19,5,1 5,5,17,1,10,18}	1	1	Correct
72.	80, 61, {47,8}	27	27	Correct
73.	54, 273, {23,15,54,1,52,13,27,15,9,25,44 ,35,23}	4	5	Wrong
74.	96, 289, {73,66,10,73,74,56,37,13,85,17, 91}	8	11	Wrong
75.	17, 148, {6,6,10,10,11,1,8,8,15,2,2,11,1 1,5,13,13,4,1,6,9}	1	1	Correct
76.	13, 84, {9,9,4,8,4,6,8,6,5,3,6,2,4,12,12 ,4,12,1,13,1,12,12,1,11,6,9,9,11}	1	1	Correct
77.	85, 865, {6,71,11,59,10,29,30,69,3,24,11 ,56,58,66,82,43,77,80,51,56,29,67,69,15, 64,51,84,36,41,72,48}	3	4	Wrong
78.	75, 1532, {69,25,30,25,13,34,48,24,14,12 ,60,11,29,51,7,36,52,22,10,23,18,18,72,4 5,25,25,60,69,72,14,15,20,67,56,33,55,15 ,28,13,61,53}	2	3	Wrong
79.	36, 164, {35,24,2,27,31,21,19,18,7,28,24 ,3,19,21,30,17,20,25,5,21,31,21,31,5,36, 6,14}	2	2	Correct
80.	85, 1085, {77,7,71,64,16,20,4,67,36,22,3 6,29,51,26,78,51,3,65,28,77,24,5,28,16,6 6,47,74,13,31,19,23,22,2,43}	3	3	Correct
81.	48, 294, {39,45,22,5,5,11,34,33,6,33,14, 25,14,8,9,16,38,43,22,1,13,17,8,14,25,23 ,41,36,27,41,42,12,17,29,37,17,5,45,30,9 }	2	2	Correct
82.	2, 12, {1,1,1,1,1,2,2,2,2,2,2,2,1}	1	1	Correct
83.	73, 33, {33}	37	37	Correct
84.	87, 793, {21,14,73,70,71,70,43,4,31,48,3 0,62,66,78,56,69,6,2,54,68,15,39,13,86}	4	5	Wrong
85.	64, 651, {45,30,62,44,8,23,25,17,25,27,2 1,61,12,37,41,36,55,47,39,22,8,48,16,59, 31,29,1,4,17,51,44,49,37,21,27,58,43,56, 6}	2	3	Wrong
86.	44, 105, {7,18,29,2,29}	8	8	Correct
87.	8, 32, {4,6,5,5,4,7,6,1,4,2,5,7,5,4,4,7, 7,3,6,8,1,6,7,5,2,2,4,4,1,7,5,6,8,8}	1	1	Correct
88.	7, 3, {7,2,7,2,4,4,4,7,7,5,7,1,3}	1	1	Correct
89.	72, 520, {18,3,68,67,16,2,59,22,49,38,54 ,70,37,7,36,26,21,10,24,14,15,20}	4	4	Correct
90.	75, 435, {37,27,10,67,41,1,9,28,34,24,63 ,43,34,68,12,17,50,34,40,41,33,14,57,58, 44,73,11,28,56,52,42,17}	3	3	Correct
91.	100, 243, {13,41,30,14,10,29}	15	15	Correct
92.	76, 1070, {24,38,61,50,7,71,68,43,67,57, 48,44,16,49,70,58,39,9,22,59,54,75,53,54 ,45,21,12,58,54,41,10,20,30,72,45,31,59, 30,76,5,35,6,69,4}	2	3	Wrong
93.	39, 17, {37}	20	20	Correct
94.	94, 205, {65,23,55,48,48,61,60,29}	11	12	Wrong
95.	63, 593, {38,6,47,14,14,30,7,1,22,63,33, 14,26,50,55,48,4,4,2,17,6,13,21,44,22,58 ,12,7,27,35,36,10,2,52,32,29,25,39,42,11 ,2}	2	2	Correct
96.	26, 478, {19,10,11,6,12,5,22,22,16,2,2,1 3,24,4,12,13,23,21,5,3,19,13,18,16,13,20 ,25,10,26,15,2,20,1,6,23,20,3,9,15,25,8, 7,7,14,1,25,23}	1	1	Correct
97.	18, 73, {7,11,7,5,17,7,16,16,12,9,2,10,6 ,15,14,18,8,7,1,4,7,10,4,6,1,17,10,16,10 ,11,8,13,14,2,3,15,5,9,13}	1	1	Correct
98.	17, 102, {14,11,7,13,8,4,11,13,13,1,2,16 ,13,8,14,6,7,13,12,7,3,7,4,11,4,16,3,7,4 ,16,8,11,5,15,4,8,6,15,5,10,6,6,15,1,16}	1	1	Correct
99.	30, 107, {26,9,9,17,23,30,4,29,13,21,24, 15}	3	3	Correct
100.	54, 196, {7,46,13,28,41,13,21,54,4,35,22 ,32,39,12,13,28,27,22,48,31,23,24,51,7,5 1,31,11,48,26,3}	2	2	Correct