Foysal_Ahmmed's blog

By Foysal_Ahmmed, history, 7 months ago, In English,

Problem Description:

Farmer John owns b bulls and c cows. He also owns b+c fields where each field can hold either one cow or one bull. The fields are located in an area with many hills, so for some pairs of fields the animals in those fields cannot see each other. Unfortunately, his bulls really do not like each other, and neither do his cows. To avoid making any animal angry, John would like to assign the animals to fields such that no two bulls can see each other and no two cows can see each other. Help determine if John can assign his bulls and cows in such a manner.

Input

The first line of input contains n, the number of examples. The first line of each example contains integers b, c, and a where 0 ≤ b, c ≤ 1000 are, respectively, the number of bulls and cows and 0 ≤ a ≤ 20, 000. The next a lines of input each contains two numbers u and v which indicates that animals placed in fields u and v can see each other. Fields are numbered from 1 to b + c.

I think that it is a bicoloring problem . If bicoloring fail ans must be no ,otherwise yes. But it give Wrong Answer.I got some tag for this problem DP+Knapsack .But I can not understood why need dp and knapsack .

Read more »

 
 
 
 

By Foysal_Ahmmed, history, 7 months ago, In English,

I have just started to learn Sprague-Grundy Number. Now trying to solve lightoj 1296 — Again Stone Game this problem.

Alice and Bob are playing a stone game. Initially there are n piles of stones and each pile contains some stone range[1,10^9]. Alice start the game and they alternate moves. In each move, a player has to select any pile and should remove at least one and no more than half stones from that pile. Who will win the game.

I think it's not possible to solve by Dynamic Programming. Need to find out a pattern. I just calculate some values Sprague-Grundy Number and find a pattern for even number that each even number Sprague-Grundy Number is its own half. (I using term SGN as Sprague-Grundy Number). Like it – SGN(2) = 1, SGN(4) = 2, SGN(6) = 3, SGN(8) = 4.........

For some odd numbers it SGN(1)=0, SGN(3)=0, SGN(5)=1, SGN(7)=0,SGN(9)=2......... But I could not find out any pattern for odd numbers. I can not understand that my observations is right or wrong. Looking help for odd values pattern or a new hints to solve this problem.

Thanks in advance………………………….

Read more »

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