Temat: Codility - rozwiązania zadań - wyniki
Na zyczenie, Beta 2010, rozwiązanie na 100%, zlozonosc O(N).
Zeby bylo bardziej rozrywkowo, porozdzielalem odpowiedzialnosc na obiekty, wiec mozna sie wgryzac w kod stopniowo. Najwazniejszy trick to metoda countOverlapingDiscs , ktora uwzglednia 'kumulacje' i dzieki temu mamy zlozonosci liniowa. Tak na marginesie na to rozwiazanie w pare minut wpadla moja dziewczyna ktora nie ma pojecia o zlozonosci i programowaniu :D
function solution($A) {
$plane = new Plane(0, count($A) - 1);
$disc = new Disc($plane);
for ($discCentre = 0; $discCentre <= $plane->getMaxRightPointOnAxis(); $discCentre++) {
$discRadius = $A[$discCentre];
$plane->addDisc(Disc::configureAndGetDisk($disc, $discCentre, $discRadius));
}
return $plane->countOverlapingDiscs();
}
class Disc {
private $maxRightPointOnAxis;
private $minLeftPointOnAxis;
private $leftRange;
private $rightRange;
public function __construct(Plane $plane) {
$this->maxLeftPointOnAxis = $plane->getMaxLeftPointOnAxis();
$this->maxRightPointOnAxis = $plane->getMaxRightPointOnAxis();
}
public static function configureAndGetDisk($usedDisc, $centre, $radius) {
$usedDisc->leftRange = max($usedDisc->maxLeftPointOnAxis, $centre - $radius);
$usedDisc->rightRange = min($usedDisc->maxRightPointOnAxis, $centre + $radius);
return $usedDisc;
}
public function getLeftRange()
{
return $this->leftRange;
}
public function getRightRange()
{
return $this->rightRange;
}
}
class Plane {
private $maxRightPointOnAxis;
private $minLeftPointOnAxis;
private $discsBoundaries = array();
public function __construct($maxLeftPointOnAxis, $maxRightPointOnAxis) {
$this->maxLeftPointOnAxis = $maxLeftPointOnAxis;
$this->maxRightPointOnAxis = $maxRightPointOnAxis;
}
public function getMaxLeftPointOnAxis() {
return $this->maxLeftPointOnAxis;
}
public function getMaxRightPointOnAxis() {
return $this->maxRightPointOnAxis;
}
public function addDisc(Disc $disc) {
if (!isset($this->discsBoundaries[$disc->getLeftRange()])) {
$this->discsBoundaries[$disc->getLeftRange()] = array('L' => 0, 'R' => 0);
}
if (!isset($this->discsBoundaries[$disc->getRightRange()])) {
$this->discsBoundaries[$disc->getRightRange()] = array('L' => 0, 'R' => 0);
}
$this->discsBoundaries[$disc->getLeftRange()]['L']++;
$this->discsBoundaries[$disc->getRightRange()]['R']++;
}
public function getSequenceOfBoundaries() {
$boundariesSequence = array();
for ($position = $this->maxLeftPointOnAxis; $position <= $this->maxRightPointOnAxis; $position++) {
if(isset($this->discsBoundaries[$position])) {
$boundaries = $this->discsBoundaries[$position];
for($i = 0; $i < $boundaries['L']; $i++) {
$boundariesSequence[] = 'L';
}
for($i = 0; $i < $boundaries['R']; $i++) {
$boundariesSequence[] = 'R';
}
}
}
return $boundariesSequence;
}
public function countOverlapingDiscs() {
$sumOfOverlaps = 0;
$maxValue = 10000000;
$defaulValueWhenTooMuchOverlapings = -1;
$discsCumulation = 0;
foreach($this->getSequenceOfBoundaries() as $boundaryType) {
if ('L' === $boundaryType ) {
$sumOfOverlaps = $sumOfOverlaps + $discsCumulation;
if ($sumOfOverlaps > $maxValue) {
return $defaulValueWhenTooMuchOverlapings;
}
$discsCumulation++;
} else {
$discsCumulation--;
}
}
return $sumOfOverlaps;
}
}
пропозиції роботи
