### taka_taka's blog

By taka_taka21 month(s) ago, ,

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

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.

•
• +2
•

 » 21 month(s) ago, # |   0 But, your solution is wrong, may be. My first attention was like that, but WA! After that, I fixed it.
•
 » » 21 month(s) ago, # ^ |   0 I am not good at English. I want to solve this problem. If my solution is wrong, please tell me some points.
•
 » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 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).
•
 » » » » 21 month(s) ago, # ^ |   0 Thank you.About Ruby, I read your blog. YOur commets are very helpful. 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 additionalif the algorithms complexity is O(nm) I understand these points. And I suppose that your commend is right.Thank you very much.
•
 » » » 21 month(s) ago, # ^ | ← Rev. 5 →   0 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.
•
 » » » » 21 month(s) ago, # ^ |   0 Thank you. Your comment is right. I tried to decrease * . But the number of roop was more importantor. I decreased the number of roop. (the end of roop : i < len of s — len of u;) And my code in php was acceptted.

 » 21 month(s) ago, # |   0 for (\$i = 0; \$i < \$ls; \$i++) \$i < \$ls => \$i < \$ls — \$lu + 1
•
 » » 21 month(s) ago, # ^ |   0 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.
•
 » » » 21 month(s) ago, # ^ |   0 this fix makes code a little bit faster.
•
 » » » » 21 month(s) ago, # ^ |   0 Thank you. Your comment is right, so I will amend this parts　and be careful of these parts in the next. Your fast reply is very helpful.Thank you very much.
•
 » » » » 21 month(s) ago, # ^ |   0 By Your comment , not using java, my code in php is acceptted. Thank you very much.

 » 21 month(s) ago, # |   -8 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.
•
 » » 21 month(s) ago, # ^ |   0 Thank you very much. Fast Fourier Transformation Your advice is helpful. I do not know this much, but normally this is not used in these level problem, I think so. 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. Reading "Java is faster than php in such N and M", I try to use java in such N and M(in two roop). Thank you. (I have used java, but I do not understand the difference of java and php in parformance much)