SPECIES - Editorial

editorial
, , , , , ,
2

It can also be done with brute force with some optimizations.
Here’s my code - CodeChef: Practical coding for everyone

2 Likes
3

It should be 3^Q,right in here

there are Q^3 possible ways to replace all the questions marks with these characters, where Q is the number of question marks in the grid ?

2 Likes
4

can someone please tell me why my solution didn’t pass subtask 1 (2 <= n <= 3) but passed subtask 2 and 3 -_-

https://www.codechef.com/viewsolution/13163591

2 Likes
5

I remember trying 5 times to solve this Q…only to delete my entire code when it failed at the sample test. (And I thought only dp was a pain…:_( )

But well, first things first, time to brush up the pre-requisites then.

6

N<=50 is just too less to force a complexity of O(N^{2}).

1 Like
7

The links for tester’s and second tester’s solution are not working.
alt text

alt text

2 Likes
8

Was anybody else reminded of the concept of seed fill algorithm used to color the closed figures in Graphics . I used the similar function to determine the connected components which can either be ‘B’ or ‘P’.

1 Like
9

@coolvaibhav_94 Even i failed subtask 1.Please let me know if you find the bug.

1 Like
10

Awesome Explanation!

1 Like
11

I have no idea why my solution isn’t working. All the sample testcases specified in the problem work, and I’ve tried so many other testcases and compared the outputs on both my solution and the setter’s solution. The strange thing is that none of the sub-tasks are giving right answer. If anyone has any tricky corner cases please let me know.
My solution: CodeChef: Practical coding for everyone

1 Like
12

Hi @kingofnumbers, I realised that the test cases for this problem are pretty weak. My solution (link text) fails on many testcases such as the one below even though it got an AC.

4
…
…
…
???B

I hope such cases are overlooked in future so that only the accurate submissions get Accepted.

13

Hi @errichto, I have coded my solution exactly as you guys have explained in the editorial but my solution is failing for Subtasks 2 and 3. Can you post the test cases and expected outputs for all subtasks as the competition is now over? It can help me and many others debug our solution :slight_smile:

14

A similar problem was there in INOI this year, not really same(not complaining), which used similar concepts. I wish I solved the problem back then.

1 Like
15

Hi @errichto, My solution is also same as described in the editorial. It would be great if anyone can tell some corner cases. My solution failed on subtask 2 and 3. Corner cases of subtask 2 would be helpful as the solution is pretty straightforward for that.

16

To compute connected components we can use DSU as well. Here.

17

Congratulations. Still, I think the intended solution is easier :smiley:

7 Likes
18

Thanks. But, I think that my solution was easier for me. We all have different Point of views though.

2 Likes
19

Of course, corrected, thanks!

20

I’m glad you like it :slight_smile:

1 Like
21

You aren’t calling your check function recursively, due to which I think it gave WA for subtask 1. If you modify your check function, and call things recursively when assigning values, it should fix the issue. Luckily no such test case might be present in subtask 2 and 3, hence you survived them. :stuck_out_tongue:

Eg:

.?.
.?.
.B.