Optimization in overcoming TLE in interviewStreet problem

Question

I have been trying to get the problem Quadrant Queries correct for a while now. Although my approach is an optimal one, I am getting a TLE on 3 test cases. Please help me optimize my approach so that I can pass all test cases for the problem.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair <int,int> pii;
void performCquery(int i,int j, const vector< pii > &pointList)
{
 i = i-1;
 j = j-1;
 int q1 = 0;
 int q2 = 0;
 int q3 = 0;
 int q4 = 0;
 for (int k = i; k <=j ; k++) {
 if ( (pointList[k].first > 0 ) && ( pointList[k].second > 0) ) {
 q1++;
 }
 else if ( (pointList[k].first < 0) && ( pointList[k].second > 0) ) {
 q2++;
 }
 else if ( ( pointList[k].first < 0) && (pointList[k].second < 0 ) ) {
 q3++;
 }
 else if ( ( pointList[k].first > 0) && (pointList[k].second < 0 ) ) {
 q4++;
 }
 }
 cout << q1 << " " << q2 << " " << q3 << " " << q4 << endl; 
}
void performXYquery(char qType, int i, int j, vector< pii > &pointList)
{
 i = i-1;
 j = j-1;
 for ( int k = i; k <= j ;k++) {
 pii pnt = pointList[k];
 if ( qType == 'X') {
 pointList[k].second = -pointList[k].second;
 }
 else if (qType == 'Y') {
 pointList[k].first = -pointList[k].first;
 }
 }
}
int main(int argc, char* argv[])
{
 int numOfPoints;
 cin >> numOfPoints;
 vector < pii > pointList;
 for (int i = 0; i < numOfPoints ; i++) {
 int x,y;
 cin >> x >> y;
 pii temp(x,y);
 pointList.push_back(temp);
 }
 int numOfQueries;
 cin >> numOfQueries;
 for (int i = 0; i < numOfQueries; i++) {
 char qName;
 int startIndex;
 int endIndex;
 cin >> qName >> startIndex >> endIndex;
 if (qName == 'C') {
 performCquery(startIndex,endIndex, pointList);
 }
 else if (qName == 'X' || qName == 'Y') {
 performXYquery(qName, startIndex,endIndex, pointList);
 }
 else {
 cerr << "Error: This line should not be printed" <<endl;
 }
 }
 return 0;
}

• Leonid: The point of this test is to test YOUR current ability to code, not your ability to solicit help on the internet.
• hytriutucx: Thanks, but IMO I never asked for code or solution to my problem. Instead, my code was able to pass 8/10 test case and had a timeout on the remaining 2, therefore I wanted to know if I could optimize my code or my algorithm. Now I do know that my algorithm was pretty naive one. Therefore, inseatead of posting a rude comment, please provide some help.

Answer 1

Algorithmic optimizations.

As you read the values in work out what quadrant the point belongs to and keep a running total for each quadrant (not adjustment needed on X/Y query). Then you do not need to re-calculate everything every time there is a 'C' request.

As it stands complexity for each C request of O(n). If you keep a running total then it is merely o(1). Think of the situation where you have a 1,000,000 points and you do a 1,000,000 C requests. The code would basically do 1,000,000 * 1,000,000 operations rather than just 1,000,000.

Style

Please stop using this:

using namespace std;

For simple ten line programs it makes things simpler. But once you get past that stage it makes things exceedingly more complex. By causing name clashing problems. It is preferable to prefix stuff in the standard namespace with std:: (why do you think they kept it so short).

A personal opinion. So feel free to ignore. But to distinguish types and objects. I nae types with a leading capitol letter. A lower case indicates an object (or reference).

typedef pair <int,int> pii;

What happens below if any point is on the line (first or second == 0)?

 if ( (pointList[k].first > 0 ) && ( pointList[k].second > 0) ) {
 q1++;
 }
 else if ( (pointList[k].first < 0) && ( pointList[k].second > 0) ) {
 q2++;
 }
 else if ( ( pointList[k].first < 0) && (pointList[k].second < 0 ) ) {
 q3++;
 }
 else if ( ( pointList[k].first > 0) && (pointList[k].second < 0 ) ) {
 q4++;
 }
}

Here:

void performXYquery(char qType, int i, int j, vector< pii > &pointList)

For readability I would just make this two separate functions performXquery() and performYquery(). It make the code more readable and removes the need for an if statement in the middle of a tight loop.

There is a standard utility function for creating std::pair<> called make_pair.

 pii temp(x,y);
 pointList.push_back(temp);
 // can be written as:
 pointList.push_back(std::make_pair(x, y));

Since qName is a char you can use a switch statement here:

 if (qName == 'C') {
 performCquery(startIndex,endIndex, pointList);
 }
 else if (qName == 'X' || qName == 'Y') {
 performXYquery(qName, startIndex,endIndex, pointList);
 }
 // can be written as:
 switch(qName)
 {
 case 'C': performCquery(startIndex,endIndex, pointList);break;
 case 'X': performXquery(startIndex,endIndex, pointList);break;
 case 'Y': performYquery(startIndex,endIndex, pointList);break;
 default: /* Error Msg */
 }

No need to return 0 from main() in C++. If no explicit return is placed then an automatic return 0 is planted.

Algorithmic optimizations.

As you read the values in work out what quadrant the point belongs to and keep a running total for each quadrant (not adjustment needed on X/Y query). Then you do not need to re-calculate everything every time there is a 'C' request.

As it stands complexity for each C request of O(n). If you keep a running total then it is merely o(1). Think of the situation where you have a 1,000,000 points and you do a 1,000,000 C requests. The code would basically do 1,000,000 * 1,000,000 operations rather than just 1,000,000.

Macro optimizations

Only do these to make the code more readable. Usually the compiler already handles this kind of optimization. Assume we have an average distribution of points in 4 quadrants:

100 pts // cmp == conditional test like > or < 
25 in q1 use 2 cmp // must pass both to enter
25 in q2 use 3.5 cmp // Note: average (12.5 will do 3 cmp 12.5 will do 4 cmp)
25 in q3 use 5 cmp // to enter the code section that will do q2++
25 in q4 use 6.5 cmp
Total: 425 cmp

If we change the code so you include values on the line (ie first or second == 0) in an appropriate quadrant. You don't need the last if statement which reduces the number of comparisons so that:

100 pts // cmp == conditional test like > or < 
25 in q1 use 2 cmp // must pass both to enter
25 in q2 use 3.5 cmp 
25 in q3 use 5 cmp
25 in q4 use 4.5 cmp
Total: 375 cmp

If we re-range the tests:

if (first >= 0)
{
 if (second >= 0) ++q1;
 else ++q4;
}
else // first = 0
{
 if (second >= 0) ++q2;
 else ++q3;
}

In this case there are always 2 cmp:

100 nodes * 2 cmp = 200 cmp
Approximately a 100% reduction in the number of cmp.
Note: this does not mean a doubling of speed (maybe a slight improvement on average).
 Assuming the compiler has not already worked this out.

But in my opinion makes the code more readable.

Answer 2

Your approach is not an optimal one.

What you need to do is store the points in a data structure that allows you to flip and count the points without looking at each points independently. Otherwise, it will simply take too long.

I used a tree for each quadrant for this problem, the rest I leave up to you.