5
\$\begingroup\$

This code is for handling addition of two binary numbers, which can be as long as 100,000 bits... and up to 500,000 queries are performed.

High-level pseudocode:

  1. First input N: number of bits in binary number A and B.
  2. Second input Q: number of queries to be performed.
  3. Next N inputs: 0/1s ... bits for A
  4. Next N inputs: 0/1s ... bits for B
  5. Next Q inputs are one of the following:

    1. set_a INDEX VALUE: as a result I set a[INDEX] = VALUE
    2. set_b INDEX VALUE: as a result I set b[INDEX] = VALUE
    3. get_c INDEX: as a result I print c[INDEX] where C = A+B (binary addition, like 100 + 101 = 1001)

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <utility>  // For pair
#include <iterator> // For iterator, bidirectional_iterator_tag, reverse_iterator
#include <climits>  // For CHAR_BIT, ULONG_MAX
using namespace std;


class VanEmdeBoasTree {};

int main(int argc, char * argv[])
{
  int n, q;
  char c;
  bool a[100005] = {0}, b[100005] = {0};
  VanEmdeBoasTree equals;
  cin>>n;
  cin>>q;

  for(int i=0;i<n;i++){
    cin>>c;
    if(c=='1')
      a[n-i-1] = true;
  }
  for(int i=0;i<n;i++){
    cin>>c;
    if(c=='1')
      b[n-i-1] = true;
    if(a[n-i-1] == b[n-i-1]){
      equals.insert(n-i-1);
    }
  }

  string query;
  int index, val, lastval;
  for(int i=0;i<q;i++){
    cin>>query;
    cin>>index;
    if(query[4] == 'a'){
      cin>>val;
      if(a[index] != val){
        a[index] = val;
        if(a[index] == b[index]){
          equals.insert(index);
        }else{
          equals.erase(index);
        }
      }
    }else if(query[4] == 'b'){
      cin>>val;
      if(b[index] != val){
        b[index] = val;
        if(a[index] == b[index]){
          equals.insert(index);
        }else{
          equals.erase(index);
        }
      }
    }else if(query[4] == 'c'){
      int final = 0;
      if(index == n){
        if(equals.size() > 0){
          VanEmdeBoasTree::const_iterator it = equals.predecessor(index+1); 
          if(it!=equals.end() && a[*it] == 1){
            final = 1;
          }
        }
      }else{
        final = (a[index] + b[index])%2;
        if(equals.size() > 0){
          VanEmdeBoasTree::const_iterator it = equals.predecessor(index); 
          int last = -1;
          if(it != equals.end())
            last = *it;
          if( last!=-1 && index!=0 && it!=equals.end() &&  a[last] == 1){
            final = 1-final;
          }
        }
      }
      cout<<final;
    }
  }

  return 0;
}

My solution is not fast enough as the Judge says "time out" after some test cases.

\$\endgroup\$
  • 4
    \$\begingroup\$ Can you link the online judge for this problem? \$\endgroup\$ – Winston Ewert Jan 30 '12 at 19:21
  • \$\begingroup\$ @WinstonEwert its the same one posted in one of the issues raised in meta.codereview.stackexchange.com by you. :-/ \$\endgroup\$ – Pheonix Jan 30 '12 at 19:28
1
\$\begingroup\$

Profile and you will find your bottlenecks, you can do that with gprof under gcc/g++. You have to set the -g -pg on compile and then run your program like you would do normally. It will then produce a gmon.out file which you can open with gprof main gmon.out (assuming main is the name of your executable).

It will show you, in which functions your program spends most of the time.

\$\endgroup\$
  • \$\begingroup\$ The code in is C++ and gcc wont compile it, i tired what you said with g++ but no gmon.out was created. \$\endgroup\$ – Pheonix Jan 30 '12 at 19:20
  • \$\begingroup\$ @Pheonix Oh, I forgot, you have to add -g. \$\endgroup\$ – inf Jan 30 '12 at 19:28
  • \$\begingroup\$ @Pheonix: The gmon.out is generated after you run the program. \$\endgroup\$ – Martin York Jan 30 '12 at 23:34
0
\$\begingroup\$

I've just solved this problem (using a different technique then you)

Things I learned that you might find useful:

  1. There is a lot of input for the test cases. I found that I was spending the bulk of my time just reading in the input. However, this didn't didn't show up in the output of gprof
  2. I had to construct test cases with pathalogical natures to find the performance issues with my solution.
\$\endgroup\$
  • \$\begingroup\$ congratulations... but on the other hand, i am struggling a lot, i changed quiet a few things, not using stl::map anymore, my own testcases are coming fine, tested with hundreds of them now, but wrong answer after #5... and its been 2 days with that :( am out of test cases \$\endgroup\$ – Pheonix Feb 1 '12 at 18:24
  • \$\begingroup\$ @Pheonix, if you share the latest version of the code, I'll see if I can pinpoint where yours fails \$\endgroup\$ – Winston Ewert Feb 1 '12 at 18:32
  • \$\begingroup\$ i updated my code in the question, removed the implementation of VanEmdeBoasTree from code, keithschwarz.com/interesting/code/?dir=van-emde-boas-tree .. i dont get timeout (thanks to van-emde-boas), but wrong answer. \$\endgroup\$ – Pheonix Feb 1 '12 at 19:02
  • \$\begingroup\$ additionally, there is one more implementation with some changes, which i made to make testing easier, it sets random bits and A/B and prints all A, B, C... so i see if result is matching or not, if u wish i will post that code too. \$\endgroup\$ – Pheonix Feb 1 '12 at 19:04
  • \$\begingroup\$ @Pheonix, your code doesn't print a newline after all the bits. Other then that, I haven't found a case where my version differs. \$\endgroup\$ – Winston Ewert Feb 1 '12 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.