A simple 3D segment tree does the job.

change the ints to long long and it will pass i guarantee it !!! says this with thumbs up

Look, you are a newbie. This world of Codeforces is really very tough for newbies. Sorry to say that :(

Work hard. You will succeed here. Though it is gonna be tough. :P

I think you should read my new book: How to Get 2700+ Rating on Codeforces in 10 Days

You must read this :)

ugh newbies these days....

theres an easier way to do this

#include <weed>
#include <alcohool>
#include <nicky minaj>

int mein(){

int tequila,vodka;
int drunk==0;
f>>tequila>>vodka;
drunk=tequila-vodka;
cout<<drunk<<'enld';

return 0;
}

Egor it seems that you need to make training like cgy4ever
I expect you will be better in the near future I discovered a lot of guys but this time really I believe that you someday will be good and I'm sure you will be red.
anyway If you need any kind of help in any hard problems just tell me.
I will make training soon for some Beginners if you are interested you can join :P

My solution also gives TLE, I think I should try memoization:

#include <iostream>
using namespace std;

int compute(int n){
    if(n<3) return n;
    return 2*compute(n-1) - compute(n-2);
}


int main() {
    int a,b;
    cin >> a >> b;
    cout << compute(a)+compute(b) << endl;
}

I like your sense of humor, Egor. It sure makes me laugh (although I am a poor newbie as well :P)

Indeed, it's a tough problem for your level. I think it can be solved by defining the addition operation through Lambda Calculus.

First, let's define Natural Numbers. Let's say that a number x is a function that given another function y and a variable z, applies y on z for x times.

0 ::== λx.λy.z
1 ::== λx.λy.x y
2 ::== λx.λy.x x y
...

So, let's define the addition operator. It would simply be:
add a b ::== a λx.λy.x b x y (Remember: a, b are natural numbers, so they are just functions.)

I'll leave the easy work of handling negative numbers, thinking about how to relate that to code, .. etc, to you as a kind of practice.

One last note: I really didn't try to learn these things, so I'm probably speaking nonsense. But a newbie like you wouldn't tell.

I have this problem: http://www.spoj.com/problems/TEST

I'm thinking about an approach using Suffix Tree, Splay Tree, Dynamic convex hull, Max flow using pre-flow push with global heuristic. But I still don't have any good solution. Can anyone help me please :(

It's so hard for you to solve this problem... :|

You should practice hard to do that... :|

Once mathlover told me this problem can be solved by using network flow. I think the approach newbie mathlover told us can be understood easily by us poor newbies.

Interesting... I really enjoy this problem but since I am only an expert, I am looking forward to opinions from these explosions of International Grandmasters, (I honestly don't know how).

Your code runs in linear time, with a constant factor of one. The constant factor however can be reduced to half with two simple base cases by doing the following:

int main() { int a, b; cin >> a >> b; int ans = 0; if (a == 1) { cout << b + 1 << endl; } else { cout << a + 1 << endl; } for (int i = 0; i < a; i += 2) ans += 2; for (int i = 0; i < b; i += 2) ans += 2; cout << ans << endl; return 0; }

It requires complex bit manipulation.
So, I think it might be too tough for your level. First work on easier problems and build your level up to this.
Anyway, here is my AC solution for your reference.

int add(int a, int b) {
    if (!b) return a;
    return add(a^b, (a&b) << 1);
}

int main() {
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

    int a, b;
    cin>>a>>b;
    cout<<add(a,b)<<"\n";

    clock_t endTime = clock();
    return 0;
}

Your solution is O(a+b) which is quite slow , you can use a technique similar to Exponentiation by squaring so it will become O(log(a)+log(b)), also it's better if you use fast input/output methods

here's the code

#include <iostream>
#include <stdio.h>
using namespace std;

int a,b,ans=0;

int main(){
    scanf("%d %d",&a,&b);
    int p=1;
    while(a>0){
        if(a%2){
            ans+=p;
        }
        a/=2;
        p*=2;
    }
    p=1;
    while(b>0){
        if(b%2){
            ans+=p;
        }
        b/=2;
        p*=2;
    }
    printf("%d\n",ans);
}

Your algorithm is O(a+b). You can easily make it O(min(a,b)). Here is how to do it:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if(a>b) swap(a,b);
  int ans = b;
  for (int i = 0; i < a; i++) ans++;
  cout << ans << endl;
  return 0;
}

Also, you should use faster IO methods.

Did you try to solve it for small a and b? It must be a pattern there, and then precalc does the matter.

The answer is trivial . 1- Swap a and b

2- find the largest a*b digit prime that can be expressed only by powers of 2 ;) eg 7 = 2^3 — 2^0

