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

Автор wilcot, история, 7 лет назад, По-английски

Very interesting contest.

But, how to solve task L, G and J?

Thanks in advance.

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

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

L: For each color check all cells in its bounding box. It will work in O(n3), because if bounding box has dimensions w and h, then there should be at least w + h - 1 cells of this color.

J: Run 1 iteration of Boruvka's algorithm.

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

    It seems that the tests are too weak.

    An O(n3logn) solution with BIT can pass problem L and an O(mlogm) solution using Kruskal can pass problem J.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    We solved problem L with O(N^3) complexity and got TLE!

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

    Maybe someone can explain L more verbosely? I can't understand neither aid nor witua's team explanations :(
    I didn't realized how to solve cases

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

      Suppose that n = m for simplicity.We want to prove that . We have that (as explained above), multiply both sides by n and obtain that .

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

      You can also approach it from the other end — instead of trying to find all boxes contained inside this box, you may try to find all boxes which contain given box.

      Just pick any row which intersects with our box and check all colors presented in this row — there will be O(n) of them, and clearly any valid box containing our box should have at least one cell in this row, because of connectivity.

      P.S. We had to optimize it a little bit (like "let's only check boxes which have area larger or equal than area of our box") because initially it gave TL.

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

    I didn't realize there is an easy solution in L and solved it in O(n2) time similarly to this problem

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

      Can you please elaborate how you do it in O(n2)? It's not clear to me even after reading the hackerrank editorial...

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

        For each component choose some point to be its' representative. Now consider some bounding box b. Calculate amount of representatives inside it with prefix sums in O(1). Some components were added to the answer incorrectly, some components were not added to the answer, but should be. Both of them going through the border of b so can be handled in O(h(b) + w(b)).

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

          Oh, so this is O(n2)? That's what we did during the content, but we thought it is O(n3). Actually makes sense, number of cells in a connected component is at least len(border) / 4, and I see a similar explanation in the thread-starting comment. Thanks!

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

G: We can take size of each pile module A + B.

Proof

Only one player can make a move on the one pile, because size of pile < A + B. Then both players should always choose the biggest pile, so we can just iterate the process.

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

How to solve The Most Expensive Gift?
Our solution was to check all possible cycles of length <= 6. And it got AC. I am not sure if it is right.

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

    At least one of the characters has to be present times. So we definitely have some subsequence with score . So checking all cycles up to 9 definitely works. We didn't reduce the bound any further as this was enough to pass.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    Hm. One can proof why we can check all periods of length <= 9. Because due to the Dirichlet principle one letter will occur  ≥ N / 3 times. So, using one letter we can reach answer N2 / 9.

    The numerator of the fraction is always  <  = N2, so to reach better answer, we should have smaller denominator. So, the length of the period shuld be  <  = 9.

    UPD: late

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    For example if S = ("ab" + "c" * 5 + "ab") * 2, then ( length(ab) * count(ab) ) ^ 2 / length(ab) = ( 2 * 4 ) ^ 2 / 2 = 32 and ( length(abcccccab) * count(abcccccab) ) ^ 2 / length(abcccccab) = ( 9 * 2 ) ^ 2 / 9 = 36

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

    Actually, c<=6 is correct bound.

    Let k be the number of times cycle of length c appears in the string. So its score is c·k2. On the other case some letter appears at least times. Solving inequality gives c ≤ 6.

»
7 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Lost 20 minutes on E thinking why TC #4 is going to be correct but not Error :D But later realised that Error can be correct.

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

How to solve I?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Count occurrences of "1" in each line and each row. Then go up->down, and later left->right, and try to cut pie. After you cut it into n^2 pieces, check every peace if it has exactly 1 "1".

    (UPD: somehow Div.2 I is not same as in Div.1 but corresponds to D)

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

    It seems we never need to take balls from three different boxes. Does anyone have a proof?

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

      I’m not sure it’s ok, but I believe there is an equivalent problem, where after you get a ball, you remove all balls with the same color, and the game ends when there are some empty set of boxes which initially had at least 2 balls of some color. This is a state game, where the state is the mask of balls that you removed. And all the final states can be covered by states where you emptied one or two boxes (and possibly some other along the way, but they are irellevant). There is only one minimax path along this graph, and it will always end up in some state where you emptied one or two boxes. Now, supposing that you have infinite computing power and you find the optimal final state to converge to, you can then apply the strategy to only clear those boxes.

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

        It should probably be

        ... when there are some empty set of boxes which ((initially had at least 2 balls of some color) or (we didn't get box from them yet))

        because it's possible there are no duplicates in boxes at all.

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

How to solve H? I got WA 41

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

How to solve C?

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

You may want to check out our short descriptions of the solutions.

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

Explain, please, how to participate Grand Prix of Ukraine ???

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

How can I upsolve the contest?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В div. 2 названия задач с H по L в ejudge не соответствуют реальным. К кому обратиться, чтобы пофиксили? Если неверные останутся в дорешивании, то будет крайне неудобно.

pic

UPD. Пофиксили. Спасибо!

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

Where can I find the problemset?