Блог пользователя abdukodir

Google Code Jam 2013 — Round 1C 2013
Автор abdukodir, 12 лет назад, По-русски

Напоминаю, что раунд начнется через полчаса. Первая тысяча проходит дальше. Ссылка Предлагаю после окончания обсуждать тут задачи, всем удачи!

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Как решалась B large?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Та вроде бфс писали.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Че минусуете, я коды смотрел, у некоторых бфс) Хотя не факт, что он рабочий)

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Жадностью

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Если бы у нас была одна координата, наверное, можно было набирать двигаться в сторону точки пока мы не перейдём ей, иначе назад. А для 2 координат, какая жадность?

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

        Ну как бы понятно, что можно решать задачу независимо по обеим координатам, разве нет?

        _Upd. А. Ну да, лажу написал. Там ведь размер шага меняется. _

        А на самом деле жадность действительно работает. Сначала посчитать, сколько нужно шагов, потом — выставлять эти шаги от более длинных к менее длинным (каждый раз выбирая ту из координат, которая больше по модулю).

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится -20 Проголосовать: не нравится

          Тоесть бфс по одной, а потом по второй координате?

          → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          я решал так, у меня файл получился большой и система не приняла решение:-(

          → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

        Да, только надо начинать движение с наибольших по длине шагов. Для двух координат все также. Допустим знаем минимальное количество шагов, которое необходимо сделать. Тогда начиная с последних (наибольших по длине) шагов будем ходить в той координате, чье значение по модулю больше в нужном направлении. Для количество ходов k можно прийти в точку (x;y) если выполняется k * (k + 1) / 2 >  = |x| + |y| (т.е. суммарная длина сколько пройдем нам хватит чтобы дойти до точки) и (т.к. если у одного шага изменить + на -, то конечная четность не изменится). Этого хватает чтобы определить минимальное количество шагов.

        → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

    ( - i * (i + 1) / 2;0), (0;i * (i + 1) / 2), (i * (i + 1) / 2, 0), (0; - i * (i + 1) / 2)

    которые при покраске в шахматную раскраску имеют такой же цвет, что и вершины этого квадрата.

    Таким образом, мы можем быстро узнать длину минимального ответа. Дальше, нам надо его восстановить. Будем восстанавливать с конца рекурсивно. Мы можем прыгнуть в 4-ых направлениях. Прыгнем в том направлении, при котором сумма модулей координат меньше всего и запустимся рекурсивно от этой клетки.

    Вот код

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

World chart showing 1000 * #Remaining / #Qualification_round taken from Google CodeJam statistics page.

Chart with #Remaining only (colors are not the best)

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me whats wrong with my code for problem A which passes the small input, but not the large one? My idea is, that I count for every position the number of substring which could end at this position and sum them all up in the end...

bool isVowel(char c){
  string vowels="aeiou";
  return vowels.find(c)!=std::string::npos;
}

long long solve(string& s, int n){
  int cons=!isVowel(s[0]) ? 1 :0;
  int m=s.size();
  vector<int> v(m);
  v[0]=n==1 && !isVowel(s[0]) ? 1 :0;
  for(int i=1;i<m;i++){
    cons=!isVowel(s[i]) ? cons+1 : 0;
    v[i] = cons>=n ? i-n+2 : v[i-1];
  }
  return accumulate(v.begin(),v.end(),0);
}

int main() 
{
  int T,n;
  string L;
  cin >> T;
  for(int i=1;i<=T;i++){   
    cin >> L >> n;
    cout << "Case #" << i << ": " << solve(L,n) <<  endl;
  }

}
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why the analysis for 1B round hasn't been published yet?

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

а как на халяву реализовать C? Есть способ проще чем дерево отрезков с проталкиваением?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я написал sqrt-декомпозицию.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А координаты сжимал? там ведь 10^6 (еще на два умножить ибо со знаком)

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да, сжимал. Вот код: http://pastebin.com/VGHRMmZ8

        Или что то другое подразумевалось под сжатием? У меня как раз 2*10^6 и есть. Для GCJ это нормально. За минуту-две успевает посчитать.

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Под сжатием координат подразумевается заменение реальных значений на значения поменьше с сохранением исходного порядка значений. К примеру есть у тебя q=10^5 запросов L[i], R[i] к дереву отрезков на интервале [1..10^6]. Понятно, что для обработки запросов достаточно q * 2 т.е. 2 * 10^5 ячеек в дереве отрезков. Можно посортировать массив всевозможных значений L[i], R[i] сделать значения уникальными, и заменить L[i], R[i] на индекс соответствующего значения в сортированном уникальном массиве. тогда будет достаточным q * 2 ячеек в дереве отрезков
          Внимание вопрос: что ты называешь сжатием координат?

          → Ответить
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Я называю сжатием координат именно то, что ты сейчас описал.

            Меня просто смутила фраза "там ведь 10^6".

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Упс, не заметил. Ты мапой сжимаешь а не сортировкой :)

              → Ответить