KMHAMHA - Editorial

editorial
, , , , ,
21

Sir,There is no link for editorials in Contest page.please post it :slight_smile:

1 Like
22

This is what you would call as a Greedy Solution.

1 Like
23

You’re lucky to have got an AC. The official test cases were too weak to defeat your greedy algorithm.

2 Likes
24

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.

25

This is a greedy approach and I would really like to know any test case that it would fail?? I tried all the test cases till now even for the one given in the editorial its giving 5…

http://www.codechef.com/viewsolution/2802744 Here is the link of my solution…

26

SAme logic i have applied but still it gives WA. Actually my answer code is giving correct answers for all of the cases given.
kevinsogo- The question was open for these kind of solutions because time limit was 2sec and n<=1000. So a solution with complexity O(n^2) will easily pass.

27

@abhisht7 The problem is not speed, but correctness. No doubt this solution will pass the time limit, but it may not be correct in certain test cases. It’s hard to come up with a really strong test case, though.

28

This algorithm may be greedy but not in the sense that there are some missing test cases on which this will give wrong answer. It will show correct ans for any possible test case within the given limits.

29

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.

30

@sikander_nsit Here’s a case where your answer fails:

16
1 1
1 2
1 3
1 4
1 5
2 1
2 5
3 1
3 5
4 1
4 5
5 1
5 2
5 3
5 4
5 5

The answer is 4, but your code gives 5.

8 Likes
31

http://www.codechef.com/viewsolution/2828457
@kevinsogo- take a look at this solution it has passed the given test case but gives WA.

32

@abhisht7 Here’s one:

7
1 1
1 2
1 3
2 2
2 3
3 1
3 2

The answer is 3 but you gave 4.

2 Likes
33

@kevinsogo can you provide me the test case where this code fails. http://www.codechef.com/viewsolution/2827617

34

@sobhagya

6
1 3
1 4
2 1
2 2
3 2
4 1
1 Like
35

@kevinsogo Thanks man. I got it.

36

@kevinsogo thanks.

37

@kevinsogo Thanks for the failing case.

38

thank you Ahmed and Vikrant for pointing that out…now i know what my method missed… i am still very new to coding and unaware of many of the algorithm that are used and explained in editorials
i just guessed the method and implemented it…maybe my approach is what they are calling “GREEDY” algorithm and that’s why it failed…
Thanks again

39

if the x-coordinate and y coordinate of a point is same how can it be a bipartite

40

@Kevinsogo, Can u please give a case where this solution fails http://www.codechef.com/viewsolution/2826193