3- Now multiply that prime number by a|b

4- print a+b

I have been searching for a solution to this problem for over a year.. And today I found a solution thanks to google. However it was too complicated and I couldnt prove it. Please help, heres the code:

#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  cout << a+b << endl;
  return 0;
}

What does this '+' magical symbol does?

No no. You're wrong. You should solve it in a clear recursively way like this:

#include<iostream>
using namespace std;
typedef long long ll;
int sum(int x,int y)
{
    if (x==0)
       return y;
    else
       return sum(x-1,y)+1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    int a,b;
    cin >> a >> b;
    cout<< sum(a,b) <<endl;
    return 0;
}

Also be sure to use

ios_base::sync_with_stdio(0);

to not be time limit exceeded while getting the input. :)

*I suggest you first of all learn functions and then try to solve a+b problem. Because it needs recursive functions...

your code is too complicated to understand . as a newbie coder i suggest you to follow the way you actually do computation in mind . how do you add in mind ? obviously by memorizing the last state. so here is the best thing for newbies :D

#include<bits/stdc++.h>
using namespace std;
int mem[1000][1000];
int a,b;
int dp(int x,int y)
{
    if(x<0 || y<0) return 0;
    if(x==0) return y;
    if(y==0) return x;
    int &ret=mem[x][y];
    if(ret!=-1) return ret;
    ret=0;
    ret+=dp(x-1,y-1)+2;
    return ret;
}
int main()
{
    cin>>a>>b;
    memset(mem,-1,sizeof(mem));
    cout<<dp(a,b)<<endl;
    return 0;
}

Egor Lol :P

there is my code for this problem, it works for 1<=a,b <=1000

RGHOST

MEGA

i will try to type code solving for constraints up to 10000!

I think the hint is misleading, you shouldn't use '+'. This code gets AC and has no '+' at all:

#include <iostream>

int main() {
	long long a, b; 
	std::cin >> a >> b;
	
	for (int i = 10000 ; i ; i--) {
		long long x = 1LL << (rand() % 33);
		if (a & x) if (b & x) if (!(a & (2*x))) { a ^= x ; b ^= x ; a ^= 2 * x ; continue; }
		if (a & x) if (b & x) if (!(b & (2*x))) { a ^= x ; b ^= x ; b ^= 2 * x ; continue; }
		if (b & x) if (!(a & x)) { a |= x; b ^= x ; continue; } 
	}
	std::cout << a;
}

You're asked to use the + operator. This is why I think the following link may be useful:

http://stackoverflow.com/a/19412942

You may need to make a few insignificant changes if this program wouldn't strictly conform to the required input specification.

I watched some lectures about randomized algorithms from Burunduk1 recently, and i tried his usual recipe — as everybody knows, it works for every problem...

#include<bits/stdc++.h>
using namespace std;

int main(){

int a,b,res;

cin>>a>>b;
while (true)
{
 res=rand();
 if (res-b==a)
 {
  cout<<res<<endl;
  break;
 }
}

return 0;}

Same problem here

