Hello.

I've just thought of a way to compute the linearization times (entry and exit) for a tree given by "the father of node $$$i$$$ is $$$p_i$$$ ($$$p_i \lt i$$$)" without the usual graph creation. This might improve the time of a submission (you no longer do push_backs) but I haven't tested. It is very niche (the number of problems where the tree is given in this way is small and those where you don't need the actual graph are even fewer) so feel free to ignore the blog. This might be well known to some people, but I never saw this so maybe someone can benefit from it.

Hello everyone!

This blog will be a collection of ideas, thoughts and personal experiences I gathered over the past ~7 years (darn, I am old). It might not contribute much to the world so feel free to skip it, but I do believe most people can get something interesting out of it. I waited on writing this until my opinion was actually worth something (still, take the following with a grain of salt or two). It is be a big wall of text (you have been warned). Sorry for taking a week to post this, University is crazy at times.

Hello!

I've seen a couple of problems where the intended solution is to use Hall's Marriage Theorem on some weird reduction to solve the problem. These are few and hard to find, so I wanted to ask you for any problems/learning materials regarding this theorem.

One example is IOI-2015/Day1/Teams (although the reduction is fairly natural).

Thank you in advance

Hello!

So I need to find some stuff on Codeforces for my Bachelor's. It is not the first time the search does nothing (well, it finds a user with the given name, but nothing else seems to work). Maybe it is time that system gets fixed. I don't know who to tag so I will only tag Mike MikeMirzayanov.

Next are some images of me searching the examples provided and 2 extra from me. If you don't think I actually searched anything and just changed the input try yourself (takes 5 seconds).

Please upvote (or comment) if you think this is an important issue that should be fixed and downvote (or comment) if you think the whole system should be removed (other search engines are decent, but not if you search something very specific). If you have another suggestion please comment.

(sorry for bad English)

Hello! I came up with the following problem, tried to solve it (faster than $$$O(N^2)$$$) and failed. I asked some other people (all much smarter than me) but neither of them could solve it.

The problem statement:

There is an array of positive integers. Count the number of even length subarrays such that the first half has the same sum as the second half.

Is it possible to solve this faster than $$$O(N^2)$$$? Maybe if we add additional constraints like the values are small or randomly generated (this one does not seem to help but I included it anyways). If it cannot be done faster than $$$O(N^2)$$$, could you provide a proof? Thank you for your time.

Some constructive problems just feel like they are the perfect examples of Gödel's incompleteness theorem. i.e. They are corect (they pass all tests), yet there is no way to prove that they are actually correct.

Hello, Codeforces!

(Disclaimer: I know very little about flows and matchings)

An interesting idea that I heard at the University recently was a greedy algorithm to find the maximum matching in a bipartite graph. The idea is simple, at each step take the node with the smallest number of unmatched neighbours (I will call it active degree) and match this node with one of its neighbours. Specifficaly match it with the neighbour whose active degree is the smallest. Update the active degree for all neighbours of the 2 nodes. Repeat until you can't match anything.

Noone in class was able to find a counter example, but we also couldn't prove that it is correct (which it likely isn't).

If anyone would be kind enough to provide a counter example / proof / link to some paper / article I would be very thankful.

I was wondering if there is any faster algorithm than O(N^2) that solves the following problem: Given a tree made of N nodes, where each node has an integer value asociated to it, find the minimum/maximum distance between two nodes whose values are coprime(if such a pair exists).

For example, given the following tree:

The minimum distance is 1 and can be obtained in multiple ways, but one of them is:

And the maximum distance is 4 and can be obtained like this:

I couldn't find anything like this by googling so I thought this is the best place to ask. Thank you in advance.