Getting started with Codeforces: Part 5: Solving your second problem (Watermelon) in codeforces.

Actually this problem is easier than the first one.

You will be given a number, you have to print YES if the number can be divided into two even number, NO otherwise.

Solution strategy:

can you divide 8 into two even numbers?
Yes, because 2+6 or 4+4 
can you divide 9 into two even numbers? try all possible combination, the answer will be NO.

So, what we get so far is, if the number is even, we can divide it into two even numbers and if it's odd, we can not divide it into two even numbers.

Wait.... There is a critical case. How about 2?
even it's an even number, we can not divide it into two even number. only possible way is 1+1 where both are odd numbers. remember 0 is not considered here because it's not positive even number.

Getting started with Codeforces: Part 4: Solving your first problem (Theatre Square) in codeforces.

First of all you have to understand the problem completely. I suggest to read part 3 for that.

Let's solve a mini problem first. We consider a line instead of a matrix.

To cover a line m, with length of 6 by stick a with length of 4, we need at least 2 sticks. See image below:

Let's have another example:  m=13, a=3

we see that at least 5 stick requires to cover the line fully. if the line length were 12, only 4 stick would be enough. 

Now we can understand and calculate visually, can we calculate required number of stick mathematically? 

yes, we can. For m=13 and a=3, required stick is simply  m/a >> 13/3 >> 4.33

Wait a minutes, we can not take 0.33 stick as we are not allowed to break it. In this case, 5 stick is needed. 

For m=12 and a=3, required stick is m/a=12/3=4.0, as no partial part needed, the answer is 4. 

Simplest way to handle this with Integer data type is: 

If the line length is divisible by stick length the answer is m/a, 

If there is some reminder the answer is m/a+1. 

In C++, 

Answer  = m /a;

 If(m%a != 0) Answer++;

Simple, right?

Now, tell me how many cell in the following matrix?

36? how did you calculate that? You have calculated the number of row (6) and column (6) and multiplied them (6*6=36) instead of counting all the cell one by one, right? 

We can apply this trick solving the main problem. We will count how many square require to cover vertically and how many horizontally and then multiply them to get the answer. 

For m=6, n=6, a=4. 

Vertically requires m/a = 6/4 = 1.5 = 2 (round up) 

Horizontally requires n/a = 6/4 =1.5 = 2 (round up) 

So, total minimum required square is 2*2 = 4. 

That's it...... 

Nope, That's not all actually, you will get "Wrong Answer" verdict. Look at the constraints. 

what if the input is m=10^9, n=10^9 and a=1? Answer will be 10^18 which is out of Integer range, in that case, you need to use "long long" data type instead of "integer". 

Next: Solving your second problem in codeforces

Getting started with Codeforces: Part 3: Understanding your first problem (Theatre Square) in codeforces.

As you have found that Theatre Square is the easiest problem according to sort described in Part 2.

Let's try to understand the problem in simplest way:

There is a m*n size rectangle and a*a size square given, you have to fill the rectangle using minimum number of square. 

Let's understand the problem in details with sample input: m=6, n=6, a=4. 

Considering the rectangle is colored red and square colored green as below. 

Remember, You have to use the square straight and can not break the square. You have to cover the rectangle fully, no problem if you cover more. 

Trying with 1 square: 

We see the rectangle (red color) is not covered completely. 

Trying with 2 square: 

still not covered. 

Trying with 3 square:

You can see there is 4 red units is not covered yet. 

Trying with 4 square: 

CIAO!!, now the red rectangle is completely covered. Thus we need minimum of 4 square of given size to cover the given rectangle fully. That's why the sample answer is 4

Next:  Solving strategy of this problem

Getting started with Codeforces: Part 2: Find out easiest problem.

It's always better to start with the easiest problems first. To find easiest problems, follow the steps.

Step 1: First of all, login to you account. [read previous post for registration and login]

Step 2: Click on "PROBLEMSET" tab. or go http://codeforces.com/problemset directly.

Step 2: You will see a list of problems sorted according to the problem added date.

Step 3: But this is not the easiest list. Problems with maximum solve is the easiest. to sort the problem list according to maximum number of solve, click on the Solved button as marked red in the picture below.

You will notice the list has changed. This is the easiest list. You can also find the list by the following link.
http://codeforces.com/problemset?order=BY_SOLVED_DESC

Step 4: Click on the first problem. That's the easiest to start with.

Next Post: Understanding your first problem (Theatre Square) in codeforces.

Getting started with Codeforces: Part 1: Opening an account

Step 1: Open your browser. Type codeforces.com and hit enter.

Step 2: You will see similar page as picture below. Click on Register button (marked in red circle in the picture below) or goto http://codeforces.com/register directly.

