Hello Codeforces Community,

With reference to my previous blog Link

Today, we provide you explanation to problems from Codeforces Round 538(Div 2).

This is the link to the playlist for video explanation to all problems of the round 538.

Hope these videos help the community to learn concepts and upsolve at a faster rate.

Also, We definitely look forward to suggestions and tips on how we can improve ourselves and help the community to upsolve and understand editorials in an interesting way.

Feel free to like and comment on the videos if you have any doubts or queries.

Also if these videos help you in solving the problems, subscribe to the channel as this definitely motivates us for the same.

Thank You.

Hello Codeforces Community,

Me along with dodobhoot have started a youtube channel Link and will be posting video editorials to regular codeforces rounds.

As part of the initiative, we have made videos to solutions for problems A,B,C,D & E from Codeforces Global Round 1 Contest Link

Hope these videos help the community to learn concepts and upsolve at a faster rate.

As this is our first attempt. We definitely look forward to suggestions and tips on how we can improve ourselves and help the community to upsolve and understand editorials in an interesting way.

Feel free to like and comment on the videos if you have any doubts or queries.

Also if these videos help you in solving the problems, subscribe to the channel as this definitely motivates us for the same.

Thank You.

Considering the fact that acm icpc regionals are on the GO! One of the only advantages in acm apart from the fact that one participates in teams of three is that you also get to carry a

25 pages booklet

that contains templates for some specific algorithms that individuals usually find difficult to code . I tried to google some and found this

link-

It contains most of the well known complex algorithms that require both time and knowledge to code them accurately without any bugs . So i believe having such a template in hand if someone is lucky enough to get a similar question that requires such complex algorithms to be coded fast then it obviously turns out to be a boon , the simple reason being that you dont have the power to sit and google out things there. :P

I also wonder what the highly rated coders in division 1 who are participating in acm this year and practicing hard for their regionals or finals , whatsoever the case may be :D , keep which algorithms in their booklet prepared because for them its always a matter of how fast and short they can code out bug free (atleast i feel so).

I understand the fact that having a template of an algorithm in hand without understanding how the algorithm actually works is useless but considering the also obvious fact many regionals are yet to take place and with the world finals at stake people might consider learning something complex and therefore even a small knowledge of what the code does can be an added advantage.

Also for people who code in Java, Egor github link has many templates of standard data structures and algorithms that one can use easily . Github Link — Thanks to him.

It would be helpful if others also share their experiences , if the usage of booklet does serve any help and suggest such templates of algos that if kept would turn out to be beneficial for all because if resources are given to someone i think one might always make the best possible use of it.

Thanks to all in advance .

Problem C : Mr. Kitayuta, the Treasure Hunter

I was trying to solve this Problem on codeforces but when i was trying to solve it in my laptop it gave me StackOverflow error even for small inputs.

I wrote the code in Sublime Text and run it using command prompt

I tried running the same code on Eclipse IDE but in vain . Got the same StackOverflowError .

I checked other people's AC codes and found that logic was same . So i tried submitting the code on codeforces and to my surprise it got AC.

Submitted Solution :- 21278829

Do i need to create a thread and initialize something or something is wrong with the memory. I am unable to figure out the mistake why the program is not executing successfully in my laptop. If someone knows what might be the appropriate solution it would be helpful...!

Greatest Common Divisor

To become a good coder, knowledge of concepts of maths are essential. GCD or Greatest Common Divisor of two or more integers, when at least one of them is not zero, is the largest positive integer that divides both the numbers completely without leaving a remainder.
    For example GCD of 8 and 12 is '4'. Wondering Y?? Lemme Xplain :P

Let us assume two integers 'a' and 'b'. Let 'x' be the largest integer that can divide both 'a' and 'b' completely without leaving a remainder. Any guess about , What can be the range of 'x'??

1<='x'<=minimum(a,b)

Y so?? Let us consider the example above shown:- gcd(12,8)=4 . let me write the possible values of x for 'a'=12 and 'b'=8 x={1,2,3,4,5,6,7,8}; if we consider an integer greater than 8 then then the value of (b/x) is 0 because the denominator in such a case becomes greater than the numerator so the ratio is less than 1. Now, From all the values of set 'x' the numbers that divide 'a' and 'b' completely are [1,2,4], but among these three values the largest number that divides both 'a' and 'b' completely is '4'. Hence gcd(12,8)=4.

Now how to compute gcd very fast... A serious issue :D

