Vichitr's blog

By Vichitr, 6 months ago, In English

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

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!!!

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: Contest starts in 90 mins.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest is live!

»
6 months ago, # |
  Vote: I like it +37 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for Secure city solution?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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:

    1. Convert the grid to a directed graph with a source and sink. Add an edge from source to each entry, add an edge from each exit to the sink. For each cell, make two nodes in the transformed graph (in_node and out_node). Add an edge from in_node to out_node. Now for each valid (empty) neighbouring cell add an edge from out_node of current cell to in_node of the neighbouring cell. All edges have capacity 1. Now if the max-flow in this graph is 2 that means it is secure
    2. Another approach is — note that the above approach is essentially finding two augmenting paths between source and node. That can be implemented without the transformed graph by finding a path from a source to sink and trying from another source but keeping track of the previous path and only travelling in reverse direction in this path (similar to residual network). This requires careful implementation.

    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.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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