It_Wasnt_Me's blog

Help on F2-Pictures with Kittens TLE for unknow reason
By It_Wasnt_Me, history, 4 years ago, In English

I submit this solution which its time complexity is n*k*log(n) 72309942 I got TLE on test 35

and the constrain in the problem 1077F2 - Pictures with Kittens (hard version) n <= 5000, k <= 5000

I have no idea why my solution is TLE, I think it should fit in the time, Any help ?

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi, I haven't really looked on the code but you seem to memset inside a for; with your constraints that memset can reset up to 10^8 positions over the course of the entire program -- this is probably why you're getting TLE.

Please try to reset only as much as you need, this might fix the problem

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

    I think if I memset 10^8 in the total program it will be fine

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

Well, it's not really that surprising that a solution performing $$$5000 \cdot 5000 \cdot \log 5000 \cdot c$$$ operations did not fit into TL. But if you're determined to squeeze a solution with such complexity into TL, consider changing the logic of your segment tree. (Memsetting $$$10^8$$$ is no big deal, even $$$10^{10}$$$ can pass -- memset is extremely well-optimized.)

A function call costs a lot. So, try to eliminate recursive function calls in queries. In Russian, this is called a "bottom-up segment tree". The main idea is to start a query in the leaves of the tree, and work your way up with a while loop. Looks like this: 72366596 and performs blazing-fast on testcase 35 (<300 ms).

Usually, such trees are less functional than regular segment trees (enjoy implementing lazy propagation in them), but much faster (up to 6-7x).

→ Reply