Topcoder Open Algorithm Round 2D 2015

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

Автор chrome, история, 9 лет назад, По-русски

Привет всем!

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

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

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

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

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

topcoder, tco, 2d, 2015, tco2015

chrome
9 лет назад
24

Комментарии (24)

Написать комментарий?

Swistakk

9 лет назад, # |

+52

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

→ Ответить

Egor

9 лет назад, # ^ |

It would be rather strange

→ Ответить

Swistakk

9 лет назад, # ^ |

+15

And it got AC... Do I have to mention that I tried hacking it and got -25? (solution of sekiye)

→ Ответить

wrdsaj

9 лет назад, # ^ |

-37

O(N(N + 1)(2N + 1) / 6) = O(N³) ( ͡° ͜ʖ ͡°)

→ Ответить

Egor

9 лет назад, # ^ |

Well, this is very fast N^3. Everything is in cache and so on

→ Ответить

Kvark161

9 лет назад, # |

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

→ Ответить

IgorKoval

9 лет назад, # ^ |

← Rev. 3 →

-8

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

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

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

→ Ответить

HellKitsune

9 лет назад, # ^ |

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

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

→ Ответить

Kvark161

9 лет назад, # ^ |

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

→ Ответить

I_love_tigersugar

9 лет назад, # |

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

→ Ответить

Swistakk

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 :>.

→ Ответить

tafit3

9 лет назад, # ^ |

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.

→ Ответить

saurabhverma

9 лет назад, # ^ |

← Rev. 2 →

Can you share your solution idea?

→ Ответить

rng_58

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.

→ Ответить

satyaki3794

9 лет назад, # |

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

→ Ответить

Errichto

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] + ....

→ Ответить

satyaki3794

9 лет назад, # ^ |

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

→ Ответить

Errichto

9 лет назад, # ^ |

+11

Interval [1, 4] is balanced when 0 = 0·t₁ + 1·t₂ + 2·t₃ + 3·t₄ or 0 = - 1·t₁ + 0·t₂ + 1·t₃ + 2·t₄ or 0 = - 2·t₁ + ... or 0 = - 3·t₁ + .... All these equations could be written as 0 = t₁ + 2t₂ + 3t₃ + 4t₄ + k·(t₁ + t₂ + t₃ + t₄) 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 t_x + t_x + 1 + ... + t_z.

→ Ответить

satyaki3794

9 лет назад, # ^ |

Yes, I understand now. Thanks for the help.

→ Ответить

TsunamiNoLetGo

9 лет назад, # ^ |

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.

→ Ответить

Egor

9 лет назад, # |

+13

Screencast

→ Ответить

ffao

9 лет назад, # |

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

Let p_i be probability to succeed in level i, v_i value of level i, P_i probability to succeed in all levels before i, S_i 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 q_i = (1 - p_i) * P_i.

Let E_i 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 $\text{[math]}$ .

In challenge phase I realized this is actually pretty close to being correct. Right formula is $\text{[math]}$ . Can anyone say where I went wrong or explain how to reach the correct solution?

→ Ответить

Lewin

9 лет назад, # ^ |

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 f_i(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 f₀(0), and we can also note that f₀(0) = f₁(0) = ... = f_n - 1(0).

Now, the key observation is that f_i(x) is a linear function of x for all i, so f_i(x) = a_i·x + b (where b is the same for all i). Additionally, we can write the equations $\text{[math]}$ 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.

→ Ответить

Swistakk

9 лет назад, # |

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.

→ Ответить