SIMPLE TUTORIAL PROBLEM

Problem Link:
http://www.spoj.com/problems/SODUJ/

CODEFORCES ROUND #278 Div.2 PROBLEM A : GIGA TOWER

Problem Link : http://codeforces.com/contest/488/problem/A

We just need to make an function of finding whether a number has a digit 8 or not.....  &

For -9<x<0     answer will be 8-x

For x>=0       iterate up from x till the answer

For x<-8       iterate  down from abs(x) till the answer

Sample Test Cases:

                           Answer

-192                       3/-189

192                        6/198

-7                         15/8

 Don't forget to take number as long integer :P

CODEFORCES ROUND # 277.5 Div2 C. Given Length and Sum of Digits...

Problem Link: http://codeforces.com/problemset/problem/489/C

Death Call Problem!!! :P

If number has length of m and having sum as S
then minimum amd maximum nos. could be found out by ::

Set MAXNO[m]= 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...................
Set MINNO[m]=1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...........

Increment the nos. in MAXNO from left till 9 and jump to its right till we get the required sum S
 Similarly ,
Increment the nos. in MINNO from right till 9 and jump to its left till we get the required sum S

These are our required results!!!!!!11

Dont miss the testcase: 1 0
Expected Output: 0 0

Code Link:  http://pastebin.com/eujy24nt

MINIMUM DISTANCE BETWEEN NODES IN TREE

Distance b/w two nodes in tree such as:

                                                              1
                                     2                                                  3
                      4                        5                           6                            7
             8             9          10          11           12           13         14           15

Ex.: 
 Distance b/w nodes 8 and 15 =>>6   
        ( 8->4->2->1->3->7->15)    6 vertices

 Distance b/w nodes 8 and 10=>>3

     while(i!=j)
     {
                if(i>j)
                     {
                        i=i/2;
                         count++;
                      }
                else
                    {
                       j=j/2;
                       count++;
                    }
      }

where i is intial node and j is final node :)

SPOJ PROBLEM 3921: THE GREAT BALL (BYTESE2)

Selection Process :)
Code:

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        vector< pair<int,int> > v;
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            v.push_back(make_pair(a,b));
        }
        /*for(int i=0;i<v.size();i++)
        {
        cout<<v[i].first<<" "<<v[i].second<<endl;
        }*/
        sort(v.begin(),v.end());
        int max=0;
      for(int j=0;j<v.size();j++)
      {
        int count=1;
        for(int k=0;k<v.size();k++)
        {
        if(k==j)  continue;
        if(v[k].first<v[j].second && v[k].second>=v[j].second)
              { count++;
               //cout<<"h"<<endl;
               }
        }
        if(count>=max)
          max=count;
        }
        cout<<max<<endl;
    }
    // your code goes here
    return 0;
}

YET ANOTHER PROBLEM BASED ON SIEVE OF ERASTOTHENES

Problem Link: http://www.spoj.com/problems/ETF/

Euler’s totient function:

The number of positive integers, not greater than n, and relatively prime with n, equals to Euler’s totient function φ (n). In symbols we can state that
φ (n) ={a Î N: 1 ≤ a ≤ n, gcd(a, n) = 1}
This function has the following properties:

1. If p is prime, then φ (p) = p – 1 and φ (p^a) = p a * (1 – 1/p) for any a.
2. If m and n are coprime, then φ (m * n) = φ (m) * φ (n).
3. If n = , then Euler function can be found using formula:

φ (n) = n * (1 – 1/p1) * (1 – 1/p2) * ... * (1 – 1/pk) 

For more http://en.wikipedia.org/wiki/Euler%27s_totient_function

Modify sieve as: all the multiples of prime nos. would have prime no. as divisor. So, just modifying it there only would produce the desired result.

Euler Function:

void sieve()
{
    prime[0]=0;
    prime[1]=1;
    for(long long i=2;i<MAX;i++)
    {
        if(!prime[i])
            {
             prime[i]=i-1;//For prime nos. euler(i)=i-1  Property 1
                
                for(long long j=2*i;j<MAX;j=j+i)
                {
                    if(!prime[j]) 
                           prime[j]=j; //First visit to the no.
                    prime[j]=prime[j]/i*(i-1); 
     //it couldn't be written as prime[j]*(i-1)/i as it gives 0 :P                }
            }
    }
}

But it gives TLE .Still some more modifications are needed up :)


 

