Statement:

There are $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$, and there is an exit that lies after room $$$n$$$.
There are $$$a_i$$$ $$$(1 \le i < n)$$$ doors numbered from $$$1$$$ to $$$a_i$$$ connecting room $$$i$$$ to room $$$i+1$$$, and $$$a_n$$$ doors numbered from $$$1$$$ to $$$a_n$$$ connecting room $$$n$$$ and the exit.

Stanley starts at room $$$1$$$. Each time Stanley is at room $$$i$$$, he chooses one of the $$$a_i$$$ doors and goes through it to room $$$i+1$$$ (or to the exit if $$$i=n$$$).

Each time Stanely reaches the exit he gets an ending, and two endings are considered different if the path Stanely took in each of them is different (i.e. there exists a room $$$i$$$ such that Stanely choose different doors while he was in room $$$i$$$ in the two paths)

But there is a twist, there are $$$k$$$ constraints, the $$$j$$$-th $$$(1 \le j \le k)$$$ has $$$4$$$ values $$$x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$$$ $$$(1 \le x_{j,1} < x_{j,2} \le n),$$$ $$$(1 \le y_{j,1} \le a_{x_{j,1}}),$$$ $$$(1 \le y_{j,2} \le a_{x_{j,2}}),$$$ meaning that if Stanely on his path took door $$$y_{j,1}$$$ while he was in room $$$x_{j,1}$$$, then he can't take door $$$y_{j,2}$$$ when he is at room $$$x_{j,2}$$$

Stanley wants to find the number of different endings he can get, since this number can be large he wants to find its value modulo $$$10^9 + 7$$$

Subtasks:

• Subtask $$$1$$$: $$$(1\le n \le 10),$$$ $$$(k = 0),$$$ $$$(1\le a_i \le 10)$$$

• Subtask $$$2$$$: $$$(1\le n \le 10),$$$ $$$(0\le k \le 10),$$$ $$$(1\le a_i \le 10)$$$

• Subtask $$$3$$$: $$$(1\le n \le 20),$$$ $$$(0\le k \le 20),$$$ $$$(1\le a_i \le 10^5)$$$

• Subtask $$$4$$$: $$$(1\le n \le 20),$$$ $$$(0\le k \le 2\times 10^5),$$$ $$$(1\le a_i \le 10^9)$$$

You are given a chocolate bar represented as a grid of size $$$N$$$x$$$M$$$, find the number of ways you can finish the chocolate bar by eating it.

When eating the chocolate bar, each time, you remove one block from the grid which is not surrounded by another chocolate block which has not been eaten yet from all 4 directions

Example : Consider the $$$3$$$x$$$3$$$ chocolate bar below, corners colored in Dark Brown and the center in Red, every chocolate block is accessible to be eaten in the very beginning except the center, it becomes accessible if at least on the corners was eaten

What is the best complexity that can be achieved in terms of $$$N, M$$$? and how?

Edit : Sorry for not mentioning that, but the best solution I have came up with myself so far is bitmask dp in $$$O(N*M*(2^{(N*M)}))$$$

Note : I noticed this blog got Privated, why is that? I reuposted it

• Which website/application do you think is the best among those :

1. Codeforces
2. Facebook
3. Instagram
4. Twitter
5. Youtube
6. Telegram
7. Discord