it took 2 hrs of coding but nothing at the end :(

I'll keep trying, I'll teach you if i got accepted

It is easy to guarantee constant time lookup:

#include <iostream>                                                           
int main()                                                                    
{                                                                             
  int a,b;                                                                    
  cin >> a >> b;                                                              
  if(a==0 && b==0){                                                           
    cout << 0 << endl;                                                        
  }                                                                           
  if(a==0 && b==1){                                                           
    cout << 1 << endl;                                                        
  }                                                                           
  if(a==0 && b==2){                                                           
    cout << 2 << endl;                                                        
  }                                                                           
  if(a==0 && b==3){                                                           
    cout << 3 << endl;                                                        
  }                                                                           
  if(a==0 && b==4){                                                           
    cout << 4 << endl;                                                        
  }                                                                           
  if(a==1 && b==0){                                                           
    cout << 1 << endl;                                                        
  }                                                                           
  if(a==1 && b==1){                                                           
    cout << 2 << endl;                                                        
  }                                                                           
  if(a==1 && b==2){                                                           
    cout << 3 << endl;
  }
  if(a==1 && b==3){                                                           
    cout << 4 << endl;                                                        
  }                                                                           
  if(a==1 && b==4){                                                           
    cout << 5 << endl;                                                        
  }                                                                           
  if(a==2 && b==0){                                                           
    cout << 2 << endl;                                                        
  }                                                                           
  if(a==2 && b==1){                                                           
    cout << 3 << endl;                                                        
  }                                                                           
  if(a==2 && b==2){                                                           
    cout << 4 << endl;                                                        
  }                                                                           
  if(a==2 && b==3){                                                           
    cout << 5 << endl;                                                        
  }                                                                           
  if(a==2 && b==4){                                                           
    cout << 6 << endl;                                                        
  }                                                                           
  if(a==3 && b==0){                                                           
    cout << 3 << endl;                                                        
  }                                                                           
  if(a==3 && b==1){                                                           
    cout << 4 << endl;                                                        
  }                                                                           
  if(a==3 && b==2){                                                           
    cout << 5 << endl;
  }                                                                           
  if(a==3 && b==3){                                                           
    cout << 6 << endl;                                                        
  }                                                                           
  if(a==3 && b==4){                                                           
    cout << 7 << endl;                                                        
  }                                                                           
  if(a==4 && b==0){                                                           
    cout << 4 << endl;                                                        
  }                                                                           
  if(a==4 && b==1){                                                           
    cout << 5 << endl;                                                        
  }                                                                           
  if(a==4 && b==2){                                                           
    cout << 6 << endl;                                                        
  }                                                                           
  if(a==4 && b==3){                                                           
    cout << 7 << endl;                                                        
  }                                                                           
  if(a==4 && b==4){                                                           
    cout << 8 << endl;                                                        
  }                                                                           
} 

I think you can easily see how to extend this :)

It seems you have chosen a very hard problem. You must try another problem easier than this... You are good enough this problem is so hard don't cry.

anyway, try to solve it before participating in TCO 2015 Final Round because it's a very important classic problem :D

Wow this problem is quite impressive because I have seen in all online judge I have been. I don't know any aproach to attack this kind of problem, good luck Egor

Change your rating back, maybe it's the problem.

After a day of thinking, I realized that this was a simple binary search exercise:

#include<iostream>

using namespace std;

int main() {
   int a, b;
   int ans;
   cin >> a >> b;
   int l = 0, r = 1 << 30;
   while (l + 1 < r) {
      int mid = (l + r - 1) / 2;
      if (mid == a + b) ans = mid;
      else if (mid < a + b) l = mid + 1;
      else r = mid + 1;
   }
}

Of course to be safe, at the end you can add a check to see if this is the right sum by doing if (ans == a + b) ... Oh wait a minute.

you could solve it with binary index trees in o(log(a+b))

#include<bits/stdc++.h>
#define ll long long unsigned int
using namespace std;
ll maxn=100000;
ll bt[100000];
void update(ll ind,ll v){
    while(ind<maxn){
        bt[ind]+=v;
        ind+=(ind&-ind);
    }
}
ll query(ll ind){
    ll ans=0;
    while(ind>0){
        ans+=bt[ind];
        ind-=(ind&-ind);
    }
    return ans;
}
int main(){
    ll a,b;
    cin>>a>>b;
    update(a,a);
    update(b,b);
    cout<<query(a+b);
}

