taka_taka's blog

when using php(#110 (Div. 2), problem: (C) Message)
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.

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

Comments Comments (8)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

But, your solution is wrong, may be. My first attention was like that, but WA! After that, I fixed it.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not good at English. I want to solve this problem. If my solution is wrong, please tell me some points.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't see anything wrong with the solution. But a quick check of nested loops reveals that they are at least as slow as in Ruby (as I posted earlier). A simple nested loop (outer range = 0..3000, inner range = 0.1000; which is a possible scenario for this problem) takes 0.6 seconds without any additional commands and when you add commands you easily exceed the 2-second limit.

      So I suppose you are right, this problem can't be solved in PHP as well — at least not if the algorithms complexity is O(nm).

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      I am sorry, I didnot knew PHP good, and not sew that, you are add more * to first string. ))
      My first wrong solution like that, but without adding * to first string. Because, I thing your solution wrong, too.

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for ($i = 0; $i < $ls; $i++)
$i < $ls => $i < $ls — $lu + 1

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you.(I am not good at English ,so Sorry.) But I understand this problem, and before I wrote this blog , I submitted the code that was as your comment.

    In php, in case of outofindex, 1.notice is shown 2.return null(String(0) ""). so, in my code I think outofindex is all right. (For example, in Java, it will stop and error is shown) But exactly your comment is rigth.So thank you.

    → Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

There is solution for 26 * K * logK, where K is about 2^13. It uses Fast Fourier Transformation. But it is stupid, to use it here, and it has heavy constant factor, so maybe you are right, there we must to use more fast languages like C++ or Java. BTW, FFT can be replaced with Karatsuba multiplication, for such N and M it will be faster i think.

→ Reply