SIEVE OF ERASTOTHENES BASED SPOJ PROBLEMS

PROBLEM LINK:
http://www.spoj.com/problems/PRIME1/
http://www.spoj.com/problems/APS/
http://www.spoj.com/problems/AFS/

Approach is pretty same for all three problems.
Precomputation is needed .
Common approach to problems is initialize them initially to 0 or 1 as per ur choice and sieve it out.

Problem 1: http://www.spoj.com/problems/PRIME1/

Take an array
Mark all the multiples of no. by 1 or 0 
Pseudo Approach::
       1 2 3 4 5 6 7 8 9 10
a[n]   0 0 0 0 0 0 0 0 0 0    ==>>intial
       0 0 0 1 0 1 0 1 1 1    ==>>final
Prime nos.: 2 3 5 7  (marked with 0s)

Problem 2:http://www.spoj.com/problems/APS/

Take two arrays i.e. one for f(n) and the other for a[n]
pre-compute f(n)
marks all multiples of no. with the no.   ex.:  a[2]=2  a[4]=2  a[6]=2  a[8]=2...........................
Pseudo Approach::
           1 2 3 4 5 6 7 8 9 10
  f(n)     0 0 0 0 0 0 0 0 0 0      ==>>initial 
           0 2 3 2 5 2 7 2 3 2      ==>>final
  a[n]     0 0 0 0 0 0 0 0 0 0      ==>>initial
           0 2 5 7 12 14 21..................... ==>> final  

Problem 3:http://www.spoj.com/problems/AFS/ 

Take one array 
pre-compute the sum
add the no. to the multiple of the no.   ex.:     a[2]=1    a[4]=a[4]+2   a[6]=a[6]+2........................
Pseudo Approach::
         1   2    3    4    5   6   7   8   9
f(n)     0   0    0    0    0   0   0   0   0  ==>> initial
         0   1    1    3    1   6   1   7   4  ==>>final
a[n]     0   0    0    0    0   0   0   0   0
         0   1    2    5    6   12  13  20  24..

:) :)

C# SOLUTION TO SPOJ PROBLEM 1:TEST

Problem Link : Life, the Universe, and Everything

Code:

using System;
public class Test
{
    public static void Main()
    {
        int a=0;
        a=int.Parse(Console.ReadLine());
        while(a!=42)
        {
            Console.WriteLine(a);
            a=int.Parse(Console.ReadLine());
        }
        // your code goes here
    }
}

SPOJ PROBLEM 95: STREET PARADE (STPAR)

Problem Link 

Done using stack 

Logic is to take an test array and make operations to make an series of 1,2,3,4...........
if possible!!!!

Code::

#include <iostream>
#include<stack>
#define MAX 1001
using namespace std;

int main() {
    int n;
    stack<int> s;      
    cin>>n;
    while(n!=0)
    {
    int arr[MAX]={0},test[MAX]={0};
    while(!s.empty())   s.pop();   // clear the stack
    for(int i=1;i<=n;i++)    cin>>arr[i];
    int j=0;
    int num=1;
    
     for(j=1;j<=n;j++)
    {
           if(arr[j]==num)      // checked in array if number is present
              {
                  test[num++]=arr[j];
                  continue;
              }
            while(!s.empty() && s.top()==num)  //checked at the top of stack if num is present
            {
                test[num++]=s.top();
                s.pop();
            }
            s.push(arr[j]);
    }
    while(s.size()!=0)         // making the stack empty at the last
    {
        test[num++]=s.top();
        s.pop();
    }
    int flag=0;
    for(int k=1;k<=n;k++)      // checking whether array can be modified in the way given 
    {
        //cout<<test[k];
        if(test[k]!=k)   {  flag=1;  break;  }
    }
    if(flag==0)  cout<<"yes"<<endl;
    else   cout<<"no"<<endl;
    cin>>n;
    }
    // your code goes here
    return 0;
}

