rob.kh's blog

284D: Linear complexity with big constant
By rob.kh, 12 years ago, In English

During CF Round #174 on 284D - Cow Program my algorithm didn't passed system tests. I used DFS algorithm with memorization (as in Editorials), so complexity is linear. But I got TLE in test #12. See 3341733.

In practise, I just made the following changes in my code:

1) First node isn't pushed to stack.

2) Edited this block (it's possible after first change, without this change — still TLE on test# 12)

                int cur = S.top();
                if ( cur >=2)
                {
                    res[cur] = ans;
                }

to

                int cur = S.top();
                res[cur] = ans;

After this I got AC, but time is very close to TL: 1968 ms. See 3344711

I saw that users have solved this problem with time less than one second. I don't understand why my program has big constant in linear complexity, and where is performance overhead in my program.

If anyone can help me, I will thank you ever so much.

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

»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it 
for (int i=1;i<n;i++)
{
    adj[0] = (i<<1)+1;
    v[0]=i;
    
    vector<bool> flag(2*n,false);

I suspect that the above code block is the problem. The code initializes the "flag" vector of size 2*n at each loop iteration, and there are O(n) loops. The runtime is O(n^2), which shouldn't fit the time limit (I'm actually very surprised it worked).

I made a few modifications to your algorithm (such that you can use just one flag array without reinitialization): check it out 3346847.

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

    Thank you! Hope to be more careful in future.

    → Reply