boi1234's blog

By boi1234, history, 3 years ago, In English

On problem 1519C - Berland Regional my submission 125877791 passes test 3 which across all subtests has an n of 200000 in 500ms. On the other hand test 4 has 1 subtest with the same total n of 200000 and that time limits. Why is this?

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you have numbers $$$a, b \in \mathbb{N}$$$ then $$$a^2 + b^2 \le (a+b)^2$$$ so if you have 1000 test cases where each test case has $$$n \approx 500$$$ and if your algorithm runs in $$$O(n^2)$$$ then it will give you $$$\approx 1000 * 500^2 \approx 1.39 * 10^8$$$ operations which shouldn't, but technically might fit into TL. While if you have 1 test case with $$$n = 2*10^5$$$ then your algorithm will do $$$\approx 4*10^{10}$$$ operations which is way too much.

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

This segment of your code:

for(ll i=0;i<n;i++){
   pre[i].push_back(a[i][0]);
   total_sum+=a[i][0];
   for(ll j=1;j<(ll)a[i].size();j++){
        total_sum+=a[i][j];
        pre[i].push_back(pre[i][j-1]+a[i][j]);
   }
}

seems to have a time complexity of $$$O(N^2)$$$. In order for the code to pass, you need to optimize it to $$$O(N \log N)$$$ at least.

Edit: Actually the segment above is fine, I misunderstood the code and turns out sum of all a.size() is at most $$$n$$$. However this code has $$$O(N^2)$$$ complexity:

for(ll i=0;i<n;i++){
    for(ll k=1;k<=n;k++){
        ans[k]-=pre[i][((a[i].size()-1)%k)];
    }
}

You need to optimize this part.