You are not logged in. Please login at www.codechef.com to post your questions!

×

CANDY123 - Editorial

2
1

PROBLEM LINK:

Practice
Contest

Author: Kamil Debowski
Primary Tester: Marek Sokołowski
Secondary Tester: Praveen Dhinwa
Editorialist: Praveen Dhinwa

DIFFICULTY:

cakewalk

PREREQUISITES:

none, knowledge of for or while loops in any programming language

PROBLEM:

Limak and Bob are friends who play a game involving eating candies. They take turns alternately with Limak starting first. Initially Limak eats 1 candy, then Bob eats 2 candies, then Limak 3 followed by Bob eating 4 candies and so on. Limak can eat at most $A$ candies, whereas Bob can eat at most $B$ candies. The person who is not able to eat the required candies in his turn will lose the game. Find out the winner of the game.

Problem constraints mention that $A$ and $B$ can be at max 1000. The idea of the solution is to implement the turns of the game. We iterate over the number of candies being eaten in the current starting from 1 onwards and check whether the current player can eat the desired amount of candies or not. We can find the current player by checking the parity of number of candies in the turn being eaten. You can see that Limak always eats odd number of candies, while Bob even number of candies. If the current player is not able to eat the required amount of candies, he will lose. Pseudo code follows.

limakCandies = 0 // denotes number of candies eaten by Limak.
bobCandies = 0 // denotes number of candies eaten by Bob.
c = 1;
while (true)
    // In this turn the person should eat exactly c candies.
    // if c is odd, then it is Limak's turn, otherwise Bob's.
    if c % 2 == 1:
        limakCandies += c;
        if (limakCandies > A):
            // limak can't eat these c candies, so Bob will win.
            winner = "Bob";
            break;
    else:
        bobCandies += c;
        if (bobCandies > B):
            // Bob can't eat these c candies, so Limak will win.
            winner = "Limak";
            break;

    c += 1;

Notice that the while loop can have at most $A + B$ iterations, i.e. at most $2000$ iterations. There are 1000 test cases. So, total number of operations will be around 2000 * 1000 = 2 * 10^6 which is sufficient to pass under a sec. For a rough guideline, you can assume that around $10^8$ operations take a second to execute. Please note that this is a rough guideline, actual number of operations depend very much on the implementation of the solution and also on the architecture of the machine on which your code is being judged. You should also account for the extra constant factor due to your implementation.

In fact, if you analyze carefully, you can prove that number of iterations of the while loop will much less than 2000, they will be around $\sqrt{2000}$, around 45. This is because we are subtracting $c$ candies each time, $c$ going from 1 to 2 to 3 and so on. As we know that sum of $1 + 2 + \dots + n = \frac{n \cdot (n+1)}{2} = \mathcal{O}(n^2)$. Therefore, $c$ will become greater than $A$ or $B$ in around $\sqrt{A + B}$ operations.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester1
Tester2

This question is marked "community wiki".

asked 22 Apr '17, 20:27

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136169
accept rate: 20%

edited 24 Apr '17, 01:42

admin's gravatar image

0★admin ♦♦
19.6k349497539


include<stdio.h>

void main() { int n,a,b,limak,bob,i=1,flag; scanf("%d",&n); while(n--) {

    limak=1,bob=2,flag=0;
    scanf("%d%d",&a,&b);
        if(limak>a)
        {
            flag=1;
        }
        else if(bob>b)
        {
            flag=2;
        }
    if(flag==0)
    {
    while(1)
    {


        if(i%2!=0)
        {
            limak=limak+i;

        }
        else
        {
            bob=bob+i;

        }
        if(limak>a)
        {
            flag=1;
            break;
        }
        else if(bob>b)
        {
            flag=2;
            break;
        }
        i++;
    }
    }
    if(flag==1)
    {
        printf("bob\n");
    }
    else if(flag==2)
    {
        printf("limak\n");
    }
}

}

where did I go wrong sir?

link

answered 24 Apr '17, 11:47

souvik_haldar's gravatar image

2★souvik_haldar
111
accept rate: 0%

I took a bit different approach, let's assume both Limak and Bob can eat candies till N times. Now, total candies eaten by Limak in N turns is N^2 and by Bob is N(N+1), given that former eats only odd number of candies and latter only even number of candies. We have been provided constraints for both N^2 and N(N+1) in the form of max number of candies each participant can eat. Now, we find N for each of them in each test case by equating N2 to max candies Limak can eat and N(N+1) to max candies Bob can eat. We obtain N as floor value of the above solutions, since a turn can't be partially executed. Either all candies in that turn will be eaten or the person will lose.

