Problem Statement

Given an n × m chessboard, try and place as many rooks as possible on the board in such a way that the number of rooks on each row is equal to the number of rooks on each column (it is allowed for two rooks to attack each other). You are prohibited from placing the rook at some given locations on the board.

Source

This problem was an exercise left to the reader on a Topcoder tutorial click.

After many attempts, I am unable to formalise a solution. To be more specific neither was I able to formulate this problem as an instance of max-flow, nor was I able to model it as an instance of min-cut.

My observations

• The total number of rows that contain a rook must be equal to the total number of columns that contain a rook
• Could we possibly binary search for the solution and construct a bipartite graph for each candidate solution in the binary search?

Hello,

I found this weird dynamic programming solution to the following Hackerearth problem.

The problem setter's solution uses network flow to solve the task and I was able to understand that after reading the editorial. On the other hand, I am unable to come up with a proof of correctness for the dp solution which I have linked above. This has been in my TODO list for over a month now and it feels as if I am not getting anywhere near the proof.

To be honest, it feels counter intuitive that a task that uses network flow can be solved with dynamic programming but I could not come up with a counter example either.

However, I was able to prove the following lemma that hints that the dp solution might be correct but this is about as far as I reached —

If for each index 1 ≤ i ≤ n we can generate a segment that starts at i using the given queries then your opponent can discover the parity of each element from i = 1 to n

Any kind of help will be appreciated :)

Hi

I am solving a problem that is conceptually simple.

Given an integer x, such that 1 ≤ x ≤ 10¹⁷, check if v = 5x² + 2x + 1 is a perfect square. I have solved this using Big Integers and long doubles in C++ (with a binary search to find the root) and used PyPy to get it accepted in Python but I did not receive satisfaction in solving it this way.

Also, __int128 do not work on SPOJ for some reason :/

I think Big Integer may be an overkill for such a problem and the uncertainty with floating point precision is never re-assuring. Hence, my question is, is there any way to solve this problem without Big Integers or long doubles in C++?

Thanks

I was trying to solve problem A from the recently conducted ICPC regional contest.

My approach was to use the following DP transition state — dp(i)(j) denotes the number of ways to assign labels to the subtree rooted at node i such that node i is given the label j.

I came up with the following transition for this state

where is the binomial coefficient, l_i and r_i are the left and right child of i and s_i denotes the size of the sub-tree rooted at i.

According to me the time complexity of this algorithm is if I use prefix and suffix sums in the summation but it seems that this solution gets accepted. Can someone help show me how?