Create a gist now

Instantly share code, notes, and snippets.

use strict;
use warnings;
# find the most greater value in range of less or equal to given target.
# returns the index of that value.
# array must be ascend sorted.
sub idx_of_max_in {
my ( $array, $head, $tail, $target ) = @_;
return $tail if $array->[$tail] <= $target;
return $head if $array->[$head] == $target;
while ( $head <= $tail ) {
my $where = int( ( $head + $tail ) / 2 );
if ( $array->[$where] == $target ) {
return $where;
}
elsif ( $target < $array->[$where] ) {
$tail = $where - 1;
}
else {
$head = $where + 1;
}
}
return $head - 1;
}
my @lines = split "\n", do { local $/; <> };
my ( $num_prices, undef ) = split( " ", shift(@lines) );
my @prices = splice ( @lines, 0, $num_prices );
sub array_based {
@prices = sort { $a <=> $b } @prices;
my $price_max_idx = $num_prices - 1;
my $min_price = $prices[0];
my $min_pair_price = $prices[0] + $prices[1];
my $binsearch_limit = $prices[0] + $prices[-1];
my @results;
DAY: for my $target (@lines) {
$target = int($target);
# short cut for exceptional situation
if ( $min_pair_price > $target ) {
push @results, 0;
next DAY;
}
# find most expensive price in which cheeper than target price
# with using binary search
my ( $head, $tail ) = ( 0, $price_max_idx );
if ( $target < $binsearch_limit ) {
$tail = idx_of_max_in( \@prices, $head, $tail, $target - $min_price );
}
my $best = 0;
PRODUCT: while (1) {
my $tail_val = $prices[$tail];
my $head_target = $target - $tail_val;
my ( $head_val, $head_next_val ) = ( $prices[$head], $prices[$head+1] );
while ( $head_next_val <= $head_target && $head < $tail ) {
( $head_val, $head_next_val ) = ( $head_next_val, $prices[++$head] );
}
my $val = $head_val + $tail_val;
if ( $best < $val && $val <= $target ) {
$best = $val;
last PRODUCT if $best == $target;
}
$tail--;
last PRODUCT unless $head < $tail;
}
push @results, $best;
}
my $res = join( "\n", @results );
print $res, "\n";
}
sub hist_based {
my @hist;
$hist[$_]++ for @prices;
my @low_ends;
for ( 0..500 ) {
push @low_ends, $_ if $hist[$_];
}
my @results;
DAY: for my $target ( @lines ) {
my $tail = $target;
my $best = 0;
my $low_head = 0;
PRODUCT: while (1) {
do { $tail-- } while !$hist[$tail] && $tail;
last PRODUCT unless $tail;
my $head_target = $target - $tail;
last PRODUCT if $tail < $head_target;
next PRODUCT if $head_target == $tail && $hist[$tail] < 2;
if ( $head_target < $low_ends[-2] ) {
$low_head++ while $low_ends[$low_head + 1] <= $head_target;
my $head = $low_ends[$low_head];
if ( $best < $head + $tail && $head + $tail <= $target) {
$best = $head + $tail;
last PRODUCT if $best == $target;
}
}
else {
my $head = $head_target;
$head-- while !$hist[$head] && $head;
next PRODUCT unless $head;
if ( $head + $tail > $target ) {
next PRODUCT;
}
if ( $best < $head + $tail ) {
$best = $head + $tail;
last PRODUCT if $best == $target;
}
}
}
push @results, $best;
}
my $res = join( "\n", @results );
print $res, "\n";
}
$num_prices > 10000 ? hist_based() : array_based();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment