ABhinav2003's blog

Problem — Shovels and Swords | plz help i tried to find bug all night still did'nt get and i am frustrated!!!
By ABhinav2003, history, 4 years ago, In English 
#include<bits/stdc++.h>
using namespace std;

long long int emerald(long long int sticks ,long long int diamonds)
{
	
	if(sticks <= 0 || diamonds <= 0 ||(sticks == 1 && diamonds == 1) )
	return 0;

	else
	return max(1+emerald(sticks - 1 , diamonds-2), 1+emerald(sticks-2,diamonds-1));
}


int main()
{
	
	int t;
	cin>>t;
	while(t--)
	{
		long long int sticks , diamonds;
		cin>>sticks>>diamonds;
		
		cout<<emerald(sticks,diamonds)<<"\n";
		
	}
}

-----------------------------------------------------------------------

HERE IS THE QUESTION — (https://codeforces.com/contest/1366/problem/A) |

  • Vote: I like it
  • -24
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Imagine the number of times recursion runs.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like the issue is stack overflow. You are having too many recursive calls.Even if you use memoization, total memory will be 10^8*10^8 for the given test which itself will cause memory limit exceeded.So better try to come up with efficient algorithm both in terms of space and time.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In A problem I don't think they will give so much implementation to do The solution will have 1-2 if/else statement or some loop

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the solution should be O(1), your code run wrong because it call emerald() too many times

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

I can understand the frustration, problem A gave me a lot of trouble too in the contest, what makes me even more angry at myself is that I had a problem similar to this just a week ago, and still I was not able to solve as quickly as a I wanted to in this contest.

Anyway, there is a very simple solution to this problem. If you don't want to hear me explanation, you can just see the solution link, I think my code is pretty self-explanatory — https://codeforces.com/contest/1366/submission/83417205

Here is the explanation — DON'T over-complicate this problem, the answer is as simple as (a+b)/3, because, eventually it boils down to this, you are using 3 "resources" to make 1 "product" (2a1b, 1a2b), hence the answer is the quotient of (a+b)/3, there is catch though, what if either of a or b is less than (a+b)/3? then our answer in this case would be min(a,b).

Hence, the final answer to this problem is — min((a+b)/3,min(a,b))

→ Reply