SPOJ PROBLEM 4343: EMPTY BOXES (EBOXES)

http://www.spoj.com/problems/EBOXES/
 
BRUTE FORCE
MAKE EQUATIONS AND SOLVE IT...

Let intial no. of boxes be N and let X1,X2,...............,X(T) be the no. of selected boxes in T trials

Let K be no. of smaller boxes kept in each larger boxes.

No. of empty boxes would be=:

N -X1 + (K*X1-X2) +   (K*X2-X3)....................+(K*X(T-1)-X(T))+K*X(T)=F

N + K*(X1+X2...........+X(T)) - (X1+X2...........+X(T))=F

(X1+X2............+X(T))=(F-N)/(K-1)

Total no. of boxes would be=:

N+K*(X1+X2...........+X(T))    =>   N+K*((F-N)/(K-1))

SPOJ PROBLEM 9788: Friends of Friends (FACEFRND)

STL simply makes life easier!!!!
used set stl...................
Counted all non duplicates and then subtracted up by no. of friends of Bob

Code#

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

int main() {
    int n;
    cin>>n;
    set<int> myset;
    set<int>::iterator it;
    pair<set<int>::iterator,bool> w;
    w=myset.insert(0);
    if(w.second==true)
          it=w.first;
    for(int i=0;i<n;i++)
    {
          int x;
           cin>>x;
           myset.insert(it,x);
           int num;
           cin>>num;
           for(int j=0;j<num;j++)
           {
                int y;
                cin>>y;
                myset.insert(it,y);
           }
    }
    int count=0;
    for(it=myset.begin();it!=myset.end();it++)
        count++;
    cout<<count-(n+1)<<endl;
    // your code goes here
    return 0;
}

SPOJ PROBLEM 14930: PRINCESS FARIDA (FARIDA)

Easy DP problem!!!

The problem states that it will either accept coins from ith mobnster or leave it...........
It will accept if previous sum was less than the sum of adding coins to previous to previous
sum of coins..........

 Consider dp[n] array for storing no. of coins till ith position(0-based)

So,     dp[0]=arr[0]   //no other option but just to consider it
         dp[1]=max(dp[0],arr[1])
         dp[2]=max(dp[1],arr[2]+dp[0])
         dp[3]=max(dp[2],arr[3]+dp[1])
         .
         .
         .
         dp[i]=max(dp[i-1],arr[i]+dp[i-2])

Testcase#1:
1 3 6 4 5                     
dp[0]=1
dp[1]=3
dp[2]=7
dp[3]=7
dp[4]=12

Answer is: 12

Testcase#2:
1 2 3 4 5
dp[0]=1
dp[1]=2
dp[2]=4
dp[3]=6
dp[4]=9

Answer is: 9

SPOJ PROBLEM 4: TRANSFORM THE EXPRESSION (ONP)

Realized the power of STL....

Solution:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    char a;
    stack<char> s;
    char arr[1001];
    cin>>arr;
    int len=strlen(arr);
    for(int i=0;i<len;i++)
    {
        if(arr[i]=='(')
             s.push(arr[i]);
        else if(arr[i]==')')
             {
                 while(s.top()!='(')
                 {
                     cout<<s.top();
                     s.pop();
                 }
                 s.pop();
            }
        else if(arr[i]=='+' || arr[i]=='-' ||arr[i]=='*' ||arr[i]=='/' ||arr[i]=='^' )
              s.push(arr[i]);
        else
            cout<<arr[i];  
            
    }
    cout<<endl;
    }
    return 0;
}

The problem would be made more difficult if expression wasn't in the RNP form 
like ((a^b+c)/(d/e))           RNP form: (((a^b)+c)/(d/e))

