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.