3
Doubt in a solution
source link: http://codeforces.com/blog/entry/105106
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By abs_xyz, 22 minutes ago,
This solution uses a break statement at the end of for(int i=0; i<n; i++) loop (just after mask -= (1<<i)).
How to "prove" that this break still allows all cases to be tested?
What are some other problems that have this?
What is the time complexity (closed form?)?
My take:
If T(k)T(k) is the time complexity when there are kk zeroes in the mask, then
T(k)=(k−1)T(k−2)+O(n)T(k)=(k−1)T(k−2)+O(n)
(as there are (k-1) choices for j)
Required: T(n)T(n).
T(n)=(n−1)(n−3)...(1)+O(k2n)T(n)=(n−1)(n−3)...(1)+O(k2n)
If that break is removed, then
T(k)=(k2)T(k−2)+O(n2)T(k)=(k2)T(k−2)+O(n2)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK