1

Тема: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

https://algotester.com/uk/ArchiveProble … File/40463
Задача ніби проста, але на 10 прикладі ліміт часу і я не уявляю, як можна оптимізувати програму.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        new Vau();
    }
}

class Vau{

    public Vau(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // умова каже, що числа належать відрізку [1;10^9], тому мінімуму присвоюємо значення 10^9+1,
        // щоб перше число було менше за мінімум і він скрикнув "вау"
        int min = 1_000_000_001;
        int result = 0;
        for (int i = 0; i < n; i++){
            //вводи число
            int input = in.nextInt();
            //якщо число менше за мінімум, то отримуємо новий мінімум і результат збільшуємо на 1
            if (input <= min) {
                result++;
                min = input;
            }
        }
        System.out.println(result);
    }
}

І намагався з масивом, але результату це не дало.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        new Vau();
    }
}

class Vau{

    public Vau(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int i_minimal_element = 0 , result = 0;
        for (int i = 0; i < n ; i++){
            arr[i] = in.nextInt();
            if (arr[i] <= arr[i_minimal_element] ){
                i_minimal_element = i;
                result++;
            }
        }
        System.out.println(result);
    }
}

Буду щиро вдяний за допомогу!

2

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

https://algotester.com/uk/ArchiveProblem
Тут в пошуку ви можете ввести або номер або назву задачі. Просто один форумчанин зробив зауваження, що зручніше шукати задачу таким способом.

3

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Так, схоже, це неприємна ситуація з оптимальним алгоритмом. Вам у будь-якому разі доведеться читати всі елементи і перевіряти їх - отже, швидше, ніж O(n), не вийде, а у вас і так O(n).
Гальмує, швидше за все, Scanner.nextInt. Спробуйте читати по символу (можливо, через BufferedReader) і вручну збирати числа, це не так складно (якщо прочитали цифру - поточне число множимо на 10 і додаємо цифру, якщо пробіл, новий рядок чи кінець введення - обробляємо поточне число і скидаємо його в 0). Якщо не вистачить - дам ще один лайфхак по швидкості.

Подякували: zxzpogoncuk1

4

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Дякую, задача пройшла на максимальний бал! Використав System.in.read().

public class Main {

    public static void main(String[] args) {
        new Vau();
    }
}

class Vau{
    public Vau(){
        int n = 0, inp;
        try{
            // поки не натиснимо enter читаємо n по цифрах
            while ((inp  = System.in.read()) != 10){
                n = n*10 + (inp - 48);
            }
        }catch (Exception e){}


        int min = 1_000_000_001, result = 0, numbers = 0;
        try {
            // поки не натиснули enter
            while (  (inp = System.in.read()) != 10){
                // якщо не натиснули пробіл(якщо число не закінчилося)
                if (inp != 32) numbers = numbers*10 + (inp - 48);
                else{// якщо число закінчилося, то порівнюємо його з мінімумом,
                     // якщо менше рівне, то отримуємо новий мінімум і результат збільшується
                    if (numbers <= min){
                        min = numbers;
                        result++;
                    }
                    //обнуляємо число, бо після пробілу вводи наступне
                    numbers = 0;
                }
            }
            // після того, як натиснули enter останнє введене число не порівнялося з мінімумом
            // тому порівнюємо
            if (numbers <= min) result++;

        }catch (Exception e){}
        System.out.println(result);
    }
}

5

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

А який максимальний час?

6

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Обмеження 1 секунда, а програма найдовше працювала 0,232 секунди.

Подякували: koala1

7

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Значить, порада про BufferedReader була шкідливою.
Ідею з подальшою оптимізацією перевірив, але вона дала десь 5мс економії. Якщо цікаво, розповім.
Раджу замість 10, 32 і 48 писати '\n', ' ' і '0' - значення ті самі, а код читаніший.

Подякували: zxzpogoncuk1

8

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Звісно ж розповідайте.

9

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Операція множення трохи повільна. А нам тут треба на 10 багато разів множити. Скористаємося тим цікавим фактом, що якщо одне число менше за друге в десятковій системі, то числа в будь-якій системі числення, що записуються так само, не змінюють порядку (якщо, звісно, лишаються коректними). Наприклад, 15>12 і в десятковій системі, і в вісімковій (де це означає 13>10).
Замінимо систему на 16-кову. Тоді множення можна замінити на зсув:

numbers = numbers<<4 + (inp-48);

Можна піти далі і замінити все бітовою арифметикою:

numbers = (numbers<<4) | (inp & 0xF);

