Quora programming challenge

#1

Walls
Problem ID: walls
Due to COVID-19, Quora decided to split the office space into a grid of 3 × n cells and set up the walls between each
cell to isolate employees as much as possible. Unfortunately, the walls ended up affecting the productivity significantly
in a negative way. Once our employees are all vaccinated we want to break down the walls and connect all our
employees again.
The cost to break each wall is different and we would like to minimize the cost to connect people. So, given the
locations of m employees and cost of individual walls, find the minimum cost to connect employees again.
Input
Your program will receive input from standard input.
The first line contains two space-separated positive integers n and m, representing the number of columns in the grid
and the number of employees, respectively.
3 lines follow. The i-th line of this set contains n − 1 integers a1, . . . an−1. aj is the cost to break the vertical wall
between the cells in columns j and j + 1 in the i-th row.
Then, 2 lines follow. The i-th line of this set contains n integers b1, . . . bn. bj is the cost to break the horizontal wall
between rows i and i + 1 in the j-th column.
Finally, m lines follow. The i-th line of this set contains two integers ri and ci, representing the row and column of
the i-th employee’s cell.
Output
Your program should write to standard output.
Print exactly one line containing the minimum cost to connect all employees.
Constraints
• n 104
• 1 m 3n
• 0 aj 106 for all j.
• 0 bj 106 for all j.
• 1 ri 3 for all i.
• 1 ci n for all i.
Subtasks
You will get points for each subtask when you pass all of the testcases of the subtask.

  1. n 5 (14 points)
  2. n 20 (13 points)
  3. n 100 (22 points)
  4. No additional constraints (51 points)
    Sample Explanation
    This image illustrates the grid in the sample Input/Output.
    This image illustrates the optimal walls to break for the sample Input/Output.
    Sample Input 1 Sample Output 1
    5 4
    2 3 1 4
    5 1 1 1
    1 1 1 1
    5 0 1 0 2
    5 5 5 5 1
    1 1
    1 5
    2 3
    3 5
    8

Can u plz help me regarding the implementation and wor

#2

sure
what is your logic?
also share the code

#3

I have not Written the code but my logic is that can we use Dijikstras Algorithm here?/

#4

yes you can use Dijkstra’s Algorithms here

#5

CAn u plz show th eimplementation

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.