finally accepted with this code. :D

I know all of you are alien machine of gods' from 57Ds outspace ,Gods wants all of you to maitain the society of 3Ds,not disturb the 3Ds world,just keep it,not doing crime!!!!!!

Congratulation for being Specialist from Newbie.
No doubt that, you have tried hard for this rating change. Try more. If you rightly do your work, sure, you will be able to solve this hard problem in 8 days. :P

Finally I did it:

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int main()
{
    long long int first,second;
    char a[128],b[128],c[128];
    int asz,bsz,curr,t=0,i;
    scanf("%lld %lld", &first, &second);
    sprintf(a,"%lld",first);
    sprintf(b,"%lld",second);
    reverse(a,a+strlen(a));
    reverse(b,b+strlen(b));
    while(strlen(a)<strlen(b))
        strcat(a,"0");
    while(strlen(b)<strlen(a))
        strcat(b,"0");
    asz=bsz=strlen(b);
    for(i=0;i<asz;i++)
    {
        curr=t+a[i]-'0'+b[i]-'0';
        t=curr/10;
        curr%=10;
        c[i]=curr+'0';
    }
    if(t)
        c[asz]=t+'0';
    reverse(c,c+strlen(c));
    printf("%s\n",c);
    return 0;
}

Wow... You improved... You are specialist now...

Egor, you must be enjoying this :D Plot twist: he can't solve the problem for real (:ok je sors:).

Now Egor is green! Did you solve this problem?

Hi Egor. I think your code is ok for nonnegative values, but it fails for negative ones!

ur problem looks very similar to this problem.
u should just submit the same solution 5 times, it will give u WA. when u submit 6th time, u will get AC! :)

.-. LOL very hard problem.

This is a very complex MST problem. It took me two days to reach the conclusion that I can do it like this: Nodes A and B are connected with a total weight of A+B This is my AC code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;
int a,b;
vector<tuple<int,int,int> >EdgeList;
vector<int> pset(1000000);
void initSet(int N) { for(int i=0;i<=N;i++) pset[i] = i; }
int findSet(int i) {return (pset[i] == i) ? i : (pset[i]=findSet(pset[i])); }
void unionSet(int i, int j) {pset[findSet(i)] = findSet(j); }
int isSameSet(int i, int j) {return findSet(i) == findSet(j); }
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    while(cin>>a>>b){
        initSet(max(a,b)+1);
        EdgeList.clear();
        EdgeList.push_back(make_tuple(a+b,a,b));
        sort(EdgeList.begin(),EdgeList.end());
        int mst=0;
        for(tuple<int,int,int> u:EdgeList){
            int w,a,b;
            tie(w,a,b)=u;
            if(!isSameSet(a,b)){
                unionSet(a,b);
                mst+=w;
            }
        }
        cout<<mst<<"\n";
    }
    return 0;
}

Congrats Egor, now you're "Expert" :)) I think you have solved this problem finally, have you? :D

Egor must be truly great rising star of competitive programming since he became blue from grey in such a short period of time! Even lack of contests wasn't an obstacle for him!

One thousand upvotes. Wow.

Solution in 20+ languages https://www.hackerrank.com/challenges/solve-me-first :D

it prints the answer for x , y

printf("%d",printf("%*c%*c", x,'\r', y, '\r'));

It Seems like This post gonna be on Top till next Christmas :D

Use ++i and ++ans.

Congratulation Egor !!!
You are in div 1 now !!! Wish you best luck.

you are Candidate master now.Now try once again.

International master ... ! way to go Egor ... ! :D

Why you posting a blog for vain Threads.:| you are crazy !

.

U BAD U BAD U BAD U BAD U BAD

here is the code: ;)

if you need any more help feel free to contact me ~~~~~

include

using namespace std; int main() { int a,b; cin>>a>>b; cout<<a+b; return 0; } ~~~~~

The editorial is finally here, check it out.

#good_old_times

[deleted]