Now for each test case, person with higher N, essentially person who can eat for more number of turns wins. In case of equal Ns, Bob wins as he plays second and Limak can't eat anymore.

This yields an O(1) solution for each test case. I don't have code availabe as of now. Can share if needed later on.

link

answered 24 Apr '17, 12:53

chiragg91's gravatar image

0★chiragg91
111
accept rate: 0%

I have used an approach in which I have calculated the number of maximum turns a player can eat candies. There are two formulas to calculate maximum no. of turns for both players can eat candies.

For 'Limak' :- sqrt(total candies can eat by Limak) For 'Bob' :- (sqrt(4 * total candies can eat by Bob + 1) - 1)/2

Which player have maximum no. of turns will be the winner of the game.

Note :- These formulae can be derived using formula of summation of Arithmetic Progression (AP). Where, a = 1 (for Liamk) and 2 (for Bob) d = 2 (for both)

You can check out the solution here.

link

answered 24 Apr '17, 18:08

as7664's gravatar image

2★as7664
111
accept rate: 0%

You may check my code here..but it is written in Java https://www.codechef.com/viewsolution/13377461

link

answered 24 Apr '17, 21:51

bhola_nit's gravatar image

5★bhola_nit
2015
accept rate: 0%

HI Sauvik, its "Limak" not "limak" and similarly its "Bob" not "bob".

link

answered 24 Apr '17, 12:14

vidyut_1's gravatar image

5★vidyut_1
1444
accept rate: 20%

I have corrected your code here: https://www.codechef.com/viewsolution/13384169

What mistake you did? Initialize i=1 outside the while loop and wrote limak instead of Limak and same for Bob.

Hope it helps. :)

link

answered 24 Apr '17, 17:37

ayan_nitd's gravatar image

4★ayan_nitd
2097
accept rate: 13%

I used AP to solve it in constant time ;)

First case no. of turns N1=sqrt(A) Second case N2=(-1+sqrt(4B+1))/2 and (-1-sqrt(4B+1))/2 (whichever is positive) then if N2>=N1 then Bob will win otherwise Limak will win

Note: 1. >= is used because even in the case when N2==N1 Bob will win as Limak will get the next chance in which he can't eat candy 2. Instead of storing and comparing only positives i stored and compared both values of N2

Code

link

answered 24 Apr '17, 20:37

alphastar's gravatar image

3★alphastar
295
accept rate: 0%

Thanks a lot! I stand corrected now.

link

answered 24 Apr '17, 21:51

souvik_haldar's gravatar image

2★souvik_haldar
111
accept rate: 0%

Complexity: O(1)

#include<iostream>
#include <math.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        int na,nb;
        na = sqrt(a);        // 1+3+5+... = a (get no of turns na of Limak using AP)
        nb = (sqrt(1+4*b)-1)/2;      //2+4+6+... = b (get no of turns nb of Bob using AP)
        if(na==nb)
            cout<<"Bob\n";
        else if(na>nb)
            cout<<"Limak\n";
        else
            cout<<"Bob\n";
    }
    return 0;
}
link

answered 15 Sep '17, 21:14

ankesh_john's gravatar image

1★ankesh_john
21
accept rate: 0%

edited 16 Sep '17, 11:26

int m,n;
   cin>>m>>n;

   int a=sqrt(m);
   int b=(-1+sqrt(1+(4*n)))/2;

   if(b>=a)
   {
       cout<<"Bob"<<endl;
   }
   else
       cout<<"Limak"<<endl;
link

answered 14 Jun, 15:39

prateek181996's gravatar image

2★prateek181996
1
accept rate: 0%

include<bits stdc++.h="">

using namespace std; int main() { int n,i; cin>>n;

for(i=0;i<n;i++) {="" int="" l,b;="" cin="">>l>>b;

int j,x,count=0;
for(j=1;j<33;j++)
{
    x=j*j;
    if(l==x && b<x+j)
    {
        cout<<"Limak\n";
        count++;

    }
}


if(count==0)
{
    cout<<"Bob\n";
}

}

}

where i am wrong because it is working for all the cases i can think of but still after submition i am getting wrong answer ,please help me

link

answered 08 Nov, 01:31

sidbhati's gravatar image

2★sidbhati
1
accept rate: 0%

What cases have you tried?

For example:

1
1000 1

should have Limak as an easy winner, right?

(08 Nov, 07:47) joffan5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,198
×1,579
×83
×6

question asked: 22 Apr '17, 20:27

question was seen: 1,929 times

last updated: 08 Nov, 07:47