Cannot understand the error in the code

binary-search
c-plus-plus-14
linear
linear-search

#1

I was trying to solve the practise problem name Max and Electrical panel
the question is :https://www.codechef.com/problems/MAXEP
I wanted to apporach the problem by dividing into smaller parts of 1000 then 100 and then applying linear search. but my code doesn’t seem to work. can someone point out what is the problem wiht the code:

The code that I was trying is :

    #include<iostream>

int main()
{
	int n, c;
	std::cin >> n >> c;
	int money = 1000;
	int low, high;
	low = 1;
	high = n;
	int ans;
	for (int i = 1000; i <= n; i += 1000)
	{
		std::cout << 1 << " " << i << std::endl;
		std::cin >> ans;
		if (ans == 0)
		{
			low = i;
			money -= 1;

		}
		else
		{
			money -= c;
			high = i;
			break;
		}
	}
	if ((high - low) > 100)
	{
		for (int i = low; i <= high; i += 100)
		{
			std::cout << 1 << " " << i << std::endl;
			std::cin >> ans;
			if (ans == 0)
			{
				low = i;
				money -= 1;

			}
			else
			{
				money -= c;
				high = i;
			}

		}
	}
	for (int i = low; i <= high; i++)
	{
		std::cout << 1 << " " << i << std::endl;
		std::cin >> ans;
		if (ans == 1)
		{
			std::cout << 3 << " " << i << std::endl;
			break;
		}
	}
	std::cin.get();
		std::cin.get();
}

The result was: https://www.codechef.com/viewsolution/22044353

I also wanted to know whether the approach is good or it is flawed. If not whats going wrong?
As such there are no syntax or compile errors but on submitting its shows wrong answer.
Also I am new to competetive coding so any tips would be appreciated.


#2

Your approach is correct given the constraints.

It seems that you missed a crucial point while reading the problem statement.

Here’s your code which passes all the test cases with a minor modification that I’ve made. (Try to figure that out yourself).

https://www.codechef.com/viewsolution/22045310

Just go through the problem statement once and I think you’ll catch it. Good Luck!


#3

Well, you have made several mistakes. Here is the link to the AC submission. I have changed just a little bit.

Here are the mistakes :

  1. You forgot to print “2” while repairing the panel.
  2. Forgot to break in 2nd loop, where there is jump of 100.

#4

@m_never_dies

I don’t think that number 1 should be a problem, isn’t it?

As far as I can see, high is initialised to n and is never set to a number higher than n. (Although i is increased in blocks of 100/1000 , the condition part of the for loop ensures that i is within limits. So just checking for i<=high should suffice.

Although I agree that there’s no harm in putting an extra condition just to be safe (i<=n), but that’s just a trivial matter.


#5

Oh, yeah right @masood786. Actually this was similar to the problem I faced. So in hurry I forgot that high initialized as n. Thanks for pointing out the mistake.


#6

Thanks a lot for pointing out the mistakes.


#7

what if the reuslt was, say 2500 and the third loop would have run from 2400-2499 and then i would have to check again at high, so basically that evades that problem.
Thats what i thought.Ain’t it right?
Btw thanks for pointing out the mistakes, highly appreciated.