Can't find the bug in my code

3 года назад, # ^ |

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

→ Ответить

somil_jain_120

3 года назад, # ^ |

← 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).

→ Ответить

epsilon_573

3 года назад, # ^ |

← 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.

→ Ответить

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

+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)$$$.

→ Ответить

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

3 года назад, # ^ |

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));
	}
};

→ Ответить

3 года назад, # ^ |

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).

→ Ответить