When I was a little child I learned a lot (indirectly via the website which also have a community-driven english transation) from e-maxx.(Orz).

In particular, there is a post about Dijkstra on sparse graphs (English version. It is mentioned there that priority_queue is based on heaps, thus has smaller hidden constant then set which is based on RB-trees. Explanation makes perfect sense.

I got back from quite a long break from CP and checked the recent Educational Codeforces Round 102 (Rated for Div. 2) for a warm up. There was a nice problem 1473E - Minimum Path authored by Neon which required Dijkstra's algorithm. So I used the priority_queue based one from my template 105061903 and got TLE 61. I thought of several bad words and started to optimize. Eventually, I tried the set-based solution and got AC 105066945. For your convenience, there is a diff between the submissions:

Is it some other hidden bug in my code, or is set-based Dijkstra works faster then priority_queue one? When and why?

Hello,

I had to learn Ukkonen's algorithm in order to solve this question. So I searched something found this, and this, and this, and this. Decided that I understood theory and could proceed to implementation of this problem.

I tried to implement it readably and reliable and tested it a bit and received TL afterwards optimized and got TL with this, so I rewrote code and still got TL and my vacation run to an end.

Can you please help me and tell what am I missing (seems like major difference from e-maxx's implementation is that I am calculating suffix links not on the fly but when coming to next vertex (it is suffix link of previous)

Thank you and kiitos

This draft is 4 years old, so its time to post it, especially, since I found a bug in the code.

I just returned to violet and decided it is time to increase my contribution before next div 1 contest makes me blue again. had bad luck to learn binary search from informatics.mccme.ru (I think they rewrote article from that time but the irreversible damage was done and even after explaining tricks by my friends AndrewB330 and nagibator I still can not write binary search without bugs). And I was searching for easy tricks to use lower and upper bound functions of the STL library (yes I am talking about C++ only) to solve binary search problems. Anyway, you usually need to find the first element satisfying or not satisfying some conditions. So you can easily implement your "Iterator" class with difference, prefix increment, increment, not equal operator and dereference operator:

struct BinarySearchIterator : public iterator<random_access_iterator_tag, bool>
{
  long long value;

  typename iterator_traits<BinarySearchIterator>::difference_type operator - (const BinarySearchIterator &it) const { return value - it.value; }

  BinarySearchIterator& operator ++() { return *this += 1; }

  BinarySearchIterator& operator --() { return *this += -1; } // msys

  BinarySearchIterator& operator +=(typename iterator_traits<BinarySearchIterator>::difference_type n) { value += n; return *this;}

  bool operator != (const BinarySearchIterator &it) const { return value != it.value; }

  bool operator*() const {
    /* code here */
    return true;
  }
};

Since I wrote this post, Python has entered our lives. And those who use it for CP probably aware that one of the rare things from STL which exists in Python is the bisect module with bisect_left (equivalent to lower_bound) and bisect_right (equivalent to upper_bound). So we can abuse it to do binary search as well:

class BinarySearchCollection(object):
    def __init__(self, length=None):
        self.__length = length

    def __len__(self):
        return self.__length

    def __getitem__(self, item):
        raise NotImplementedError()

List of problems:

• 1251D - Salary Changing

• Blindfolded Bullseye

• New Elements: Part 2

Enjoy.

I suppose as a person with rating terribly going down this post will receive plenty downvotes, but still.

I suppose anyone, who used hacking with generator (and considering limit on file size for handmade tests, when you are hacking for TL another ways are impossible), hates messages like "Invalid input Unexpected character #13, but ' ' expected". Personally I receive them every time, and considering pending time... In other words it almost impossible to hack someone with generator (for me, do you have any tricks?)

Hello everyone! The question arose, while solving 100783D - Book Club. Somehow it was night when we read it, and first thought that got to my mind: in unit network with source, edges from source to all A's, edges from A to B and from B's to sink, flow should be equal to number of people. I started to search max flow algorithm which suits to limits and found out that Dinic used for solving bipartite problem takes O(sqrt(V)E) (Wow this is the case with E maximum N we can get O(N^1.5)). Ok I wrote Dinic almost like e-maxx it and it got as far as test 13 with TL.

Ok, said AndrewB330, why didn't you wrote Khun. I thought about it, and agreed that yes O(N^2) suits me. And got bloody AC.

The question is: what so horrible I did in Dinic or what should I have done so it worked as expected?

Thank you, community.

Hello, everyone! Once, I was learning about Eulerian path and algorithm of it's founding, but did not find then the appropriate problem on online judges. Now I am solving another problem, where finding Eulerian cycle is just a part of task, and I would like to check my skills in realization of the algorithm on some simpler problem.

The question is: can anyone recommend me problems connected with finding Eulerian path?

Thank you in advance!