Malay Keshav

Download Resume PDF

Malay Keshav

Netaji Subhas Institute of Technology

ACM ICPC Amritapuri 2013 - Problem A (Arrows and Quiver) - Solution

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

This could be solved using binary search on the size S of quiver.

For every size it is required to check whether it is possible to complete the task in time C.
The tricky part of the problem was to implement the least recently used feature.
Using a Priority Queue would lead to TLE.
A linear search on the order of arrows given on input would have worked.

Create another Array LRU[n] that stores the index in the sequence TARGETS[M] of arrows/targets given in input.

Scan from left to right and update LRU based on the arrow just used/shot.
To replace an arrow and find the least recently used, maintain a pointer initialized to 0. Let this pointer be J.
When required to find the least recently used Arrow simple scan TARGETS[M] from J until

LRU[ TARGET[J] ] == J;

The index J for which the above condition is true, will be the arrow that was least recently used.

The code for binary search is :

int bin_search(){
	int lo = 1, hi = n,ret=-1,mid;
	while (lo < hi){
		mid = lo + (hi-lo)/2;
		if (isValid(mid)){
			ret = mid;
			hi=mid;
		}
		else
			lo = mid+1;
	}
	return ret;
}

The isValid(mid) checks whether the size mid for quiver can be used to complete the task in time C. 
The function finds the smallest value for Size of quiver.

bool isValid(int k){
	int ii = 0,jj=1;
	int tt =0; /* Time Elapsed */
	memset(lu, 0, sizeof(lu)); /* LRU array */
/* Hash Table to keep Track of whether the Arrow is already in Quiver */
	memset(inBag,false,sizeof(inBag)); 
	for (int i = 1; i<=m; i++) {
		if( inBag[tar[i]] ){ /* Arrow found in Quiver */
			lu[tar[i]] = i;
		}
		else if(ii!=k){ /* Quiver not Full Yet */
			tt++;
			ii++;
			lu[tar[i]] = i;
			inBag[tar[i]] = true;
		}
		else { /* Find LRU to replace */
			tt++;
			while(lu[tar[jj]]!= jj)jj++;
			inBag[tar[jj]] = false;
			inBag[tar[i]] = true;
			lu[tar[i]] = i;
			jj++;
		}
	}
	if(tt<=c) 
		return true;
	return false;
}

The overall running Time Complexity is T*O(M*log(N)).

 

2 Comments

  1. malay.keshav |

    Thats exactly the kind of binary search that has been used in this solution. The Binary search does not work on an array, instead it finds the most optimum value for the size of quiver.

    Reply

So, what do you think ?