На жаль, тепер доведеться збільшити розрядність до long - число 0x80000000 не влазить в int.

Подякували: zxzpogoncuk, leofun012

10

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Хоч я читав про побітові операції, але я не розумію як це працює. Чому зсуваємо на 4? Чому логічне або , і замінюють дію додавання і віднімання.
Наприклад, маємо 4(10) = 100(2) , коли ми зсуваємо на 4, то отримуємо 100 0000, а це дорівнює 64.

11

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Зсув на один ліворуч — те саме, що дописати двійковий нуль справа до числа. Якщо ми в десятковій системі дописуємо 0 справа, то це еквівалент множення на 10, так? У двійковій те саме, тільки 10 там означає 2. Зсув на 4 - 4 рази множення на 2, тобто множення на 16.

13<<1 == 26
4<<4 == 64

Звертаємо увагу, що цифри мають послідовні коди від 48, а 48 закінчується 4 двійковими нулями (ну тобто ділиться на 16). Отже, всі цифри від 0 до 9 мають останні 4 розряди, як дорівнюють числовому значенню цих цифр. Вимикаємо решту розрядів бітовим & з 0b1111 == 0xF - старші розряди стають 0, молодші 4 лишаються:

'6' & 0xF == 54 & 0xF == 6

Тепер ми маємо:
- число з 4 останніми нульовими двійковими розрядами
- число з 4 останніми розрядами, яке ми маємо дописати в кінець
Ось це і робить | - "вмикає" одинички там, де хоча б в одному з двох чисел вони є. Обидва числа мають 0 там, де в іншому числі розряди, що містять інформацію, тобто результат буде просто "переписуванням" потрібних розрядів без побічних ефектів, і це трохи швидше за додавання. Все.

Подякували: zxzpogoncuk, leofun012

12

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Вау! Оце круто! Я б до такого ніколи не додумався. Підкажіть що почитати, щоб більше дізнатися про побітові операції і ось такі трюки.

13

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Штудіюйте Токхейм Цифрова схемотехніка

Подякували: zxzpogoncuk1

14

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Я став засмічувати розділ Java своїми запитаннями про задачі. Може варто створити одну тему "Задачі" і там все викладати?

15

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Та ні, нормально. От якби ви умови сюди копіювали - було б краще.

Подякували: zxzpogoncuk1

16

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Спробував закинути на алготестер програму з використання побітових опекрацій і на 2-ому прикладі неправильна відповідь.

public class Main {

    public static void main(String[] args) {
        new Vau();
    }
}

class Vau{
    public Vau(){
        long n = 0L, inp;
        try{

            while ((inp  = System.in.read()) != 10){
                n = (n<<4) | (inp & 0xF);
            }
        }catch (Exception e){}


        long min = 1_000_000_001L, result = 0L, numbers = 0L;
        try {
            while (  (inp = System.in.read()) != 10){
                if (inp != 32) numbers = (numbers<<4) | (inp & 0xF);
                else{
                    if (numbers <= min){
                        min = numbers;
                        result++;
                    }
                    numbers = 0L;
                }
            }
            if (numbers <= min) result++;

        }catch (Exception e){}
        System.out.println(result);
    }
}

Ось ця програма на 4 прикладі.

public class Main {

    public static void main(String[] args) {
        new Vau();
    }
}

class Vau{
    public Vau(){
        int n = 0, inp;
        try{

            while ((inp  = System.in.read()) != 10){
                n = (n<<4) | (inp & 0xF);
            }
        }catch (Exception e){}


        int min = 1_000_000_001, result = 0, numbers = 0;
        try {
            while (  (inp = System.in.read()) != 10){
                if (inp != 32) numbers = (numbers<<4) | (inp & 0xF);
                else{
                    if (numbers <= min){
                        min = numbers;
                        result++;
                    }
                    numbers = 0;
                }
            }
            if (numbers <= min) result++;

        }catch (Exception e){}
        System.out.println(result);
    }
}

Підкажіть ,будь ласка, що не так.

17

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

Ви n читаєте побітовим способом. Але він же неправильно читає числа - він лише зберігає їхній порядок.

Подякували: zxzpogoncuk1

18

Re: Алготестер задача №0877. Мінімальні вигуки. Проста задача, але ...

zxzpogoncuk написав:

Вау! Оце круто! Я б до такого ніколи не додумався. Підкажіть що почитати, щоб більше дізнатися про побітові операції і ось такі трюки.

https://replace.org.ua/post/145904/

Подякували: zxzpogoncuk, leofun012