Step 3: Now Fill-up the form and then click Register button below.
Here, 'Handle' is your desire username. If your desire username is already taken try a new one. Don't forget your username, it will require each time you login to codeforces. Email is your active email account. In Password, type a new password for your codeforces id, write the same password again in Confirm Password box.

Step 4: After clicking register button, codeforces will send an email verification link in your email account. Login to your email, open the mail (inbox or spam folder) and click on the activation link. .
Your account is ready to use now.

Step 5: After your account being activated, you can go to codeforces.com and click Enter (marked red in the picture below) to login to your account.
You could also use http://codeforces.com/enter directly.

Step 6: Type your Handle (username) and password as you put in the form while registration. And click Login button. You could also check "Remember me for a month" if you wish to login automatically in your browser for next 30 days.

After successful login, you will see your Username and Logout button instead of Enter and Register button as below.

Now, you have created and logged in to your codeforces account successfully.


Next Post: How to find out the easiest problem in codeforces for practicing.

Fermat's Chirstmas Theorem ( UVALive 4088, Regionals 2007 >> Africa/Middle East - Arab and North Africa)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 1000005

bool stats[MX];
vector<int>prime;
vector<int>sqp;


void PrimeGenerate(int n)
{
    int sq=sqrt(n);
    for(int i=3; i<=sq; i+=2)
    {
        if(!stats[i])
            for(int j=i*i; j<=n; j+=i+i)
                stats[j]=true;
    }
    for(int i=2;i<=n;i+=2) stats[i]=true;

    prime.push_back(2);
    for(int i=3; i<=n; i+=2)
        if(!stats[i])
            prime.push_back(i);
return;
}

void squareRootGen(int n)
{
    int sq=sqrt(n);
    for(int i=1;i<=sq;i++)
        for(int j=i+1;j<=sq;j+=2)
        {
            int mul=i*i+j*j;
            if(mul>1000000) break;
            if(!stats[mul])
                sqp.push_back(mul);
        }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, L, U, x, y;
    string s;
    char ch;
    PrimeGenerate(1000000);
    squareRootGen(1000000);
    sqp.push_back(2);
    sort(sqp.begin(), sqp.end());
    while(cin>>L>>U)
    {
        if(L==-1 && U==-1) break;
        int x = upper_bound(prime.begin(), prime.end(), U) - lower_bound(prime.begin(), prime.end(), L);
        int y = upper_bound(sqp.begin(), sqp.end(), U) - lower_bound(sqp.begin(), sqp.end(), L);
        cout<< L <<" "<<U<<" "<<x<<" "<<y<<"\n";
    }
return 0;
}

Wooden Sticks (UVALive 2322, ZOJ 1025, HDU 1051, POJ 1065, SPOJ MSTICK, Regionals 2001 >> Asia - Taejon)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100000


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n;
    pair<int, int> pii[5002];
    bool vis[5002];
    string s;
    char ch;
    cin>>tc;
    while(tc--)
    {
        CLR(vis);
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>pii[i].first>>pii[i].second;
        sort(pii, pii+n);
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            if(!vis[i])
            {
                cnt++;
                vis[i]=true;
                int cur=i;
                for(int j=i+1;j<n;j++)
                    if(!vis[j])
                        if(pii[j].second>=pii[cur].second)
                        {
                            vis[j]=true;
                            cur=j;
                        }
            }

        }
        cout<< cnt <<"\n";
    }
return 0;
}

Change (UVaLive 3004, Regionals 2004 >> South Pacific)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100000


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, notes[]={2000, 1000, 500, 200, 100, 50, 20, 10, 5}, cst, ofr, chg;
    double cost, offer;
    string s;
    char ch;
    while(cin>>cost>>offer)
    {
        cost+=.005, offer+=.005;
        cost*=100.0, offer*=100.0;
        cst=cost, ofr=offer;
        //cout<<offer<<" "<<cst<<endl;
        if(cst==0 && ofr==0) break;
        if(cst%5==1) cst-=1;
        else if(cst%5==2) cst-=2;
        else if(cst%5==3) cst+=2;
        else if(cst%5==4) cst+=1;

        if(cst>ofr) cout<<"Not enough money offered.\n";
        else if(cst==ofr) cout<<"Exact amount.\n";
        else
        {
            chg=ofr-cst;

            int space=0;
            for(int i=0;i<9;i++)
            {
                int cnt=0;
                while(chg>=notes[i])
                {
                    cnt++;
                    chg-=notes[i];
                }
                if(cnt)
                {
                    if(space) cout<<" ";
                    space=1;
                    if(i<5)
                        cout<<"$"<<notes[i]/100<<"*"<<cnt;
                    else
                        cout<<notes[i]<<"c*"<<cnt;
                }
            }
            cout<<"\n";
        }

    }
return 0;
}