Ну, я никогда не думал, что мой счет достигнет этого, поэтому я старался изо всех сил, и тогда это случилось. Всегда помните, трудолюбие и самоотверженность являются ключом.

Доброе утро всем. Меня зовут Анудж Кумар из Индии, я учусь на бакалавриате в области компьютерных наук и инженерии. Если вам понравились мои советы по улучшению навыков программирования или вы считаете, что мое решение можно улучшить, дайте мне знать.

Что такое хэш-код?

Командное соревнование Google по программированию Hash Code позволяет вам поделиться своими навыками и пообщаться с другими программистами, работая вместе над решением проблемы, смоделированной на основе реальной инженерной задачи Google! В небольших командах от двух до четырех программисты со всего мира будут решать первую задачу в квалификационном онлайн-раунде. Хотя этот раунд проводится онлайн, команды могут собраться вместе, чтобы соревноваться бок о бок в локально скоординированных центрах Hash Code. Лучшие команды этого раунда приглашаются присоединиться к людям в международном офисе Google для нашего ежегодного финального раунда Hash Code.

Хотите узнать, имеете ли вы право на участие?

Пожалуйста, посетите веб-сайт правил и условий Google HashCode для получения обновленной информации по этой ссылке.

Так в чем заключалась практическая проблема?

Каждый год участникам дается постановка практической задачи, чтобы они попытались понять, что будет происходить в основном онлайн-квалификационном раунде. Например, получение входных данных из заданного файла или отправка выходного результата в другой файл также являются важной частью решения подобных задач. В этом году, в 2020-м, постановка задачи выглядит достаточно просто, но обычным программистам по-прежнему трудно выполнить необходимые требования задачи. Постановку задачи можно посмотреть по этой ссылке.

Примечание. Прежде чем продолжить изучение этой статьи, убедитесь, что вы хорошо поняли вопрос.

Несколько основных моментов, которые необходимо помнить при решении проблемы, заключаются в следующем:

  1. Организатор мероприятия может заказать не более одной пиццы каждого вида.
  2. Каждый тип пиццы имеет определенный размер, то есть количество кусочков в этой конкретной пицце.
  3. Нам нужно заказать как можно больше кусочков пиццы, но не больше, чем количество людей, которые придут на это мероприятие. Определенно, дополнительные ломтики будут потрачены впустую, если мы закажем больше ломтиков, чем людей, прибывающих на мероприятие.

СТРУКТУРА ВХОДА

Входной файл представляет собой обычный текстовый файл, и каждый входной файл, т. е. каждый набор данных, представляет собой отдельный экземпляр задачи для тренировочного раунда. Эти символы представляют собой исключительно символы ASCII и строки, заканчивающиеся одним символом «\n» (окончание строк в стиле UNIX). Кроме того, когда одна строка содержит несколько элементов, они разделяются одиночными пробелами.

Структура содержимого входного файла выглядит следующим образом:

M N

a0 a1 a2……… aN

M — целое число с ограничениями (1≤ M≤ 10⁹). Он описывает максимальное количество кусочков пиццы, которые нужно заказать. Точно так же N — целое число с ограничениями (1≤ N ≤ 10⁵). Он описывает количество пицц, предлагаемых местом, откуда пицца заказывается.

1 ≤ s0 ≤ s1 ≤ s2 ≤ …… ≤ sN-1 ≤ M

В следующей строке есть N целых чисел, представляющих количество кусочков в каждом типе пиццы, в неубывающем порядке, как указано выше.

СТРУКТУРА РЕЗУЛЬТАТОВ

Точно так же мы должны использовать символы ASCII в выходном файле, а новая строка создается с использованием символа «\ n». Структура содержимого выходного файла выглядит следующим образом:

K

a1 a2……… aN

K — целое число с ограничениями (0≤ K≤ N). Он описывает количество заказываемых сортов пиццы. В следующей строке должно быть K целых чисел, типы пиццы, которые нужно заказать (типы пиццы пронумерованы от 0 до N -1 в том порядке, в котором они перечислены во входных данных).

Итак, как я решил?

Используемый язык: Java

Сначала я думал, что это довольно простая задача, но, конечно же, Google дал конкурентам эту задачу, придумав что-то. Так что выполнить эту задачу будет не так-то просто. Как обычно, самое главное при решении задачи — разделить ее на несколько небольших задач. Это снижает рабочее напряжение, полностью исключает различную логику и ускоряет общее решение проблем.

