Can't find the bug in my code

4 years ago, # ^ |

Yeah, I checked for that but I am dividing the length by 2 at every call so I don't see that happening.

→ Reply

somil_jain_120

4 years ago, # ^ |

← Rev. 3 →

actually your time complexity is O(n^2).

Because you are calling recursion 4 times. So, you are forming a tree with height log2(n) with 4 calls everytime.

hence, net complexity = 4^(log2(n))=n^2.

(Feel free to Correct me if I am Wrong).

→ Reply

epsilon_573

4 years ago, # ^ |

← Rev. 2 →

Yeah, that seems to be the case. Maybe use memorization to try and speed it up, if you cannot reduce number of recursion nodes.

→ Reply

4 years ago, # ^ |

https://codeforces.net/contest/559/submission/29503685 this code is almost same as mine and it got accepted. It has the same recursive calls.

→ Reply

4 years ago, # ^ |

+15

There is a tiny (but very significant) difference in the two codes: in the accepted version they use the functions directly in the return, but in yours you calculate the values before. The reason this matters is because in the accepted version, if the first part of the and statement returned false, the code won't evaluate the rest of the and statement, because it knows that the expression will be false (because x&0 = 0 for any value x). This means that in the accepted version, there is a good chance many of the recursive calls are actually skipped. Here is an accepted version of your code, where I explicitly skipped the second recursive call if the first one failed. 108130742 Note that you shouldn't rely on this in the future because it's an unproven heuristic, and I'm pretty sure it's possible to make a hack test that causes the code to run in $$$O(n^2)$$$.

→ Reply

4 years ago, # ^ |

I tried submitting using the same fix and still this fails. Did I miss something? 108130830

→ Reply

4 years ago, # ^ |

Changing the substring comparison back to the comparing them letter-by-letter made it pass pretty comfortably: 108131602. There are two reasons that this could've happened:

Bad constant: because you first have to create two separate strings from the substrings and then compare them instead of just one pass through the string, this could have a 3x worse constant factor.
Early breaking: when there is a mismatch, the for loop automatically breaks, possibly also making it faster.

→ Reply

4 years ago, # ^ |

Oh okay okay, got your point!
Thanks! =)

→ Reply

4 years ago, # ^ |

oh I got it. but I am still getting tle at 91 https://codeforces.net/contest/559/submission/108131756

→ Reply

4 years ago, # ^ |

It passes if you submit it in 64 bit: 108132405. In my experience, in most cases 64 bit is better (it's often faster and it has things like 128 bit ints), so if I were you, I would submit everything in 64 bit.

→ Reply

4 years ago, # ^ |

thanks a lot man! Is there any downside to submitting in 64 bit?

→ Reply

4 years ago, # ^ |

There are none that I know of, but I can't definitively say that 64 bit is always better. Maybe someone who understands the nuances of both better can comment here.

→ Reply

4 years ago, # ^ |

I once faced an issue with the 64 bit compiler while making a comparator:

This passes in both 14,17 but fails in 17(64-bit)

struct cmp
{
	bool operator()(pair<lld,lld> a, pair<lld,lld> b)
	{
		return (((a.st-a.st/2)*a.nd) > ((b.st-b.st/2)*b.nd));
	}
};

This change fixes it

struct cmp
{
	bool operator()(pair<lld,lld> a, pair<lld,lld> b) const
	{
		return (((a.st-a.st/2)*a.nd) > ((b.st-b.st/2)*b.nd));
	}
};

→ Reply

4 years ago, # ^ |

Ah yes, I forgot about that. That is an example of the issue mentioned in this blog, where 64 bit c++ has weird precision issues when working with doubles. I think it's still worth it to submit in 64 bit, especially since it's possible to fix this issue by adding one line to your template (see the blog).

→ Reply