Malay Keshav

Download Resume PDF

Malay Keshav

Netaji Subhas Institute of Technology

ACM ICPC Amritapuri 2013 – Problem C (Ganga Fort) – Solution

December 29, 2013, by malay.keshav, category ACM ICPC, All, C++, Editorial

The problem was simple and could be solved using a sliding window of size K.
Although the number of corner cases made it difficult to get the solution Accepted. As a result our team could not complete it during the onsite ACM ICPC Amritapuri 2013 regionals.

To begin solving this problem, create the following structure

struct wall{
    int pos;
    int cost;
    bool isEnd;
}fort[600005];

For each forticication (A[i], B[i], C[i]) create two elemts of wall, one for the beginning and one for the end. Let the two indexes in fort[] array be b and f.
The trick to making this problem simpler was to add two more points to the already added b and f. These points would be the point immediately after the end of the fortification and the point just before the beginning of the fortification.

Once all the points have been added, add two more points, one of them at position 0 kilometre and another one at position N kilometre.

Sort the array fort[] based on element pos.
Run a sliding window and keep track of the current cost of the forts inside that window. I implemented two functions to increment and decrement the sliding window. This was to make sure I handle the case of overlapping inputs easily.

My Final code looked as follows :

bool comp(wall i, wall j){return i.pos<j.pos;}
int t,n,m,k,ii,s,e;
bool reached;

inline long long inc_e(){
	long long ret= 0;
	e++;
	while(fort[e].pos == fort[e+1].pos && e < ii){
		if(!fort[e].isEnd)
			ret += fort[e].cost;
		e++;
		if(e >= ii || fort[e].pos > n){
			reached = true;
			return ret;
		}
	}
	if(!fort[e].isEnd)
		ret += fort[e].cost;
	return ret;
}

inline long long inc_s(){
	long long ret = 0;
	s++;
	while(fort[s].pos == fort[s+1].pos && s<=e){
		if(fort[s].isEnd)
			ret += fort[s].cost;
		s++;
	}
	if(fort[s].isEnd)
		ret += fort[s].cost;
	return ret;
}

int main()
{
	
	ios_base::sync_with_stdio(false);
	long long curCost,ans;
	cin >> t;
	while(t--){
		cin >> n >> m >> k;
		curCost = 0;
		ans = 10000*110000;
		ii = 0;
		reached = false;
		for(int i =0;i<m;i++){
			cin >> fort[ii].pos;
			cin >> fort[ii+1].pos;
			fort[ii+1].isEnd = true;
			fort[ii].isEnd = false;
			cin >> fort[ii].cost;
			fort[ii+1].cost = -fort[ii].cost;
			fort[ii+3].pos = fort[ii+1].pos+1;
			fort[ii+2].pos = fort[ii].pos-1;
			fort[ii+2].cost = fort[ii+3].cost = 0;
			fort[ii+2].isEnd = fort[ii+3].isEnd = false;
 			ii+=4;
		}
		fort[ii].pos = n;
		fort[ii].isEnd = true;
		fort[ii].cost = 0;
		fort[ii+1].pos = 0;
		fort[ii+1].isEnd = true;
		fort[ii+1].cost = 0;
		ii+=2;
		fort[ii].cost = (int)ans;
		fort[ii].isEnd = false;
		fort[ii].pos = n+1;
		sort(fort,fort+ii+1, comp);
		s = e = 0;
		while(fort[e].pos- fort[s].pos < k && !reached)
			curCost += inc_e();
		if(fort[e].pos- fort[s].pos >= k && fort[e].pos<=n)
			ans = minOf(ans, curCost);
		while(e<ii && !reached){
			while(fort[e].pos- fort[s].pos >= k && s <=e){
				curCost += inc_s();
				if(fort[e].pos- fort[s].pos >= k && fort[e].pos<=n)
					ans = min(ans, curCost);
			}
			do{
				curCost += inc_e();
			}while(fort[e].pos- fort[s].pos < k && e < ii && fort[e].pos <= n);
			if(fort[e].pos- fort[s].pos >= k && fort[e].pos<=n)
				ans = min(ans, curCost);
		}
		while(fort[e].pos- fort[s].pos >= k && s <=e){
			curCost += inc_s();
			if(fort[e].pos- fort[s].pos >= k && fort[e].pos<=n)
				ans = min(ans, curCost);
		}
		cout << ans << endl;
	}
	return 0;
}

s and e are the back and front of the sliding window. Both have a separate funciton to be incrememnted that also returns the cost of the newly encoutered/removed fortifications while incrementing.

One Comment

  1. anonymous |

    hey,
    your editorial is helpful
    but try to explain more detailedly in the sense that not just the solution but also logic by logic.
    Thanks anyway!

    Reply

So, what do you think ?