none
Операция MEX, не укладываюсь в 3 секунды - C# RRS feed

  • Вопрос

  • Не могу уложиться в 3 секунды по решению задачи

    Условие задачи

    MEX

    ограничение по времени на тест3 секунды 
    ограничение по памяти на тест256 мегабайт
    вводstdin
    выводstdout

    Операция MEX для набора целых неотрицательных чисел возвращает наименьшее неотрицательное целое число, не содержащееся в наборе. Например, для набора (0, 1, 2, 2, 4, 4, 11) это значение равно 3, для набора (1, 1, 2, 5, 7) это значение равно 0, а для набора (0, 1, 2, 2, 2, 3) это значение равно 4. В наборе могут встречаться одинаковые числа. Вам задана последовательность из нескольких операций одного из двух видов:

    + x — добавить число x в набор.
    - x — удалить одно вхождение числа x из набора (если числа x в наборе нет, то операция игнорируется).
    Изначально набор пуст. Вам необходимо вывести значение MEX для набора после применения каждой из операций. Операции выполняются последовательно одна за другой.

    Входные данные

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

    + x — добавить число x в набор (0 ≤ x ≤ 109).
    - x — удалить одно вхождение числа x из набора.
    Знак операции и число разделены единичным пробелом.

    Выходные данные

    Выведите n чисел через пробел — значение MEX для набора после применения каждой из указанных операций.

    Примеры

    входные данные

    7
    + 2
    + 1
    + 0
    + 4
    + 2
    - 2
    - 2

    выходные данные

    0 0 3 3 3 3 2

    входные данные

    6
    + 0
    + 1
    + 0
    - 1
    - 0
    - 0

    выходные данные

    1 2 2 1 1 0

    Примечание

    Операция MEX (minimum excludant) является одной из основных операций в теории игр.

    Код реализованный мной на C#

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
     
    namespace ConsoleApp186
    {
        class Program
        {
            static void Main(string[] args)
            {
                List<int> introw = new List<int>();
                List<int> intresult = new List<int>();
                int min = 0;
                int x = 0;
                int n = int.Parse(Console.ReadLine());
                for (int i = 0; i < n; i++)
                {
                    string current = Console.ReadLine();
                    if (current.Substring(0, 1) == "+")
                    {
                        x = int.Parse(current.Substring(1, current.Length - 1));
                        introw.Add(x);
                        if (x == min)
                        {
                            while (introw.Contains(min))
                            {
                                min++;
                            }
                        }
                    }
                    else
                    {
                        x = int.Parse(current.Substring(1, current.Length - 1));
                        introw.Remove(x);
                        if (x < min)
                        {
                            if (introw.Contains(x) == false)
                            {
                                min = x;
                            }
                        }
                    }
                    intresult.Add(min);
                }
                Console.WriteLine(String.Join(" ", intresult));
                Console.ReadLine();
            }
        }
    }
    


    16 октября 2017 г. 12:25

Ответы

  • По моим тестам, при входном наборе из 150000 случайных чисел от 0 до 100, время выполнения:

    Цикл: 32 ms
    
    Метод String.Join: 16 ms
    
    Вывод результата (при выводе в консоль): 14000 ms
    
    Вывод результата (при перенаправлении стандартного вывода в файл): 6 ms
    

    В общем, нужно чуть больше информации, в каком именно окружении запускается программа, чтобы ответить на этот вопрос.

    Edit: единственное, что я изменил это current.Substring(0, 1) == "+" заменил на current[0] == '+' , выиграло всего ~3 ms 

    Вот код с измерениями:

    static void Main(string[] args)
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                long t1, t2;
    
                t1 = sw.ElapsedMilliseconds;
                List<int> introw = new List<int>();
                List<int> intresult = new List<int>();
                
                int min = 0;
                int x = 0;
                int n = int.Parse(Console.ReadLine());
                
    
                t2 = sw.ElapsedMilliseconds ;
                Console.WriteLine("Init: " + (t2 - t1).ToString() + "ms");
    
                t1 = sw.ElapsedMilliseconds;
                          
                
    
                for (int i = 0; i < n; i++)
                {
                    string current = Console.ReadLine();
    
    
                    if (current[0] == '+')
                    {
                        x = int.Parse(current.Substring(1, current.Length - 1));
                        introw.Add(x);
                        if (x == min)
                        {
                            while (introw.Contains(min))
                            {
                                min++;
                            }
                        }
                    }
                    else
                    {
                        x = int.Parse(current.Substring(1, current.Length - 1));
                        introw.Remove(x);
                        if (x < min)
                        {
                            if (introw.Contains(x) == false)
                            {
                                min = x;
                            }
                        }
                    }
                    intresult.Add(min);
                }
    
                t2 = sw.ElapsedMilliseconds;
                Console.WriteLine("Loop: " + (t2 - t1).ToString() + "ms");
    
                t1 = sw.ElapsedMilliseconds;
                string str = String.Join(" ", intresult);
                t2 = sw.ElapsedMilliseconds;
                Console.WriteLine("Join: " + (t2 - t1).ToString() + "ms");
    
                t1 = sw.ElapsedMilliseconds;
                Console.WriteLine(str);
                t2 = sw.ElapsedMilliseconds;
                Console.WriteLine("Out: " + (t2 - t1).ToString() + "ms");
    
                Console.ReadLine();


    16 октября 2017 г. 17:34