Before that lemme show some of the properties of divisibility that we will need in future. Theorem 1 : let 'a' be an integer and 'b' be a positive integer, then there are unique integers q and r, with 0<=r<b such that a=(b*q)+r : Rule of divisibility. That is if we divide 'a' by 'b' then 'q' denotes the quotient and 'r' denotes the remainder and we can write them as a=(b*q)+r. for example a=9 and b=2. So when 9 is divided by 2 we get 4 as our quotient and 1 as the remainder. So 9=(4*2)+1. And the remainder is always 0<=r<b.

Theorem 2. If 'a' is divisible by 'x' and 'b' is also divisible by 'x', then (a+b) is also divisible by 'x' as well as (a-b) is also divisible x. Reason :- If 'a' is divisible by x we can write it as a=q*x+0

for some quotient q and remainder r=0

      Similarly , if 'b' is divisible by 'x then
                     b=k*x+0

     for some quotient k and remainder r=0

     Now, a=q*x            :-equation 1
          b=k*x            :-equation 2
     So =>a+b
        from equation 1 and equation 2
        =>( q*x ) + ( k*x )
        taking x common we get
        =>x*( q+k )
     So we get,
         => ( a+b ) = x*( q+k )
         => ( a+b ) = x*( q+k ) + 0          :-equation 3
         let u=( a+b ) and  v = ( q+k )
         =>    u    = x*v + 0
     So, u is divisible by x , as the equation states because the remainder part is zero.
     Thus, as u=(a+b) , so, (a+b) is divisible by x . 
     Hence Proved

Similarly we can show that (a-b) is divisible by x. You can check this by yourself :) Just start with (a-b) instead of (a+b) and follow the steps above.

Now back to GCD .. Hell yeah. Let 'a' and 'b' be two integers and let 'g' be their greatest common divisor. So, gcd(a,b)=g;

So 'g' is an integer that divides both 'a' and 'b' completely without leaving any remainder,So we can write them as :

'a' is divisible by 'g'. So, => a=p*g+0 :equation 4 'b' is divisible by 'g'. So, => b=q*g+0 :equation 5

here p and q are the quotients when a and b are divided by g respectively.

Now, By rule of divisbility if we divide a by b , we can write the equation as: a=t*b+rem here t is the quotient and rem is the remainder. Now, =>a-t*b=rem Substituting the values of a and b from equation 4 and 5 we get: =>(p*g) — t*(q*g) = rem Taking g as common we get: =>g*( p — (t*q) ) = rem This equation can be rewritten as : =>[g*{ p — (t*q) }] + 0 = rem Sounds similar right. This means that 'rem' is divisible by 'g', as the remainder of the equation is zero. So, 'g' not only divides 'a' and 'b' completely but also divides the remainder obtained when a is divided by b.
Thus we can say that: gcd(a,b)=gcd(b,remainder when a is divided by b) we derived it right and this even reduces our computations now So, gcd(a,b)=gcd(b,r) where r is the remainder when a is divided by b. Now, terminating condition because we cant forever go on computing the remainder and never stop. We need to stop right.

Remember i told u that the set of values 'x' for gcd(a,b) is actually 1<=x<=minimum(a,b). Assume a>=b. Now what if 'b' divides 'a' completely without leaving a remainder in such a case the largest integer dividing both 'a' and 'b' is 'b' itself , So the set of x contains 'b' as a possible value for our gcd computation and also 'b' is the largest value in our range of set 'x' hence gcd is 'b' itself. Example gcd(12,4)=4 itself. Baaammmmmm. Now we got our trick to end computing.

Lets start coding:

C Code:

#include<stdio.h>
int gcd(int a,int b)
{
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}
int main()
{
    int a,b;
    printf("Enter the numbers\n");
    scanf("%d %d",&a,&b);
    int x=gcd(a,b);
    printf("GCD of %d and %d is %d\n" ,a,b,x);
    return 0;
}

ideone link :-

Java Code

import java.io.*;
import java.util.*;
class GCD
{
 public static void main(String args[])throws IOException
 {
  Scanner sc=new Scanner(System.in);
  System.out.println("Enter the numbers");
  int a=sc.nextInt();
  int b=sc.nextInt();
  System.out.println("GCD of a and b is "+gcd(a,b));
 }
 static int gcd(int a,int b)
 {
  if(a%b==0)
   return b;
  else
   return gcd(b,a%b);
 }

}

ideone link :-

Happy Coding. Pardon tying Errors :D

Related Questions:

1. CodeForces Problem
2. CodeChef Problem
3. Spoj Problem