Я разделил основную проблему на 4 подзадачи. Они есть:

Мини-задача 1: копирование значений из входного файла в программу. Чтобы я мог над ними работать.

Мини-задача 2:обработка граничных ограничений. (В моем случае наборы входных данных находились под заданными ограничениями, поэтому я не позаботился об этом. Но в реальных сценариях обработка граничных ограничений чрезвычайно важна — это позволяет избежать ошибок и ошибок, которые могут возникнуть в дальнейшем)

Мини-задача 3:Основная проблема — найти разные виды пиццы для заказа и выбранные сорта.

Мини-задача 4:Сохранение результата в выходной файл.

РЕШЕНИЕ МИНИ-ПРОБЛЕМЫ 1

Необходимо было захватить все значения из входного файла в программу. В нескольких заданных наборах данных есть тысячи целых чисел. Я бы определенно не стал вводить эти значения сам. Итак, я подумал о рабочем процессе. Как следует из входной структуры, в первой строке присутствуют только два числа, и их необходимо сохранить в переменной с именами M и N. Точно так же в следующей строке есть N целых чисел с количеством срезов. Массив был бы наилучшей структурой данных для хранения похожих данных.

Итак, я сделал это:

void takeInputFromFile(String pathName) throws FileNotFoundException {
 //Creating File Object from Input Pathname
 File file =
 new File(pathName);
 //New Scanner Object from file object
 Scanner sc = new Scanner(file);
 int count = 1;
 while (sc.hasNextLine()) {
 if (count == 1) {
 //Storing M and N from first line of input.
 String line = sc.nextLine();
 String[] tokens = line.split(“ “);
 m = Integer.parseInt(tokens[0]);
 n = Integer.parseInt(tokens[1]);
 count++;
 } else if (count == 2) {
 //Storing the size of N types of Pizza in an Array of size N.
 mySizeArray = new int[n];
 selectedArray = new Integer[n];
 String line = sc.nextLine();
 String[] tokens = line.split(“ “);
 for (int i = 0; i < n; i++) {
 mySizeArray[i] = Integer.parseInt(tokens[i]);
 }
 count++;
 } else {
 //Boundary Check If Line Exceeds The Input Constraint Strategy of two lines.
 break;
 }
 }
 }

Я создал метод с именем входного файла в качестве аргумента. Этот метод будет довольно простым, если вы знаете о классе File (java.io.File). Он берет файл и, используя класс Scanner (java.util.Scanner), я читаю первую и вторую строку. Входной файл содержит всего две строки. Итак, я справился с ограничением, пренебрегая предстоящими строками ввода. То есть любой контент за пределами двух строк будет просто проигнорирован. В первой строке я копирую M и N, а затем сохраняю их в переменную. Точно так же во второй строке я копирую все оставшиеся N переменных в массив с именем mySizeArray размера N.

РЕШЕНИЕ МИНИ-ПРОБЛЕМЫ 2

Эта часть была проигнорирована мной, поскольку ввод уже соответствовал заданным ограничениям. Я повторяюсь: всегда сталкивайтесь с такими ограничениями. Оценщики могут снизить ваш балл, просто предоставив входные данные, выходящие за пределы предварительно заданного ограничения.

РЕШЕНИЕ МИНИ-ПРОБЛЕМЫ 3

Теперь я скопировал значения из файла в переменные M и N и массив с именем mySizeArray. Теперь этот метод просто говорит, что я делаю. Это довольно просто, верно?

void findValues() {
        myList = new ArrayList<Integer>();
        for (int i = mySizeArray.length - 1; i >= 0; i--) {
            if (mySizeArray[i] + sum <= m) {
                sum = sum + mySizeArray[i];
                myList.add(i);
            }
        }
        while (myList.remove(null)) {
        }
selectedArray = myList.toArray(new Integer[myList.size()]);
        sum = 0;
        myList = null;
    }

Я создаю список, чтобы узнать индексы выбранных сортов пиццы. Затем я удаляю нулевые элементы, если не выбраны все разновидности. (Это определенно произойдет.) Я просто выбираю сорт пиццы, если заказ этой пиццы просто не превысит количество людей, прибывающих на мероприятие.

Затем я помещаю эти значения просто в выбранный массив. Кроме того, размер списка будет равен размеру selectedArray. Вот как я получаю элементы, которые мне нужно отправить в выходной файл.

