So, after many days of being too lazy to update this journal, I've decided to come back. This time with a lot more intent. I'll try to solve some problems every day and put my thoughts here.
শুক্রবার, ২৫ মার্চ, ২০১১
সোমবার, ১৪ ফেব্রুয়ারী, ২০১১
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.
বুধবার, ৯ ফেব্রুয়ারী, ২০১১
SPOJ - MKTHNUM
Problem statement
You are given an array. It's size can be as big as 10^5. You'll also be given a some (<=5000) queries. Each query will ask you about the k-th element of the sorted array between indices a and b. How to solve that?
Naive idea is to sort the query subarray and find the answer. As pointed out in the problem statement, naive algorithm will not work. How about keeping some presorted intervals? Hmm...
Remember the way we did merge sort, we divide each interval, sort each of them and merge them. We can pre-process the sorted intervals that way.
How to use the presorted arrays to answer queries? At each query, it's easy to find the intervals of the merge sort tree which are completely contained in the query. We'll have to find the least x for which the number of elements with value <= x is less than or equal to (actually equal to) x. for fixing the x (log n), for each interval (log n intervals), binary search for each interval (log n). So (log n)^3 for each query. So complexity for answering queries is m (log n)^3. With n log n merge sort, the overall complexity is O(n log n + m (log n)^3).
Code
Mistakes:
1. Mistaking it for k-th smallest element finding at first.
2. Annoying mistake: If an element can't be found in an interval, lo of binary search should be decreased by one.
3. Binary search on negative numbers: (a+b)/2 rounds towards zero (ceiling) instead of floor. A workaround is to binary search on min-value + |min-value| and max-value + |min-value| which converts to to a non-negative binary search.
You are given an array. It's size can be as big as 10^5. You'll also be given a some (<=5000) queries. Each query will ask you about the k-th element of the sorted array between indices a and b. How to solve that?
Naive idea is to sort the query subarray and find the answer. As pointed out in the problem statement, naive algorithm will not work. How about keeping some presorted intervals? Hmm...
Remember the way we did merge sort, we divide each interval, sort each of them and merge them. We can pre-process the sorted intervals that way.
How to use the presorted arrays to answer queries? At each query, it's easy to find the intervals of the merge sort tree which are completely contained in the query. We'll have to find the least x for which the number of elements with value <= x is less than or equal to (actually equal to) x. for fixing the x (log n), for each interval (log n intervals), binary search for each interval (log n). So (log n)^3 for each query. So complexity for answering queries is m (log n)^3. With n log n merge sort, the overall complexity is O(n log n + m (log n)^3).
Code
Mistakes:
1. Mistaking it for k-th smallest element finding at first.
2. Annoying mistake: If an element can't be found in an interval, lo of binary search should be decreased by one.
3. Binary search on negative numbers: (a+b)/2 rounds towards zero (ceiling) instead of floor. A workaround is to binary search on min-value + |min-value| and max-value + |min-value| which converts to to a non-negative binary search.
মঙ্গলবার, ৮ ফেব্রুয়ারী, ২০১১
Codechef - Flipping coins
Problem statement
A relatively easier segment tree problem before going to sleep. I wanted to pass it by one try but one logical error was the reason for the incorrect submission. I kept a lazy value for each node.
Code
Mistakes:
1. Logical error : <to be completed>
A relatively easier segment tree problem before going to sleep. I wanted to pass it by one try but one logical error was the reason for the incorrect submission. I kept a lazy value for each node.
Code
Mistakes:
1. Logical error : <to be completed>
PKU 2777 - Count Color
Problem statement
There are N (<=100000) strips of something (say paper). Initially all of them are painted white. You'll be given some queries, two types of them.
1. Paint a range (a, b) with color x (x<=30)
2. Print the number of different colors in range (a,b)
A really nice problem. Another segment tree problem which requires lazy propagation. I wrote a solution with keeping an array of bools for each color in each node. At first it got couple of WA: I didn't really read the input specification thoroughly. There can be some queries with a>b. It again got WA, I carefully checked the code and realized that my query function wasn't returning anything! (It was returning the correct output, thanks to the stack) A quick fix brought a TLE. I realized that the array of bools can be replaced by a bitmask of int (as there can be as many as 30 colors). That change finally made it AC.
Here is the code.
Mistakes:
1. Not reading the problem statement carefully.
2. Trying to finish the code in a hurry after getting the idea.
3. Forgetting to put return statement.
There are N (<=100000) strips of something (say paper). Initially all of them are painted white. You'll be given some queries, two types of them.
1. Paint a range (a, b) with color x (x<=30)
2. Print the number of different colors in range (a,b)
A really nice problem. Another segment tree problem which requires lazy propagation. I wrote a solution with keeping an array of bools for each color in each node. At first it got couple of WA: I didn't really read the input specification thoroughly. There can be some queries with a>b. It again got WA, I carefully checked the code and realized that my query function wasn't returning anything! (It was returning the correct output, thanks to the stack) A quick fix brought a TLE. I realized that the array of bools can be replaced by a bitmask of int (as there can be as many as 30 colors). That change finally made it AC.
Here is the code.
Mistakes:
1. Not reading the problem statement carefully.
2. Trying to finish the code in a hurry after getting the idea.
3. Forgetting to put return statement.
PKU 3468 - A Simple Problem with Integers
Problem statement
You'll be given an array of N<=100000 integers. And some M<=100000 queries. The queries are of two types: one asks to print the sum of values of a range, the other asks you to add some value to all the numbers in a range.
It's a standard application of lazy propagation or late update, whatever people prefer to say. It's a technique to update a range of values efficiently.
The following things are done when using late update: (Every time I use node as an array index, I mean it to be the current node)
1. During an update, every time a segment is fully inside the query interval, stop it right there. Update that interval. And remember that some value was added to the interval, like lazy[node] += x;
2. Otherwise, explore the left child and right child. Suppose you are at some node. If the value of lazy[node] is non zero, then it's known that the current node was updated but it's child wasn't. Update both child, and add the lazy value of current node to it's child nodes. Set the lazy[node] = 0;
3. Normal parent from child update follows.
4. During the retrieval only step number 2 should be taken care of.
Here is the code.
Mistakes I made:
1. Mixing index with endpoints, got two WAs, didn't even find the bug the first time :|
You'll be given an array of N<=100000 integers. And some M<=100000 queries. The queries are of two types: one asks to print the sum of values of a range, the other asks you to add some value to all the numbers in a range.
It's a standard application of lazy propagation or late update, whatever people prefer to say. It's a technique to update a range of values efficiently.
The following things are done when using late update: (Every time I use node as an array index, I mean it to be the current node)
1. During an update, every time a segment is fully inside the query interval, stop it right there. Update that interval. And remember that some value was added to the interval, like lazy[node] += x;
2. Otherwise, explore the left child and right child. Suppose you are at some node. If the value of lazy[node] is non zero, then it's known that the current node was updated but it's child wasn't. Update both child, and add the lazy value of current node to it's child nodes. Set the lazy[node] = 0;
3. Normal parent from child update follows.
4. During the retrieval only step number 2 should be taken care of.
Here is the code.
Mistakes I made:
1. Mixing index with endpoints, got two WAs, didn't even find the bug the first time :|
সোমবার, ৭ ফেব্রুয়ারী, ২০১১
Next weeks tasks: Segment tree
I am going to practice tasks related to data structure next week. More specifically with segment trees. I have some problems in mind, plus some additional problems if I find some.
এতে সদস্যতা:
পোস্টগুলি (Atom)