Все ответы

  • На мой взгляд это ускорить можно, если отказаться от преобразования типов, но не забыть про сортировку строк. Отказаться от for в пользу while. Плюс у списков есть функция IndexOf работает чутка быстрее обычного перебора.
    16 октября 2017 г. 13:22
  • Liliya Muray, могли бы вы переделать, очень надо вложиться в 3 секунды,
    • Изменено CBBBBB 16 октября 2017 г. 13:30
    • Изменено Alexander RusinovModerator 16 октября 2017 г. 19:11 Удален текст " 500 р. могу сразу на карту сбросить, как сделаете"
    16 октября 2017 г. 13:30
  • Простите не до смотрела, у Вас используется Contains. Единственное улучшение, что можно это

    int.Parse(current.Substring(2, current.Length - 2));

    Убрать пробел из преобразования строки в число. Простите, не могу найти из-за чего у вас код работает медленно. На каких объемах код начинает тормозить чтоб выполняться больше 3-х секунд?

    16 октября 2017 г. 14:13
  • Вот так бы выглядел код с чуть меньшим кол-вом int.parse
    using System;
    using System.Collections.Generic;
    
    namespace ConsoleApp186
    {
        class Program
        {
            static void Main(string[] args)
            {
                List<string> introw = new List<string>();
                List<string> intresult = new List<string>();
                string min = "0";
                string x = "0";
                int n = int.Parse(Console.ReadLine());
                for (int i = 0; i < n; i++)
                {
                    string current = Console.ReadLine();
                    if (current.Substring(0, 1) == "+")
                    {
                        x = current.Substring(2, current.Length - 2);
                        introw.Add(x);
                        if (x == min)
                        {
                            int imin = int.Parse(min);
                            while (introw.Contains(min))
                            {
                                imin++;
                                min = imin.ToString();
                            }
                        }
                    }
                    else
                    {
                        x = current.Substring(2, current.Length - 2);
                        introw.Remove(x);
                        if ((String.Compare(x,min)==-1)&&(x.Length<=min.Length))
                        {
                            if (introw.Contains(x) == false)
                            {
                                min = x;
                            }
                        }
                    }
                    intresult.Add(min);
                }
                Console.WriteLine(String.Join(" ", intresult));
                Console.ReadLine();
            }
        }
    }


    16 октября 2017 г. 14:35
  • По моим тестам, при входном наборе из 150000 случайных чисел от 0 до 100, время выполнения:

    Цикл: 32 ms
    
    Метод String.Join: 16 ms
    
    Вывод результата (при выводе в консоль): 14000 ms
    
    Вывод результата (при перенаправлении стандартного вывода в файл): 6 ms
    

    В общем, нужно чуть больше информации, в каком именно окружении запускается программа, чтобы ответить на этот вопрос.

    Edit: единственное, что я изменил это current.Substring(0, 1) == "+" заменил на current[0] == '+' , выиграло всего ~3 ms 

    Вот код с измерениями:

    static void Main(string[] args)
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                long t1, t2;
    
                t1 = sw.ElapsedMilliseconds;
                List<int> introw = new List<int>();
                List<int> intresult = new List<int>();
                
                int min = 0;
                int x = 0;
                int n = int.Parse(Console.ReadLine());
                
    
                t2 = sw.ElapsedMilliseconds ;
                Console.WriteLine("Init: " + (t2 - t1).ToString() + "ms");
    
                t1 = sw.ElapsedMilliseconds;
                          
                
    
                for (int i = 0; i < n; i++)
                {
                    string current = Console.ReadLine();
    
    
                    if (current[0] == '+')
                    {
                        x = int.Parse(current.Substring(1, current.Length - 1));
                        introw.Add(x);
                        if (x == min)
                        {
                            while (introw.Contains(min))
                            {
                                min++;
                            }
                        }
                    }
                    else
                    {
                        x = int.Parse(current.Substring(1, current.Length - 1));
                        introw.Remove(x);
                        if (x < min)
                        {
                            if (introw.Contains(x) == false)
                            {
                                min = x;
                            }
                        }
                    }
                    intresult.Add(min);
                }
    
                t2 = sw.ElapsedMilliseconds;
                Console.WriteLine("Loop: " + (t2 - t1).ToString() + "ms");
    
                t1 = sw.ElapsedMilliseconds;
                string str = String.Join(" ", intresult);
                t2 = sw.ElapsedMilliseconds;
                Console.WriteLine("Join: " + (t2 - t1).ToString() + "ms");
    
                t1 = sw.ElapsedMilliseconds;
                Console.WriteLine(str);
                t2 = sw.ElapsedMilliseconds;
                Console.WriteLine("Out: " + (t2 - t1).ToString() + "ms");
    
                Console.ReadLine();


    16 октября 2017 г. 17:34
  • Не знаю, поможет тебе или нет, но в Python3 самый быстрый способ нахождения mex, которого я смог добиться такой:

    def mex(work_set, n):
    num_set = set(range(n + 1))
    return min(num_set - work_set)

    work_set - множество у которого надо найти mex

    n - количество элементов в изначальном множестве

    num_set - множество целых чисел от 1 до n


    • Изменено Arkhipsik 22 ноября 2018 г. 19:05
    22 ноября 2018 г. 19:05