taka_taka's blog

By taka_taka, 12 years ago, In English

In the previous contest I experimented with PHP and runned into Time Limit Exceeded.

I think My solution is normal. So I suppose that this problem cannot be solved with PHP under the time constraints (if you disagree, I want to see a solution.).

157C - Сообщение (110 (Div. 2), problem: (C) Message) Time limit exceeded on test 5

<?php

function solve(){

$Scanner = new Scanner("php://stdin");
$inp_s = $Scanner->Scan();
$inp_u = $Scanner->Scan();

$lu = strlen($inp_u);
for ($k = 0; $k < $lu; $k++) {
    $str .= "*";
}

$inp_s = $str. $inp_s. $str;
$ls = strlen($inp_s);

$max = 0;
for ($i = 0; $i < $ls; $i++) {
            $c = 0;
    for ($j = 0; $j < $lu; $j++) {
       if ($inp_u[$j] === $inp_s[$i + $j]) $c++;
    }
    if ($max < $c) $max = $c;
    if ($max === $lu) break;
}
$change = $lu - $max;
printf("%d", $change);

$Scanner->close();

}

function run(){

solve();

}

run();

======

definition of Scanner Class

======

?>

2012/3/2

Thank you for advices.

I tried two pattern.

1.in java → Accepted

In java, the time was more better.

2.in php, amending the number of roop, and the string.→ Accepted.

【what is amended】

a.for ($k = 0; $k < $lu; $k++) {$str .= "*";}

→for ($k = 0; $k < $lu — 1; $k++) {$str .= "*";}

b.for ($i = 0; $i < $ls; $i++) {

→for ($i = 0; $i < $ls- $lu + 1; $i++) {

c.added these(string to char array) $inp_s_arr = str_split($inp_s); $inp_u_arr = str_split($inp_u);

d.if ($inp_u[$j] === $inp_s[$i + $j]) $c++;

 →if ($inp_u_arr[$j] === $inp_s_arr[$i + $j]) $c++;  

【Result for amending】

1.a,b No.82 TLE

2.c,d No.55 TLE

3.a,b,c,d Accepted

(better) a,b,c,b > a,b > c,d > none (not better)

I think two things was important for solving TLE problem of my code.

1.The number of roop.

2.In php, directly accessing char of String(In java, str.charAt() ) is less faster than accessing char after string is changed to char array(in java, str.toCharArray() → c[i]) in case the size is big.

So I did a basic mistake.Sorry. But I understand the possibility that the code written by php will be not acceptted TLE, however the code written by java will be acceptted.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it