riadwaw's blog

TopCoder SRM 543
By riadwaw, 12 years ago, In English

Today, 20:10 MSK

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

How to solve 500?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Динамика. Прошли i рек, оказались на такой высоте. Переходы либо на 1 вверх по суше, либо по морю. Это какой-то len^2*m. Осталось заметить, что работают два указателя, потому-что что-то выпукло куда-то.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Вечный вопрос: а как заметить что "что-то выпукло куда-то"?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Ну это же корень. Он всегда выпуклый. Дальше надо пописать какие-то оценки и увидеть, что если нам сейчас выгодно опуститься на 1, то в прошлый раз это было еще выгоднее. А еще почему эти коментарии на английском? Пошли в другую ветку.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Мое решение на чем сломал? TL?

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Да. Просто вбил большой случайный тест. С учетом того что тернарник казалось бы вообще не работает, на чем-то бы свалилось.

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -23 Vote: I do not like it

        // эта ветка — английская.

        Сразу скажу, что сам не успел дописать задачу.

        Я заметил это так: нарисовал карту, хочу пройти в точку (x, y) из (x - 1, 0). Тогда я могу в неё попасть тремя способами: пройти по острову x - 1 расстояние y, затем по воде (получается перпендикулярно) расстояние width[x - 1], пройти по воде перпендикулярно расстояние width[x - 1], потом по острову x расстояние y, причём эти два значения будут равны (думаю, что это очевидно), либо пройти по "гипотенузе" расстояние . А потом вспоминаем, что в прямоугольном треугольнике длина гипотенузы всегда меньше суммы длин катетов, ну и интуитивно понимаем аналогию.

        P.S. Понимаю, что сказал полный бред, но это были всего лишь мои мысли :)

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Alternative solution. At first assume we got from 0, 0 to sumWidths, 0. Take this time as an answer. Then length times do following — increase difference between indices of source and destiantion ports on some river (or walk 1 segment anywhere). Choose river where such operation would lead to smallest increase of answer. Notice that for this river next increase would be bigger, so our algorithm is correct

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    А еще оказывается работает решение добавить подъем на 1 там где он меньше всего нагадит length раз. Видимо опять таки из за того что корень — очень хорошая функция.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Если быть точным, то потому, что в каждой реке это число увеличивается после операции

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        А почему из того, что для каждой речки это число увеличивается, следует, что такая стратегия оптимальна?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Потому, что мы тогда возьмем length самых маленьких чисел

          → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Another alternate solution. This problem is equivalent to knapsack problem (we want to take L meters up). So we have width.size() + 1 of objects, width.size() of there is rivers and one is the object that correspond to moving up (his width is 0, and his speed is walk). So we can proof that it's possible to solve this problem in such way: For all objects put into array L values timeToGo(width, Y+1, speed) — timeToGo(width, Y, speed) (1 <= Y < L), than sort this values, and sum first L values from array.

    So this sum is the answer to the problem without sum for all rivers timeToGo(width, 0, speed).

    timeToGo(w, y, s) = sqrt(w*w + y*y) / s.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My solution (Java) with 1 * n * length sqrt calculations works appr. 2 seconds and was challenged (got TL). I suppose it would get AC written in c++. The question is, how to avoid such number of sqrt's? Am i missing something?

UPD. It got TL as I forgot to cast width[i] * width[i] so there was an overflow, and NaN values produced time limit on max test. With cast it works about 300ms, which is totally comrehensible.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Egor's solution requires only O(n + length) square root calculations for example.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, and that solution is great. Mine dealt with two pointers, and I already found a couple of java solutions with almost the same code which passed systest, so anyway it's my fault.

      → Reply