РЕШЕНИЕ МИНИ-ПРОБЛЕМЫ 4

Этот метод создает PrintStream (java.io.PrintStream). Затем отправляет целое число K и переменные selectedArray в выходной файл через этот PrintStream. И последнее, для моей информации, он печатает на консоли, что он завершил сохранение результатов.

void sendOutputToFile(String outputPathName) throws FileNotFoundException {
 // Creating a File object that represents the disk file.
 PrintStream o = new PrintStream(new File(outputPathName));
// Store current System.out before assigning a new value
 PrintStream console = System.out;
// Assign o to output stream
 System.setOut(o);
 System.out.println(selectedArray.length);
 for (int i = 0; i < selectedArray.length; i++) {
 System.out.print(selectedArray[i] + “ “);
 }
// Use stored value for output stream
 System.setOut(console);
 System.out.println(“Output Successfully stored!”);
 }

Теперь мне нужно обработать программу для всех входных файлов. Я просто сделал это с помощью цикла for следующим образом:

public static void main(String[] args) throws FileNotFoundException {
        Main main = new Main();
        //Input File Name Array
        String[] inputs = {"a_example", "b_small", "c_medium", "d_quite_big", "e_also_big"};
        for (String file : inputs) {
            String inputPathName = "C:\\Users\\anuji\\Desktop\\Hash Code\\" + file + ".in";
            String outputPathName = "C:\\Users\\anuji\\Desktop\\Hash Code\\" + file + ".out";
            //Copying values from file to program's variables so that it can be further processed.
            main.takeInputFromFile(inputPathName);
            //Acting upon given values
            main.findValues();
            //Storing the required values from program to file
            main.sendOutputToFile(outputPathName);
        }

Этот метод просто запускается для всех входных файлов и взамен создает выходные файлы.

Итак, как рассчитывается оценка?

Решение получает 1 балл за каждый заказанный кусок пиццы.

Например, если в выводе указано 3 пиццы: s0, s2 и s3. (Вывод первого входного файла). Мы знаем, что кусков пиццы в каждом из них 2, 6 и 8 соответственно. Таким образом, счет: 2+6+8 = 16 очков.

Таким образом, общий балл будет равен сумме всех кусков пиццы, заказанных во всех этих сценариях.

Обратите внимание, что существует несколько наборов данных, представляющих отдельные экземпляры проблемы. Общий балл для вашей команды будет суммой ваших лучших результатов для отдельных наборов данных.

В моем случае: я набрал 1 505 004 318 баллов из 1 505 004 617 баллов (максимальное количество людей, прибывающих на мероприятие, и, следовательно, максимальное количество кусочков пиццы, которые нужно заказать)

Максимально возможные баллы для следующих экземпляров: 17, 100, 4500, 1000000000 и 505000000 соответственно. Итак, это означает, что я набрал 1 505 004 318 баллов, что всего на 299 баллов меньше от максимально достижимого результата. Это решение не является оптимальным по своей природе и может быть очень хорошо улучшено. Я хотел бы, чтобы вы, ребята, попробовали это и поделились своим подходом и точками.

Благодарность

Я хотел бы поблагодарить команду Google HashCode за то, что они предоставили такие проблемы для мозгового штурма. Я имею в виду, что каждый может получить от этого пользу, если посвятит себя лучшему человечеству. После решения задачи, на которую в общей сложности ушло меньше суток, хотелось бы рассказать читателям несколько вещей. Всегда создавайте заранее определенный рабочий процесс или дорожную карту, которая указывает, куда вам нужно двигаться дальше. Всегда думайте о таких вещах, которые были бы наиболее подходящими для реализации решения проблемы.

Вывод

Квалификационный раунд hashCode начинается 20 февраля 2020 года, а регистрация закрывается 19 февраля 2020 года, вы можете зарегистрироваться здесь, если вы еще этого не сделали, и хотя бы попытаться принять участие в этом году, и кто знает, возможно, вы уже на Ваш путь в штаб-квартиру Google на финал. Если вы не зарегистрированы и у вас нет команды, но вы хотели бы участвовать, зарегистрируйтесь и найдите себе подобных в социальных сетях. Может быть, Мы можем подготовить команду для вас. Кроме того, вы можете попробовать хабы, где вы и ваши товарищи по команде можете работать.

Вы можете оставлять свои вопросы в комментариях, и я с удовольствием на них отвечу.

Спасибо за ваше время.