### pks18's blog

By pks18, history, 19 months ago,

While trying the problem Tree Matching, I figured out that onw way to solve the problem could be to use network flow by adding a source and sink after splitting the tree into two partite. Otherwise, another way could be to use Hopcroft-Karp Algorithm to find the maximum matching.

There is no article written on this topic on CP Algorithms website. And on other webisites, I didn't find a implementation as clear and general as they are on CP Algorithms.

It would be great if some clean and documented implementation of this code could be shared (may or may not be a blogpost on Codeforces).

• +3

By pks18, history, 3 years ago,

The question is as follows:-

We are given n coordinates in the form of (xi,yi) for ith coordinate. Then we need to find the number of lines passing through atleast three points?

I have a feeling it would be n^3 approach with checking of slopes, but I am not able to boil down it to code. I am particularly facing problem in the case when 4 or more points fall in the same line. How to stop double counting?

Help would would be greatly appreciated.

• +9

By pks18, history, 3 years ago,

I recently (almost a week ago) gave Google's Online Challenge. There was an interesting problem in Graph Theory stated as follows:-

You are given an undirected weighted graph of n vertices and m edges. There are q queries where each query consists of a source, a destination and a weight w. For each query print ‘1’ if there exists a path from source to destination where each edge in the path has a width less than or equal to w.

Constraints:-

n,m,q<=10^5


The constraints were particularly interesting. For a beginner like me, I couldn't think of anything but a brute force solution of BFS with a restriction that the edge weight should be less than w. Clearly, this O(V+E) for each query and quickly goes into a TLE once number of queries becomes large enough. So, how do we solve this problem? Even precomputing looks difficult because each query had a different value of weight w. So, how do we solve it? I have a feeling from the constraints some kind of log factor must come into picture but I am unable to determine what would be helpful.

• +6

By pks18, history, 3 years ago,

I was solving the problem set of Code forces when I stumbled upon this question Protect Sheep. The question was pretty simple if we simply place dogs on all the empty spots.

But if we were supposed to minimize the number of the dogs used to protect the sheep. How do we solve it then? There seems to be many cases to handle. Any kind of help would be appreciated!

• +2

By pks18, history, 3 years ago,

I was solving a question from testing round 14 called Problem 910A. my code is working perfectly when I run it in my PC. But when I submitted it, I received a WA. On checking the testcase, I found that the answer which I get when I run it manually on my PC or on Codeforces Custom Test IDE, I get the correct answer. I am attaching the my submissions, please help. I am totally confused why the same code is giving different outputs at different times. 85273487 85273212 85272698 Please help!

• -6

By pks18, history, 3 years ago,

I was testing the speed of Dijkstra's Algorithm on my PC. For this purpose, I was generating large size graphs(weighted) using this test case generator. But it seems it is not capable of generating graphs with 10k vertices with around 1 million edges. Can anybody suggest how can I generate such large weighted graphs? Thanks in Advance :)

• +8