Code for that keeping my preference order as (+,-)->(*,/)  not considering ^:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a;
    stack<char> s;
    char arr[1001];
    cin>>arr;
    int len=strlen(arr);
    for(int i=0;i<len;i++)
    {
        if(arr[i]=='(')
             s.push(arr[i]);
        else if(arr[i]==')')
             {
                 while(s.top()!='(')
                 {
                     cout<<s.top();
                     s.pop();
                 }
                 s.pop();
            }
          else if(arr[i]=='+' || arr[i]=='-')
                {
                   while(s.top()!='(')
                   {
                           if(s.top()=='*' || s.top()=='/'||s.top()=='+' || s.top()=='-')
                               {
                                   cout<<s.top();
                                   s.pop();
                               }
                           else
                               break;
                   }
                  s.push(arr[i]);
                 }
        else if(arr[i]=='*' || arr[i]=='/')
                {
                   while(s.top()!='(')
                   {
                           if(s.top()=='/' || s.top()=='*')
                               {
                                   cout<<s.top();
                                   s.pop();
                               }
                           else
                               break;
                   }
                  s.push(arr[i]);
                }
        else
            cout<<arr[i];  
            
    }
}

SPOJ PROBLEM 3885: COINS GAME (MCOINS)

Nice and easy dp problem!!!!!!

First memorize state for all n and then use it for further simulation.
consider boolen array of size as specified
Mark arr[0]=0
for any i ;
Now three conditions possible :
arr[i]=1       if arr[i-1]=0
arr[i]=1       if arr[i-K]=0          ===>>>> Use up these conditions to memorize your array
arr[i]=1       if arr[i-L]=0

These conditions is such that if boy loses on i-1/i-k/i-l position then he could win next up by sweeping up 1/k/l coins and will win the game.!!!

SOLUTION TO CODEOJ PROBLEM : ITS BIT GAME (AASF PC)

http://www.codeoj.com/problemshow.jsp?q=PRACTICEP28&c=PRACTICE

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

int main() {
    int t;
    cin>>t;
    while(t--)
    {

        int arr[MAX]={0};
 
        long long int n,x;
        cin>>n>>x;
        int i=0;
        while(n!=0)
        {
            arr[i]=n%2;
            n=n/2;
            i++;
        }
        int arr2[MAX];
        fill(arr2,arr2+1000,2);      //marked non flips with 2
        int len1=i;
        for(int j=0;j<len1;j++)
          {
            if(arr[j]==1)
                 arr2[j]=0;
          }
        int arr1[MAX]={0};
        i=0;
        while(x!=0)
        {
            arr1[i]=x%2;
            x=x/2;
            i++;
        }
        int len2=i;
        i=0;
        int y=0;
        while(y<len2)
        {
            if(arr2[i]==2)
               {  arr2[i]=arr1[y];   y++;  i++;  }
              else
                 i++;
        }
        for(int u=i;u<1000;u++)
        {
            if(arr2[u]==2)
                arr2[u]=0;
        }
        long long int res=0;
        for(int f=0;f<1000;f++)
        {
            res=res+(arr2[f]*pow(2,f));
        }
        cout<<res<<endl;
                
    }
    // your code goes here
    return 0;
}

SPOJ PROBLEM 18240: GENIE SEQUENCE (KURUK14)

Genie sequence defined in the problem statement of an value n would be like:
   n-1 , (1/n-2) , (2/n-3) , (3/n-4)................................, (1/n-2) , (2/n-3) , (3/n-4) ,n-1

 Note: / defines OR i.e. 1 or n-2

So, count of n-1=2
      count of n-2=2/0  for count=0    count of  1=2  ||  count of 1=1  & count of n-2=1
      and likewise for other elements in array.

check till (n-2)/2   it also being inclusive 
costed me an WA!!!!!!!

Check it out Easy Problem!!!!   

GCD Function>>>

Greatest common divisor of two numbers is highest number smaller than or equal to minimum of two numbers which divides both numbers.
Algo would be like:
 a,b<=10^5
          for(int i=1;i<=min(a,b);i++)
                 {     if((a%i==0)&& (b%i==0))
                                  gcd=i;   }

More optimized algo given by euclid algorithm:
a,b<=10^9
Recursive definition:
int gcd(int a,int b)
{
if(b==0)
     return a;
else
      gcd(b,a%b);
}

Even more optimized algo for very long numbers 
a,b<=10^200
Calling Function: gcd(a,mod(str,a));

int mod(char str[],int d)
{
    int r=0,i;
    for(i=0;str[i];i++)
    {
        r=10*r+(str[i]-'0');
        r=r%d;
    }
    return r;
}
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        gcd(b,a%b);
}

