সোমবার, ১৪ ফেব্রুয়ারী, ২০১১

SPOJ - RACETIME


Problem description

You are given an array (size <= 100000). There are 2 kind of operations you need to perform

1. Change the value at some position.
2. Print the number of elements is <= to some number in a subarray.

I thought of using the idea of MKTHNUM (merge sort). The problem is, with every operation 1, you'll have to update the sorted array all the way. The second option is to split the whole array into sqrt(n) segments. Operations can be performed in the following manner:

1. i. Find the segment which contains the position (a binary search can be employed, linear search is fine too)
   ii. Binary search for the position of the number in that segment (It can be done with a linear search too)
  iii. Change the initial array, and make the segment sorted by right to left and left to right passes on the sub arrays.

2. i. Find out the segments which partially or wholly intersect the query segment.
   ii. Brute force for partially intersected segments, use binary search for wholly intersected segments.

I got many wrong answers for mistake number 3. I traced it only after testing the solution with small random test cases with brute force results.

Code

Mistakes:

1. Again X(: Mixing subarray indices with input array indices.
2. Binary search errors: Made a logical error on binary search check.
3. When checking how many numbers less/greater than some number, we need to check whether the binary search (lower/upper bound) result yields a valid answer.

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন