Technocup 2017 - Elimination Round 2 C. Road to Cinema

Problem

There are N cars, each car's price is C[i] and its fuel tank capacity is V[i]. The road length is S. There are K stations on the road. We must pass the road in T minutes.

Fuel is free.
Car can drive in two mode: (1) cover 1 kilometer in 2 minutes, and consumes 1 liter of fuel. (2) covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel.

Find the lowest price car to pass the road.

Solution

For each car, we can use O(N) algorithm to check whether it can get the destination in T minutes. Here is the greedy idea:

Let the distance of two stations is LEN.

If the car's fuel capacity is more than 2 * LEN then it can pass the road between these two stations in LEN minutes. (which is minimum)
Otherwise, let X is the distance the car runs in first mode. let Y is the distance the car runs in second mode. Then we have: X + Y = LEN; X + 2 * Y = V[i]. Note V[i] must be more than LEN otherwise it can not pass. Then the time it uses is: 2 * X + Y = 3 * LEN - V[i].

If we loop each to check whether it can pass and maintain the lowest price. The algorithm is O(N²) which is about 10¹⁰. We notice that if V[i] can pass the road, then V[j] > V[i] can also pass. So we can sort the cars by the fuel tank capacity. And we can use binary search to search the car with the smallest fuel tank capacity which can pass the road. Let that car's index is INDICE. Then for each car in [INDICE..N-1] we can get the lowest price. In this way, we get O(NLogN) + O(N).

This is Perl solution. It got TLE on the 9th test case, maybe because of slow Input and Output. Nobody Got AC in Python either. :-(

#!perl
#use strict;
#use warnings;
use v5.20;
use Class::Struct;
struct (Car => [c => '$', v => '$']);
my ($n, $k, $s, $t);
my @interval;
while (<>) {
    ($n, $k, $s, $t) = split;
    my ($c, $v, $i, $j, @cars);
    for $i ( 0..$n-1 ) {
        ($c, $v) = split ' ', <>;
        $cars[$i] = Car->new(c => $c, v => $v);
    }
    @cars = sort { $a->v <=> $b->v } @cars;

    my @kk = split ' ', <>;
    unshift @kk, 0;
    @kk = sort { $a <=> $b } @kk;
    for $i ( 1..$#kk ) { $interval[$i-1] = $kk[$i] - $kk[$i-1]; }
    push @interval, $s - $kk[-1];

    my $result = -1;
    my ($left, $right, $mid);
    $left = -1; $right = $#cars;
    while ($right - $left > 1) {
        $mid = int($left + ($right - $left) / 2);
        if (check($cars[$mid])) { $right = $mid; }
        else { $left = $mid; }
    }
    if (check($cars[$right])) {
        my @true_cars = @cars[$right..$#cars];
        @true_cars = sort { $a->c <=> $b->c } @true_cars;
        say $true_cars[0]->c;
    }
    else { say -1; }
}

sub check {
    my $ref = shift;
    my ($i, $j);
    $i = $ref->v;
    my $t1 = 0;

    for $j ( @interval ) {
        if ($j * 2 <= $i) { $t1 += $j; }
        else {
            if ($j <= $i) { $t1 += 3 * $j - $i; }
            else { $t1 = $t + 10; } # make it larger to break loop
        }
        last if ($t1 > $t);
    }
    return $t1 <= $t ? 1 : 0;
}

This is C++ solution. Got AC.

//
//  main.cpp
//  C. Road to Cinema
//
//  Created by liu on 16/11/22.
//  Copyright © 2016年 liu. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Car {
    int c, v;
};
int n, k, s, t;
const int N = 2 * 100000 + 10;

int kk[N], interval[N];
Car cars[N];

bool comp (Car &a, Car &b) {
    return a.v < b.v;
}
bool check (Car &a) {
    int v = a.v, t1 = 0;
    for (int j = 0; j <= k; ++j) {
        if (interval[j] * 2 <= v) t1 += interval[j];
        else {
            if (interval[j] <= v) t1 += 3 * interval[j] - v;
            else t1 = t + 10; // make it larger to break loop.
        }
        if (t1 > t) break;
    }
    return t1 > t ? false : true;
}

int main(int argc, const char * argv[]) {
    while (~scanf("%d%d%d%d", &n, &k, &s, &t)) {
        int c, v;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &c, &v);
            cars[i].c = c;
            cars[i].v = v;
        }
        kk[0] = 0;
        for (int i = 1; i <= k; ++i){
            scanf("%d", &kk[i]);
            interval[i-1] = kk[i] - kk[i-1];
        }
        sort(kk, kk + k + 1);
        
        for (int i = 1; i <= k; ++i){
            interval[i-1] = kk[i] - kk[i-1];
        }
        interval[k] = s - kk[k];
        
        sort(cars, cars + n, comp);
        int left = -1, right = n - 1, mid;
        while (right - left > 1) {
            mid = left + (right - left) / 2;
            if (check(cars[mid])) right = mid;
            else left = mid;
        }
//        printf("interval: ");
//        for (int i = 0; i <= k; ++i) printf("%d ", interval[i]);
//        printf("\nright = %d\n", right);
//        for (int i = 0; i < n; ++i) {
//            printf("(%d %d)\n", cars[i].c, cars[i].v);
//        }
//        printf("------\n");
        if (check(cars[right])) {
            int result = INT_MAX;
            for (int i = right; i < n; ++i) {
                result = min(result, cars[i].c);
            }
            printf("%d\n", result);
        }
        else printf("-1\n");
    }
    
    return 0;
}