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

Topcoder Open Algorithm Round 2D 2015
Автор chrome, история, 9 лет назад, По-русски

Привет всем!

Завтра в 09:30 MSK состоится TCO15 Round 2D.

Узнать подробности можно здесь.

Это последний шанс проидти на следующий этап.

Количество участников ограничено: 2500. Проходят только 40 участников.

Предлагаю обсудить задачи после контеста.

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

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

Are you really going to tell me that n^3 is sufficient to pass 250 :|?

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

Так как решать эту чудесную 500?

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

    Перебираем центр тяжести.
    ___Перебираем моменты, которые справа от ЦТ и закидываем их в map. Не забываем про момент, у которого длина плеча равна нулю.
    ___Перебираем моменты, которые слева от ЦТ и ищем сколько таких в map, увеличиваем ответ.

    Но дело в том, что рычаги типа "000000000" мы подсчитали много раз. Поэтому за N^2 находим все нулевые строки и уменьшаем ответ на их количество.

    UPD: я подумал, что за 500 — это 1ая задача.

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

    У нас есть N — K + 1 подходящая полоска. На каждом шаге мы можем выбрать не более K полосок и спросить, находится ли ответ в них или надо искать в остальных. Как выбрать i полосок? Спросить, находится ли шар в i-й слева коробке (1 <= i <= K).

    Будем предполагать, что нам постоянно не везет, и как бы мы не делили полоски на две половинки, нам достанется наибольшая из половин. Тогда пока N > 2K, делаем N -= K, ++ans. Затем как в бинпоиске пока N > 1 делаем N = (N + 1) / 2, ++ans;

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

      Благодарю. Печалька, так и делал, видать где-то на +-1 ошибся

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

Did anyone have an intelligent solution for the medium problem? I solved it with a very stupid one :(

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

OK, I'm generally trying not to whine that much after every contest, but this is so hilarious :P.

In the beginning of my function in medium problem I had:

    if (n >= 10 * k) {
      int div = n / k;
      int nic = div - 5;
      return nic + maxTurns(n - k * nic, k);
    }

After that I had a tailored inequality n>=3k-1, but here I put those 5 and 10 because f&*( me. And since k may be up to 1e18 this causes overflow and changing 10 to 9 results in AC :>.

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

    Yeah, I always laugh at myself when I submit a solution that turns out to be wrong and it can be corrected after the contest by a few key strokes.

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

    Can you share your solution idea?

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

      Equivalent problem: X is a positive integer between 1 and N-K+1, and you want to guess it. In each turn you choose up to K numbers and ask whether X is in the chosen set.

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

How do you solve the 250-pointer in O(n^2)?

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

    For fixed left end of interval x let's create two pointers y (balance point) and z (right end of interval). We iterate over z and slowly increase y (while side x - y is heavier than side y - z).

    Alternative solution. For interval x - z check if t[x] + 2 * t[x + 1] + 3 * t[x + 2] + ... is divisible by t[x] + t[x + 1] + t[x + 2] + ....

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

      Yes, I saw some solutions using the alternative solution you mentioned. But I did not understand it. Can you please explain that one?

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

        Interval [1, 4] is balanced when 0 = 0·t1 + 1·t2 + 2·t3 + 3·t4 or 0 =  - 1·t1 + 0·t2 + 1·t3 + 2·t4 or 0 =  - 2·t1 + ... or 0 =  - 3·t1 + .... All these equations could be written as 0 = t1 + 2t2 + 3t3 + 4t4 + k·(t1 + t2 + t3 + t4) for some k. So the question is: is this equation true for some k?

        Another explanation. Moving balance point by one changes sum of distance*weight by exactly tx + tx + 1 + ... + tz.

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

    You can loop over all balance points.

    Calculate accumulative sum of moment to the left and to the right of that balance point. Match sum of moment to the left with equal sum of moment to the right.

    The problem with that solution is that substrings consisting of zeros only get calculated multiple times because they have multiple balance points (if the substring is of length x, it will be calculated x times).

    You can compensate this by counting the number of zero substrings and decreasing length(substring) — 1 from the total answer.

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

Screencast

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

Confused about 1000... Here's what I thought:

Let pi be probability to succeed in level i, vi value of level i, Pi probability to succeed in all levels before i, Si sum of all boxes up to but not including i.

I'll assume every time we die we are forced to grab the gold we dropped, otherwise it would be equivalent to starting over. Chance of you failing level i and returning to it is qi = (1 - pi) * Pi.

Let Ei be the expected value when you reach level i for the first time.To go from i to i+1, you will grab the chest in i once, plus the chests in 1...i-1 everytime you fail i and come back. This would give .

In challenge phase I realized this is actually pretty close to being correct. Right formula is . Can anyone say where I went wrong or explain how to reach the correct solution?

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

    I actually had a similar solution at first. As a bit of a background, I came up with this problem after watching my friend play Dark Souls. The deaths in that game work similarly, in that you can go back to your corpse to collect dropped items, but there can only be at most one corpse in the game.

    Anyways, back on topic, I had a completely different approach to solve. I'm not entirely sure how to interpret your correct equation. I first define fi(x) to be the expected value we'll end up with given there is a pile of gold at the beginning of level i. We want to find f0(0), and we can also note that f0(0) = f1(0) = ... = fn - 1(0).

    Now, the key observation is that fi(x) is a linear function of x for all i, so fi(x) = ai·x + b (where b is the same for all i). Additionally, we can write the equations for all i. This gives a system of equations. You can solve this naively in O(n^3) with Gaussian elimination, but you can reduce to O(n^2) or O(n) by looking at the structure of the equations.

    I know this solution is a bit complicated, though the main reason I present this is because it can generalize to the harder version of this problem where you can have at most k piles of gold lying around.

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

Btw what is funny is that I came up with an idea of 500 problem two weeks ago when I saw this title of problem 567D - One-Dimensional Battle Ships :). I didn't read it, but in few secs I imagined a possible statement. We are playing battleships and we have a grip 1xn and somewhere there is a battleship 1xk and we have to find its exact location using least possible amount of guesses :P. So sad, that I haven't given it a thought longer than few secs, because I was at work :P.

→ Ответить