zoooma13's blog

IOI 2018 Day 1 Tasks
By zoooma13, history, 6 years ago, In English

IOI tasks are now available on IOI Website.

Tasks : combo seats werewolf

Live Scoreboard

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

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

Thanks in advance.

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

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

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

      Would 10^7 segtree operations really pass?

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

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

    Solution
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

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

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

        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.

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

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

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

            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.

            → Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

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

    Read the editorial at the official IOI website.

    LooOoOoOOOooOoLooOooOooOooL. LMAO. ROFL.

    Are you even too lazy to google that?

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

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.

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

    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.

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

      Thank you for your reply, just to ask, in your update function by val_11 and val_12 do you mean the left and right neighbours of the current position?

      → Reply
»
5 months ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Can someone write editorial of day1 problem A please!

→ Reply