r3novatio's blog

By r3novatio, history, 2 months ago, In English

I was trying 2019 ICPC Regionals contest on codechef for practice. Found it quite stragne that out of the 8 problems, only Game of ORs is not available for submission. Although the problem statement is visible, like the rest, but there is no submit button. Is this a glitch or was it removed for some reason?

I even tried to directly find the problem on codechef (here) but it just shows "Attention: Problem is not visible now. Please try again later." whereas other problems from the contest show up just fine.

I wanted to verify my solution for the problem, does anyone know any other OJ for this particular round? Or maybe if someone from codechef community has any info on this, it'll be a huge help. Thanks!

I've posted a similar discussion (link) on codechef as well, but feel that codeforces blogs have a much wider viewership and more active response.

Read more »

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

By r3novatio, history, 6 months ago, In English

I came across this problem in which you have been given a directed graph $$$G=(V,E)$$$ with $$$|V|,|E|\leq 10^5$$$ and one additional edge can be added to $$$E$$$. What can be the maximum size of a strongly connected component in the resulting graph?

If anyone knows an approach, do share.

Thanks.

EDIT: I apologize that the $$$O(V.(V+E))$$$ algorithm that I thought would solve this also turned out to be incorrect.

Read more »

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

By r3novatio, history, 11 months ago, In English

I read somewhere that the C++ STL parital_sort function (used to find k smallest numbers) has a running time complexity of O(n.logk).

It achieves this by going through the entire data, maintaining a k-sized max-heap, throwing away the top whenever size exceeds k, and in the end printing the k remaining elements from the heap.

Can't an n-sized min-heap be used instead and then the first k smallest numbers simply extracted from it. I understand it won't remain in-place and would require additional memory.

But time complexity wise, it would take O(n+k.logn) which is better than O(n.logk), right? (assuming k to be any number smaller than n)

Then why is the O(n.logk) version preferred? Why is it mentioned everywhere and used by the std template?

Read more »

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