CANDY123 - Editorial

editorial
, , ,
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

2 Likes
2

#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?

1 Like
3

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

4

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.

1 Like
5

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. :slight_smile:

6

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.

1 Like
7

I used AP to solve it in constant time :wink:

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


[1]


  [1]: https://www.codechef.com/viewsolution/13379574
8

Thanks a lot! I stand corrected now.

9

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

1 Like
10

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;
}
11

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;
12

#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

13

What cases have you tried?

For example:

1
1000 1

should have Limak as an easy winner, right?