Home » questions » its a question frm google code jam .plz sb help me to solve it..?

its a question frm google code jam .plz sb help me to solve it..?

1
2006-07-30 22:40:19, Category: Programming & Design
Some students are sitting in a straight line giving an examination...The Students positon are given in an array.And the distance up to which a student can talk is also given.We have to find the minimum number of sets of questions required so that nobdy could cheat.... For eg . if a={ 1,2,3,4,5} and distance=1(each student can approach one bench ahead and one bench behind) then minimum of 2 sets are required..(give questions alternately) if a={0,4,5,6,7,12,13,14,16,17} and distance =5 Then minimum of 5 sets are required ... What would be the algorithm ??Can any body suggest sth here..

Answers

  1. Neil

    On 2006-07-30 23:52:26


    hehe.. nice question. if distance = n then make a span/window of 2n+1 centered on the middle slide the middle of that span over the array and see what is the maximum number of people who form part of teh whole span (say m) Therefore m-1 is the number of question papers you need to ensure that no one can cheat