Question 197899 in PHP Question posted in
Official manual can be found here.

Php – is there an opportunity to optimize the code here?

I’m trying to write code for an algorithmic task in PHP, but I don’t pass the Time Limit. How could I optimize the code by at least 10%?

Kuzya again did not have time to pass the essay on linguistic diversity on time. "I probably have some kind of suboptimal keyboard…" thought Kuzya and decided to invent the most optimal keyboard for typing with one finger.
Kuzya decided that his keyboard would contain
N rows with keys (different rows may contain different numbers of keys). All keys on the keyboard will be unique.For example, let the text S be equal to ABCD, and the keyboard contains two rows of keys AC and BD. In this case, there will be exactly 3 multi-row transitions when typing:S1=A in S2=B (row 1 in row 2); S2=B in S3=C (row 2 in row 1);S4=A in S5=D (row 1 in row 2).
Kuzya asks you, as the best Tetris player among friends, to calculate the heterogeneity of the created they used keyboards on the last of Kuzin’s essays.

The first line contains a single integer N(1≤N≤2⋅10^5) — the number of keys on the keyboard.

The second line contains N integers ci(0≤ci≤10^9) — the identifiers of the characters on the keys. It is guaranteed that all ci values are different.

The third line contains N integers ri(1≤ri≤10^9). The number ri specifies the number of the row on the keyboard in which the key with the symbol ci is located.

The fourth line contains a single integer K(1≤K≤2⋅10^5) — the number of characters in the essay.

The fifth line contains K integers sj(0≤sj≤10^9) are the identifiers of the essay characters in the order of typing on the keyboard. It is guaranteed that for any sj there exists such an i that sj=ci — any character from the essay is present on the keyboard.

The output is a single integer — the multi-bitness of the keyboard design specified in the input data on the essay S.
for example:
INPUT:

4
1 2 3 4
1 2 1 2
5
1 2 3 1 4

OUTPUT:

3

Below is my code that I have already tried to optimize:

<?php
$N = intval(readline());
$alph = array_map('intval', explode(' ', readline()));
$rows = array_map('intval', explode(' ', readline()));
$K = intval(readline());
$string = array_map('intval', explode(' ', readline()));
$mapper = array_combine($alph, $rows);
$counter = 0;
for ($i = 0, $length = count($string); $i < $length - 1; $i++) {
    if ($mapper[$string[$i]] !== $mapper[$string[$i+1]]) {
        $counter++;
    }
}
echo $counter;
?>
Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    here's BEST solution i have found:

    <?php
$N = intval(fgets(STDIN));
$alph = array_map('intval', explode(' ', fgets(STDIN)));
$rows = array_map('intval', explode(' ', fgets(STDIN)));
$K = intval(fgets(STDIN));
$string = array_map('intval', explode(' ', fgets(STDIN)));
$mapper = array_combine($alph, $rows);
$count = 0;
for ($i = 1; $i < $K; $i++) {
    if ($mapper[$string[$i-1]] != $mapper[$string[$i]]) {
        $count += 1;
    }
}
echo $count;
?>

    it takes 188ms on tests maximum


  2. 0

    You could be making fewer calls to count() and reducing how many times you access the array within the loop. For example:

    <?php
$N = intval(readline());
$alph = array_map('intval', explode(' ', readline()));
$rows = array_map('intval', explode(' ', readline()));
$K = intval(readline());
$string = array_map('intval', explode(' ', readline()));

$mapper = array_combine($alph, $rows);

$counter = 0;
$current_row = $mapper[$string[0]];
$length = count($string);

for ($i = 1; $i < $length; $i++) {
    $next_row = $mapper[$string[$i]];
    if ($current_row !== $next_row) {
        $counter++;
        $current_row = $next_row;
    }
}

echo $counter;
?>

    Main changes:

    • Move the count() call outside of the loop to avoid recalculating
      the length repeatedly.

    • Use a variable $current_row to keep track of the current row, so you only access the array once per iteration.

    This should make your code run faster, especially with large inputs.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search