anubhavdhar's blog

Codenite 2021 Round 2: Discussion
By anubhavdhar, history, 3 years ago, In English

Hello all!

Thank you for participating in CodeNite 2021 round-2, hope you all had fun! We will release the results and the editorials in the coming week, and prize-winners will be contacted. Meanwhile feel free to discuss problems and ask doubts in this thread!

Regards, CodeClub, IIT Kharagpur

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

Comments Comments (8)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

Intended complexity for Queries on Grid? $$$O(Q*sqrt(Q))$$$ or $$$O(Q*log^{2}(nm))$$$

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

    The author's solution has a complexity of O(Q*sqrt(N*M)*log(N))

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

      Just doing as it was said in the statement using segtrees with lazy propagation?

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

        Yeah. Although segment trees will give high constant factor so using root(N*M) fenwick trees with range updates and queries will perform better.

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

      $$$O(N√N\log(n))$$$ Type complexity is very bad for $$$N \simeq 10^5$$$. It is almost same as $$$O(\frac{n^2}{log(n)})$$$.

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

        A Q*sqrt(Q) solution exists as well using prefix xors and square root decomposition. We kept the limits liberal to allow higher complexity solutions as well

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

just saw the mail in junk T_T

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

anubhavdhar please provide the link of editorial.

→ Reply