So Any gcd could be find out using above mentioned algos according to situations


Findng out lcm using gcd function

lcm(a,b)*gcd(a,b)=a*b;

SPOJ PROBLEM 2:PRIME GENERATOR (PRIME1)

The problem though has virtually the simple image logic to be figured out but it may cause to
most cruel spoj error "TIME LIMIT EXCEEDED".
The question has many different logic but the problem has been set to make use of an algorithm
known as "SIEVE OF ERASTOSTHENES".
This algo just sieves down the prime nos. .
You would surely love the algo.
Youtube link:  https://www.youtube.com/watch?v=eKp56OLhoQs
Wikipedia link:  http://en.wikipedia.org/wiki/Sieve_of_Erastosthenes

Quick link to Dev C++ Download Mirror

http://sourceforge.net/projects/dev-cpp/files/Binaries/Dev-C%2B%2B%204.9.9.2/devcpp-4.9.9.2_setup.exe/download?use_mirror=kaz

WHAT TO CHOOSE IN ENRGY MANAGEMENT SYSTEM:OPTIMIZED BATTERY / MAXIMIZE BATTERY HEALTH

Maximize Battery Health generally means Energy Management will try to squeeze out as many minutes as possible when the laptop is running on the battery.

Optimized Battery Health means Energy Management limits the battery charge to 60% so that the battery life is not prematurely shortened. Basically between a battery is charged to 100% for a prolonged period of time it can actually shorten the life of the battery. That means if the battery can last 5 hours in normal usage when it is new, that battery life will decrease somewhat quickly over time if the battery is always kept at 100% charge. It has to do with the chemistry of how lithium battery works.
the answer taken from different sites.

So it is preffered to use it in Optimized Battery Health if u always keep it plugged in , you arent short of electric power!!!!!!!!!!!!!!!!

WHEN YOU HAD WORKED ON TURBO PLATFORM............

It sometimes happen to many people as they are working on turbo c++ platforn and are new to present trending platform like dev cc++ ,visual studio,etc.
so need to worry
Basic code goes like this:
#include <iostream>
using namespace std;

int main() {
    // your code goes here
    return 0;
}
to include any other use 'c' before it
for ex.:  <stdio.h>    ---->   <cstdio>
rest all goes same as before!!!!!!!!!!!

SPOJ PROBLEM (CLASSICAL) 5976: TRGRID

the questioon is simply brute force approach
USE PEN PAPER
you would be getting simple logic that if n<m(   m has some conditions )  
if( m<=n)   ( n has some conditions)
question takes time to understand the logic but once you are over with logic task
a simple code is to be encoded........................

SPOJ PROBLEM (CLASSICAL) 11063: AP2

Simple concepts of 11th standard are used of progression
third and last third add up to give something in sum of AP equation
use that hint & problem solved!!!!!!!!!!

SPOJ PROBLEM (CLASSICAL) 1: LIFE UNIVERSE

The problem is very simple.
No constraints problem whatsoever.
Simple integer se kaam chal jaye ga.
The basic approach is to not be confused that input is taken in an array.
The input & output are simuntaneous with each other.
Take single input & use accordingly loop condition.
& the problem is done!!!!!!!!!

Getting Started.........

Everyone new to this arena of complicated trends should surely be having slow and simple start.
Sometimes it happens that he or she may just get started with any troublesome programming sites
and simply losing their confidence of not understanding a single bit of question!!!!
Before joining up any programming platform , you must be perfect about the basics of programming
and also the brute-force techniques at the intial sttage of your esteemed programming career.

Secondly, you should know that solving problems in spoj or any other website is not your objective.
The basic objective is to decode the concepts concealed in the problem.
Anyone could just submit a problem in these sites as the solutions are easily available in the virtual world so-called 'internet'.

Be Cool !!!!

WHEN YOU KNOW NOTHING ABOUT PROGRAMMING

An indian level IT institute sounds better!!! isn't it??
But the truth behind mighty walls made up of Ambuja CEMENT is expectedly different.
From no where to vast ocean of printf ,scanf, iostream and many illogical voculabaries faced
might pretend as proudy things to be boast of .