my code is giving 5 for the give test case and i verified it for many test cases it gave correct answer, still my code was not AC during the contest
http://www.codechef.com/viewsolution/2820678
if anyone can point out the problem, that would be great
Thanks
How would it be solved if the number of demons are around 10^8 or 10^9 ??
I am not able to get the Routine by tester can someone provide me a good source to get this concept ,please!
inline bool augment(int x)
{
for (int i = 0; i < adj[x].size(); ++ i) {
int y = adj[x][i];
if (mark[y] == stamp) {
continue;
}
mark[y] = stamp;
if (match[y] == -1 || augment(match[y])) {
match[y] = x;
return true;
}
}
return false;
}hi admin,
my code is working fine for all above mentioned testcases can you give me any testcase for which it is failing.
http://www.codechef.com/viewsolution/2821524
I did not know about any of the algorithms mentioned in the prerequisites but was able to arrive at a pretty simple logical solution. Thought I’d share it.
For killing any demon either its row has to be destroyed or its column. Now if a demon is alone in its row ie. there is only one demon in that row, then destroying that row would be useless as one attack will kill only one demon. So in that case the column will be destroyed for that particular demon. It does not matter how many demons are there in that column because this attack will kill one or more demons instead of only one if we used the attack on the row. Similarly for a column having only one demon, the optimal way will be to destroy the corresponding row for that demon instead of the column.
So the basic form of the program will be :
Implementation was a little tricky but fortunately got AC on first try. Here is the solution
http://www.codechef.com/viewsolution/2795618
Sir,There is no link for editorials in Contest page.please post it 
Even I didn’t know any particular algorithm for this problem and tried an approach of mine own and would like to share it with you guys.
Since we are asked to minimize the maximum number of attacks.initially I was maintaining a count of total number of cells containing demons.suppose the value is N.
Now while N > 0, I was repeatedly doing the following
find the count of the distinct rows and columns containing demons and determing the minimum value,Determining the minimum count(row or column) is useful because thats the maximum possible number of attacks.
Now there might be three cases 1)Count of unique rows is minimum 2)Count of unique column is minimum 3)both are equal
Let us consider that count of unique row is minimum.So,Now I search if any column exist such that if I remove that column then more than 1 such unique rows are removed(i.e some rows might exist which only contains a single demon in the same column).Now this will further decrease the minimum count of unique rows.
However if no such column exist then i search if such a row exist whose removal also removes more than one column.This will decrease the minimum count of unique columns.
However if still no such rows exist then I only remove the row containing maximum number of demons.
The same approach is followed if column count is minimum.
However if both unique column and unique row count are same then first search for columns whose removal removes more than one row or any row whose removal removes more than one column**(whichever removes the higher number of rows/columns is selected)**.or Else find the row/column with maximum number of demons and delete it…
This is a greedy approach which worked for me after I got WA after first resubmissions.
I applied a solution similar to @sikander_nsit but this one actually goes through all possible configurations. For each row there are only two possible ways to kill all demons: either all the columns of that row are covered or the all row is covered. Using recursion, for each row first cover all remaining columns and proceed to the next row and store the value, after that try to cover the all row and proceed to the next row and store the value. Return the minimum of those two values. And like @sikander_nsit said if a demon is alone in its row cover its column. If any of the demons in the current row is last in its columns then cover the all row.
if the x-coordinate and y coordinate of a point is same how can it be a bipartite
I cannot find a single test case where my solution fails! take a look at it: http://www.codechef.com/viewsolution/2813956
I know my approach is not the best one, but still can any one give me a test case where my solution fails! I have tried all the test cases - those given in the comments above, those given in problem’s comment section, the one in the editorial, and many more of my own! My code works for all of them!
Please Please ! It’s becoming increasingly difficult for me to sleep peacefully without knowing what’s wrong in this code!
How do i start learning Hopcroft - Karp algorithm ? Should i know max flow - min cut problem prior to it ? I am new to this topic. Somebody please help…
I think time complexity is O(N2.5) as:
O(E) = O(N2)
O(V0.5) = O(N0.5)
Hi Ajay, Can you please give the test case failed by my code CodeChef: Practical coding for everyone . It passes the above test case.
http://www.codechef.com/viewsolution/2823452
it would be nice if anyone could give me a test case where my code fails. It’s giving correct results for above test case and all the others in comment section of the problem
hashing is the only solution i guess.you need to map the higher values to lower values as the input of demons is maximum 1000.
Yash I ran your code for test case given in editorial it outputs 6.
hey vikrant1433. plz suggest a testcase for my solution. Its giving correct answer CodeChef: Practical coding for everyone. I dont know what is wrong.