Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

0-jij-0's blog

By 0-jij-0, history, 4 weeks ago, In English,

Hello everyone,

I've been working on implementing some data structure, and the following question crossed my mind:

In terms of performance, is it better to use STL functions in my class or write them from scratch? For example, if I have a vector and I need to find it's prefix sum, do I write a typical for-loop or use the partial_sum function is the "numeric" library. (This is not my only problem but just an example to explain my question)

In terms of readability I have no doubts that STL is more convenient, but I'm not sure about performance.

Any help would be appreciated. Thank you :)

Read more »

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

By 0-jij-0, history, 3 months ago, In English,

Hello everyone,

I've noticed in the last contest (Codeforces Round #632 (Div. 2)) many people including me had this issue in 1333D - Challenges in school №41 where our verdicts changed from TLE to AC by just changing every "endl" to '\n'. You can see for yourself if you want:

TLE Submission: 75902058

AC Submission: 75903554

I knew before that "endl" does some flushing business and this usually takes (Maybe I'm wrong) time but I knew also that the following lines disable this thing: (Maybe I'm also wrong)

ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);

But I still got an issue using "endl" so can someone explain if possible how does endl work exactly and what do the lines above change about using cin/cout/endl?

Thank you!

Read more »

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

By 0-jij-0, history, 8 months ago, In English,

Hello everyone,

Consider the following problem: given a tree of N node (N <= 10^5), find the size of all subtrees of the tree, assuming the root of the tree is at node 0(or 1).

This problem is fairly easy using recursive DFS traversal of the tree, but as every recursive approach we might get a stack overflow exception if we run it on a list of 10^5 nodes for example.

So my question is: Is it possible to compute these values iteratively (ie. using iterative DFS or possibly BFS or some other approach) instead of recursively?

Read more »

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