The-Winner's blog

By The-Winner, history, 6 hours ago, In 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.

Full text and comments »

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

By The-Winner, history, 7 weeks ago, In English

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.

Full text and comments »

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

By The-Winner, history, 15 months ago, In English

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.

Full text and comments »

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

By The-Winner, 21 month(s) ago, In English

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.

Full text and comments »

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