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

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

IOI tasks are now available on IOI Website.

Tasks : combo seats werewolf

Live Scoreboard

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

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

Can someone elaborate how to solve the third subtask in seats problem.

3. (20 points) H <= 1000, W <= 1000, Q <= 5000

Thanks in advance.

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

      To check a candidate for a rectangle, we have a segment tree for calculating the minimum/maximum row/column on a range. -> we can improve it to O(H+W) easily. (update r1, r2, c1, c2). Overall time complexity is O(HW + Q(H+W)).

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

      Would 10^7 segtree operations really pass?

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

    My solution involves just iterating all the positions and recomputing for each query. You will get a total of 37 points with this.

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

      how can this pass in TL ? isnt it O(q*HW) ?

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

        THe thing is you first do $$$O(HW)$$$ to compute all good prefixes (the ones which form a rectangle) when you do a swap $$$O(|a-b|)$$$ only $$$10,000$$$ prefixes can change and hence you only need to check those to update your total count of good prefixes and answer the query.

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

          I am talking about the 20pnts stask. there, the (|a-b|) = 10K constraint was not there.

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

            Oh, I see. It is right it doesnt work for the 20pts, I might have missed that. For the 20 points the number of rectangles is less than 4000 and you can compute them iteratively starting from the 1x1 rectangle and then expanding it to include the [MEX](https://en.wikipedia.org/wiki/Mex_(mathematics)) of the current rectangle. For that you only need to have the MIN in each column and each row which can be updated on every update.

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

Someone help me problem werewolf :D . I don't have any idea about this problem

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

I tried solving the fifth subtask of the problem seats (H = 1), but after reading the editorial I cannot understand how to use the lazy propagation segment tree to solve this. Can someone explain little bit on how to do this. Thanks in advance.

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

    I can try this but I'm not sure if it is correct. Let's color cells which contains numbers 1 — x black others are white. Condition for this to be beautiful rectangle is that the (number of white cells which are adjacent to black cells should be <= 2). We have to maintain this value for each prefix.

    Building : Let current number be 'x' and its position be 'pos'. Consider three case — both neighbour cells are black or one of them is black or none of them is black. For 1st case subtract 2. For 2nd case do nothing. For 3rd case add 2 to prefix 1-x.

    Updates : Let two values that are swapped are 'sm' and 'lg'. sm is smaller of them. Consider 'sm' cell. Let its initial neighbours be val_11, val_12. If val_11 is greater than 'sm' subtract 1 from prefix(1,val_11). Same of val_12. Let its final neighbours be val_21, val_22. If they are greater than 'sm' add +1 to their prefixes. Do the same for larger value 'lg'. Update prefix (1-sm) & (1-lg) seperately.

    Query : Check how many prefixes follow to above condition. You can easily check necessity and sufficiency of the condition.