m.radwan's blog

By m.radwan, 7 years ago, In English

Hello Everyone,
I wanted to share my competitive programming blog with you, it contains some tutorials that some of you might find useful or interesting solveit.quora.com.
Any feedback is well appreciated

Read more »

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

By m.radwan, 7 years ago, In English

Dear All,

Like any other contestant in ACM-ICPC or online competitions, you probably passed by e-maxx.ru/algo. The website is a very valuable algorithm bank along with explanation and sample codes. The only problem is that it's all in Russian. I am sure Google translate can do a proper job in the easier algorithms but in the harder ones every word counts and it's usually not very sufficient.

We have been thinking how valuable it would be if we have such a bank translated into English. To do that we basically need a Russian coder that knows English well and willing to do it. Translating all the algorithms will probably take some time and possibly nobody will be willing to give that much time with no return.

The plan we have in mind is the following:
- We find a good Russian coder with good knowledge of English willing to do the translation and ask him how much money he can do that for.
- We launch a kickstarter campaign targeting anybody who will benefit from the translation (which is basically any non Russian English speaking contestant) to collect the needed amount of money.

All would be public and transparent. Do you think that would be successful??

Are you willing to either do the job (if applies) or fund the campaign?

Please let us hear from you.

Read more »

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

By m.radwan, 8 years ago, In English

Hello everyone I need help solving this problem LA 6652 Game Of Thrones The problem comes originally from ACM Regional contest (Dhaka 2013), however in the contest problem set the constraints were smaller (K≤21) which makes the problem easier, however in the version on LA K≤50.

Anyway here are my findings so far

WARNING SPOILER BELOW!

  • No cycle exists in the solution, if there were any we can safely remove and obtain a solution of smaller value.
  • The solution can be represented as a set of paths, where each path starts and ends at two different nodes from A, if we choose those paths optimally those paths will not overlap on an edge(s) otherwise we can safely remove this edge(s) and obtain a solution of smaller value.

Now the problem becomes minimum cost perfect matching in a complete graph where the graph is formed by the nodes from A, and the edge cost between two nodes is the length of the shortest path between them in the original graph.

I know that this problem can be solved in polynomial time however the algorithm is tedious to implement and hard to understand, so I was wondering if there's another solution which maybe makes use of the properties of the new graph.

Thanks in advance

Read more »

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