Loading...
Flucg avatar Flucg 16 Точки

Изкарвам 60/100 точки на BitSnow от изпита в неделя. Виждам, че почти всички имат 100 точки. Къде бъркам?

Здравейте,

Ето моето решение с битови операции:  https://pastebin.com/77VrBqgz  => Нищо сложно, тръгвам "отдолу-нагоре" и с вградените в bigInteger битови операции преправям битовете.

 

Може ли насоки къде бъркам или решение, което дава 100/100 аз ще се оправя натам.

Поздрави,

Ангел

Тагове:
0
Java Advanced
MartinBG avatar MartinBG 4803 Точки

Решението ти не минава 4 теста в Judge заради превишаване на зададените лимити за време (0.360s при лимит от 0.120). Това най-често означава, че използваният алгоритъм не е достатъчно ефективен (има твърде много излишни операции), или имаме неподходящ избор на контейнер(и) за данните, ако програмата работи с големи обеми информация.

В конкретната задача трябва да помислиш за алгоритъм, при който няма да ти се налага да обхождаш числата N * N пъти, както правиш в момента (т.е. имаш квадратична сложност на алгоритъма; при 100 числа ще правиш 100 * 100 = 10 000 итерации).

Ако се справиш с този проблем, решението ти най-вероятно ще мине в Judge.

Ако не мине, имаш още доста какво да оптимизираш:

- BigInteger е относително бавен клас и трябва да се ползва само когато наистина ни се налага. В случая работим с 16 битови числа, т.е. int  (32-bit) ни е напълно достатъчен

- Пазиш числата като стрингове и ги преобразуваш към число и обратно към стринг при всяка итерация. 

- Използваш методите на BigInteger класа за побитови операции, което си идва с цена откъм време, вместо да работиш директно с битовете на числата.

 

Това е моето решение (с линейна сложност; достъпва всеки елемент само три пъти - да му прочете битовете, да сглоби резултата и да го отпечата; т.е. за 100 елемента имаме 300 срещу 10000 итерации при твоето решение). Минава за около 0.030s.  

 

Ако ти е интересно, може да погледнеш и тази тема, където съм направил сравнение на две решения на една и съща задача - едното с линейна, а другото - с квадратична сложност. Разликите в бързодействието са огромни.

2
25/10/2017 01:40:38
Flucg avatar Flucg 16 Точки

Благодаря много за изчерпателния и най-вече бърз отговор, въпреки абсурдния час, в който пуснах темата. Честно казано веднага го видях и започнах да дебъгвам, но много от синтаксиса в горното решение го виждам за първи път. Не знам дали е заради слабата ми подготовка или е нещо, което съм изпуснал, но е факт че горното по-скоро ме демотивира в началото, отколкото да ме обнадежди :/

Само ми показа колко нищо не знам :D 

Реших да го зарежа, но днес се ядосах как така толкова хора са я решили, а аз не и реших да пробвам по "селският" метод със стрингове без битови операции и написах едно "бързо" решение с "Матрица", което е всичко, но красиво, но дава 100/100 за 0.071 секунди. 

https://pastebin.com/Tz0kAy9w

Идеята е проста.

1. Създава се матрица с размери: Редове - броят на елементите, Колони - 16 на брой (16 битови числа). 

2.  Взимат се елементите от входа и се превръщат в масив от нули и единици, като в началото на всеки масив се добавят нулички, за да се превърне в 16 битов. 

3. Обхожда се матрицата по колони и се броят колко единички има във всяка колона. 

Същият този ред се обхожда отдолу нагоре (или кой както иска) и се запълват толкова реда с единички, колкото е броят, който сме преброили отгоре. Допълва се със нули до най-горният ред на матрицата.

(Поради слабите ми дебъгърски умения си създадох нова матрица, в която си запълвам изхода, това не е нужно може и в оригиналната матрица да се пълнят). 

4. Обновената матрица се обхожда по редове, като всеки ред масива от 0-ли и 1-ци се превръща в нормално число, което се запазва в изходен масив.

5. Със String.join(", ", изходниятМасив) се създава желаният от judge изход и се принтира на конзолата. 

Успех и късмет! 

 

0
27/10/2017 18:06:59
kosyokosev avatar kosyokosev 27 Точки

Колеги ето едно решение и от мен което мисля че е разбираемо и доста кратко.За съжаление не можах да го направя на изпита:)

Ако някой ми каже как да използвам String.join за масиви които не са String щесъм му благодарен

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BitSnow {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = reader.readLine().split(", ");

        int[] numbers = new int[input.length];

        for (int i = 0; i < input.length; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }

        for (int i = numbers.length - 1; i > 0; i--) {
            int firstValue = numbers[i];

            numbers[i] = numbers[i] | numbers[i - 1];
            numbers[i - 1] &= firstValue;

            for (int j = i - 2; j >= 0 ; j--) {
                firstValue = numbers[i];
                numbers[i] = numbers[i] | numbers[j];
                numbers[j] &= firstValue;
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < numbers.length; i++) {
            sb.append(numbers[i]);
            if (i != numbers.length - 1){
                sb.append(", ");
            }
        }
        System.out.println(sb.toString());
    }
}
0
MartinBG avatar MartinBG 4803 Точки

Интересно решение, наистина, добра работа с побитовите операции! smiley

Но алгоритъмът отново е неоптимален - вложен цикъл, в който отново обхождаме (част от) елементите.

Не, че има значение за тази задача или при по-малко на брой входни данни, но подобни задачи са добра основа за търсене и намиране на по-ефективни решения и придобиването на умения, за случаите в практиката, когато бързодействието е важно. 

 

EDIT:

Относно въпросът за String.join, може да погледнеш отговорите ми в тази тема

А това е пример с обикновен int[]:

        int[] numbers = new int[10];
        System.out.println(Arrays.toString(numbers).replaceAll("[\\[\\]]", ""));

Output:

0, 0, 0, 0, 0, 0, 0, 0, 0, 0

 

0
03/01/2018 17:12:58
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.