CAC103 Tunnel or Road- CRACK-A-CODE 1.0 EDITORIAL


Tunnel or Road

Author: Mayuresh Patle
Tester: Mayuresh Patle
Editorialist: Mayuresh Patle




Brute Force, Observation


Towns are linearly arranged and numbered in sequential order. Each town t_i has tunnels connecting it to towns t_{i-M} and t_{i+M} (if these towns exist), which can be used without any tax. Roads connect a town t_i to the towns t_{i+1} and t_{i-1} (if these towns exist), but tax of using a road is X units. N people are currently located in some random towns. We have to find the minimum tax required to get all of them in same town.


Get all the people in M continuous towns for free by using tunnels. For each of these towns calculate the tax required to bring everyone in that town. Output the minimum calculated tax.


We can bring all the people in M continuous towns by using the tunnels. How?
We can keep on moving the person from town t_i to town t_{i-M} while i \geq 0. Now we have everyone in available in towns t_0 to t_{M-1}. By doing this we are moving a person from town t_i to town t_{i mod M}.
Now, we must bring all of them in one of these towns. By using brute force, we will now calculate the minimum road movements required get everyone in each of these towns.
If i-th town has c_i people, we can move them to j-th town in two ways

  • move one by one town in the direction of j-th town from i-th town by using the roads. This will need |i - j| road movements for each person.
  • move M towns in the direction of j-th town from i-th town, by using the tunnel, then move back one by one town to the j-th town by using the the roads. This will need M-|i - j| road movements for each person.

We will consider the way with minimum number of road movements, say min. Now for c_i people we need min*c_i movements.

We will calculate this for all the M towns, and keep the track of minimum total road movements in some variable, say ans. Now we know the minimum number of road movements and each road movement needs X units of tax, so the total tax will be ans*X units.

Time Complexity: O(N + M^2) for each testcase


Setter's Solution
using namespace std;
typedef long long ll;
int main()
    ll t,n,m,x,i,j,ans,d,tax;
        vector <ll> count(m,0);
        while(n--) cin>>i,++count[i%m];
    return 0;