Hello Codeforces,

I invite you to participate in the **ICPC Amritapuri Practice Session 2** hosted on **CodeDrills** in coordination with **ICPC Amritapuri**. It would be a **1.5 hours** long contest having **4 problems** of varying difficulty giving you a flavor of **ICPC Amritapuri Regionals**.

**Contest Details**

- Contest Link — https://codedrills.io/contests/amrita-icpc-practice-session-2
- Date —
**27 Dec 2020**, Sunday - Start Time —
**21:00 IST** - Duration —
**1.5 Hours** - Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)

**Registration**

You will need an account on CodeDrills to participate in the contest. If you have not signed up on CodeDrills yet, do so here. If you already have an account, no extra registration is required.

**Prizes**

- Cash prizes of INR 35000 for top 15 ranks.
- 1st Place — INR 5000
- 2nd, 3rd Places — INR 4000 each
- 4th, 5th, 6th Places — INR 3000 each
- 7th, 8th, 9th, 10th Places — INR 2000 each
- 11th, 12th, 13th, 14th, 15th Places — INR 1000 each
- Only Indian participants are eligible for prizes.

I hope you will enjoy solving the problems. Please, give your feedback on the problem set in the comments below, after the contest.

Good Luck & Have Fun!

Hope to see you participating!!

Happy Programming!!!

Reminder: Contest starts in 90 mins.

Contest is live!

The contest has ended, editorial/solution is now available for all problems. Hope you enjoyed the contest.

Any hints for Secure city solution?

The key knowledge required is: the number of non-intersecting paths between a source and destination in an unweighted, directed graph is same as the maxflow between them.

To apply this to the problem, first count the number of empty cells at the edges. If it is not 4 then the answer is no. If it is 4, we need to check if we can choose 2 of the edge points as entries (sources) and the rest 2 as exits (sinks). Let us try all possible combinations of entries (there are 4C2 of them).

To check if a entry/exit assignment is valid we have two approaches based on the key knowledge stated above:

One optimization is — note that we can always swap the entries with their corresponding exits. So, we can always fix the first point as an entry and try each of the other point as an entry. This cuts run time by 2 as we need to try only 3 possibilities instead of 6.

Since maxflow is only 2, Edmond Karp should work. Even Dinic's will work. The approach 2 above worked for larger n*m but we decided to keep it small to allow standard flow approaches to pass too.

What would be the time complexity for Dinic's Algorithm for this problem? Would it be (n*m*sqrt(n*m))?

That is the general case complexity. For graphs with only unit capacities it is much less — O(m*sqrt(n)).