Unable to find error in my logic in a codechef july challenge

Question

Chef has a calculator which has two screens and two buttons. Initially, each screen shows the number zero. Pressing the first button increments the number on the first screen by 1, and each click of the first button consumes 1 unit of energy.

Pressing the second button increases the number on the second screen by the number which is currently appearing on the first screen. Each click of the second button consumes B units of energy.

Initially the calculator has N units of energy.

Now chef wonders what the maximum possible number is, that he gets on the second screen of the calculator, with the limited energy. Here is the link: https://www.codechef.com/JULY17/problems/CALC/

Contest is ended, so I am not trying to cheat. here is my solution to the problem:

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,b;
        cin>>n>>b;
        int count = 1;
        int ans = n-b;
        while((n - count*b)>=0)
        {
            if(count*(n - count*b)>ans)
                ans = count*(n - count*b);
            count++;
        }
        cout<<ans<<endl;

    }
    return 0;
}

I have tried every test case that i can think of... Can anyone help to find the error in my logic.

Please read why you should avoid both [`bits/stdc++.h`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [`using namesapce std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Most of all, avoid using them together. — StoryTeller - Unslander Monica, Jul 17 '17 at 10:02
First please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) Then [read about how to ask good questions](http://stackoverflow.com/help/how-to-ask), and also [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) by Eric Lippert. — Some programmer dude, Jul 17 '17 at 10:03
More importantly, I'm missing the error description from the question. — MSalters, Jul 17 '17 at 10:04
@MSalters there is no error as such, but none of the test cases are passing... manually i have tried every case which i can think of... My answer is correct for all those cases... Problem must be in the logic, which i am not able to get... — Utkarsh Vaish, Jul 17 '17 at 10:08
@dasblinkenlight Can you suggest any test case for which my solution will return a wrong answer??? — Utkarsh Vaish, Jul 17 '17 at 10:09
@StoryTeller thank you for this advice... I wasn't aware about this — Utkarsh Vaish, Jul 17 '17 at 10:10
can you show a test case for which it returns correct answer? — 463035818_is_not_an_ai, Jul 17 '17 at 10:17
@tobi303 yeah it passes for basic case given in the question... as well as i tried with large values with in the limit of int and also various possible combinations of n and b — Utkarsh Vaish, Jul 17 '17 at 10:20
@Ron I wouldnt be so negative. True, they dont make you learn the language, they dont make you write nice code, they are a waste of time, but still they can be fun ;) — 463035818_is_not_an_ai, Jul 17 '17 at 10:26
To be fair to online judges, they are good at forcing you to think about your edge cases (as long as the test cases are well designed). — Phylogenesis, Jul 17 '17 at 10:31
How about `b` equal to zero? That will give an endless loop. — Support Ukraine, Jul 17 '17 at 11:25

score 2 · Accepted Answer · answered Jul 17 '17 at 10:12

2

The errors that I think can be:

1: You didn't handle N<=B case

if (n<=b) {
    ans = 0;
}

2: you didn't handle Subtask 2 Constraints

long long int ans = n-b;

3: lastly answer will be n-b if b is three time less than equal to n

if (n<=3*b) {
    ans = n-b;
}

4: Look for a straight forward approach

k1 = ((n-(b+1))/(2*b))+1;
i2 = (double((n-(3*b)))/(2*b));
i1 = ceil(i2);
i = n-((3*b)+((i1-1)*(2*b)));
ans = ((2*b)*((k1*(k1-1))/2))+(k1*i);
cout << ans;

Hope this helps :)

answered Jul 17 '17 at 10:12

Danyal Imran

2,515
13
21

i didn't get your 3rd point... why do i need to handle n>=3*b?? – Utkarsh Vaish Jul 17 '17 at 10:17
@UtkarshVaish This is something I found out by dry running the problem, you might not need to handle this condition if you have solid logic – Danyal Imran Jul 17 '17 at 10:20
my solution automatically takes care of that... – Utkarsh Vaish Jul 17 '17 at 10:21
when i handled 1st and 2nd mistakes pointed by you, first subtask passed correctly – Utkarsh Vaish Jul 17 '17 at 10:28
@UtkarshVaish If you didn't get 100 points, then there is definitely a logical error in your code. Deeply analyze the cases and try to understand the task at hand and your code flow – Danyal Imran Jul 17 '17 at 10:34
I just wanted some test case, which returns wrong answer to my solution – Utkarsh Vaish Jul 17 '17 at 10:59

score 0 · Answer 2 · answered Jul 17 '17 at 15:47

It is a mostly a mathematical question: With

N unit of energy
B energy cost of 2nd screen
p number of time 1st button clicked
s number of time 2nd button clicked

You try to maximize

s * p

whereas

p + B * s <= N

so

p <= N - B * s

and then

maximize: N * s - B * s²

s0 = 0
s1 = N / B

sMax is (s0 + s1) / 2 -> N / (2*B)

so max value is

N²/2B - N²/4B -> N²/4B

so

std::cin >> n >> b;
std::cout << n * n / b / 4 << std::endl

Unable to find error in my logic in a codechef july challenge

2 Answers2