SHAHBG Spoj

Logic :

        In each iteration keep count of groups and when a new person add in chain just see that if its left and right position are empty or not if they both are empty then groups will increase by 1 if both filled then decrease count of group by 1 otherwise nothing.
(Why this approach will work well try to simulate this in your mind or on paper ;) )


Below you can see code also :


#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

bool Line[1000000];

int main()
{
int Q;
scanf("%d", &Q);

int ans = 0;
while(Q--) {
int P;
scanf("%d", &P);
bool Left = false;
bool Right = false;
if(P - 1 > 0 && Line[P - 1]) Left = true;
if(P + 1 <= 20000 && Line[P + 1]) Right = true;

if(Left && Right) {
ans--;
} else if(Left || Right) {
ans += 0;
} else {
ans += 1;
}
Line[P] = true;
printf("%d\n", ans);
}
puts("Justice");
    return 0;
}


Happy Coding :)

UCV2013I Spoj

Logic :

     For this problem only a image is enough to understand logic. 
     Which is

Source: Click Here

now we can apply sine formula to find solution.

Below you can see code also: 

#include <iostream>

#include <sstream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cctype>

#include <string>

#include <vector>

#include <list>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <functional>

using namespace std; 

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;

#define REP(i,n) for(int i=0;i<(n);i++)

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

const int INF = 1<<29;

typedef long long ll;

inline int two(int n) { return 1 << n; }

inline int test(int n, int b) { return (n>>b)&1; }

inline void set_bit(int & n, int b) { n |= two(b); }

inline void unset_bit(int & n, int b) { n &= ~two(b); }

inline int last_bit(int n) { return n & (-n); }

inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

template<class T> void chmax(T & a, const T & b) { a = max(a, b); }

template<class T> void chmin(T & a, const T & b) { a = min(a, b); }

/////////////////////////////////////////////////////////////////////

int main()

{

while(true) {

double r;

double N;

scanf("%lf%lf", &r, &N);

if(r <= 0 || N <= 0) break;

printf("%.2lf\n", r/sin((acos(-1) * 0.5) / N));

}

    return 0;

}

Happy Coding :)

TIPTOP Spoj

Logic : 

           First of all we will try to solve problem using brute force solution.

           

           For Given N find all divisors count them and if count is Odd then answer will be 

           ''Yes"  otherwise "No".

           So finding divisors of a number can take Sqrt(N) time and N can be 10^18 that mean

           time complexity will be O(T*sqrt(N)) which will fail and give time limit exceeded.

           

           Now we will write number of divisors from N = 1 to 50 and then find some pattern.

           (Why 50 well you can take 1000 :P it depend on you)

           

            

     1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6

      now list all number N where count of divisors are odd(Why? Odd well there are so many even numbers so try to find relation from small set)

          N = 1 , count 1

          N = 4,  count 3

          N = 9,  count 3

          N = 16, count 5

          

           I think thats enough to find a relation or pattern , so by looking at N we can say that if count of divisors are odd then that number must be a perfect square number. 

          

           Now our problem reduced to detect that given number is perfect square number or not

           we can apply a standard method for this one which is binary search and also we can try some hack ;) 

          so here we will see only hack approach you can read about binary search and easily apply.

  

        Hack Approach :

              Suppose given number is N , find square root of N which is built in almost all programming languages.

              SQRT_OF_N = sqrt(N)  
              now we knew that if N is perfect square then if we multiply its square root we can get N again otherwise we will get smaller number than N. :D

Below you can see solution (both approaches)

#include <iostream>

#include <sstream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cctype>

#include <string>

#include <vector>

#include <list>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <functional>

using namespace std; 

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;

#define REP(i,n) for(int i=0;i<(n);i++)

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

const int INF = 1<<29;

typedef long long ll;

inline int two(int n) { return 1 << n; }

inline int test(int n, int b) { return (n>>b)&1; }

inline void set_bit(int & n, int b) { n |= two(b); }

inline void unset_bit(int & n, int b) { n &= ~two(b); }

inline int last_bit(int n) { return n & (-n); }

inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

template<class T> void chmax(T & a, const T & b) { a = max(a, b); }

template<class T> void chmin(T & a, const T & b) { a = min(a, b); }

/////////////////////////////////////////////////////////////////////

bool SQRT(long long x) {

double sq = sqrt(x);

long long sq_l = sq;

if(sq_l * sq_l == x) return true;

return false;

}

bool BS(long long x) {

long long low = 1;

long long high = 1e9;

while(high - low >= 2) {

long long mid = (low + high) >> 1;

if(mid * mid >= x) {

high = mid;

} else {

low = mid;

}

}

for(long long i = low; i <= high; ++i) {

if(i*i == x) return true;

}

return false;

}

int main()

{

int T;

scanf("%d", &T);

int t = 1;

while(T--) {

long long N;

scanf("%lld", &N);

printf("Case %d: ", t++);

if(BS(N)) {

puts("Yes");

} else {

puts("No");

}

}

    return 0;

}

Happy Coding :)

            

MKEQUAL

Logic : 

            we can make N - 1 equal easily by choosing a single element for decreasing.

             so according to first statement answer will be atleast N - 1 now if see this test case

             

             N = 4   Arr = {1, 9, 1, 9}
             answer is 4 because we can make 5 by choosing 1, 9 as pair and perform operation.

             

             that mean answer can be N also , now question is when it can be happen and why ?

             

 answer of above question is :

            

              If sum of numbers is divisible by n then all element changed to sum_element/n by 

              choosing two  index one with value greater than sum_element/n and other with

              smaller value at a time.

Below you can see code also

#include <iostream>

#include <sstream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cctype>

#include <string>

#include <vector>

#include <list>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <functional>

using namespace std; 

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;

#define REP(i,n) for(int i=0;i<(n);i++)

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

const int INF = 1<<29;

typedef long long ll;

inline int two(int n) { return 1 << n; }

inline int test(int n, int b) { return (n>>b)&1; }

inline void set_bit(int & n, int b) { n |= two(b); }

inline void unset_bit(int & n, int b) { n &= ~two(b); }

inline int last_bit(int n) { return n & (-n); }

inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

template<class T> void chmax(T & a, const T & b) { a = max(a, b); }

template<class T> void chmin(T & a, const T & b) { a = min(a, b); }

/////////////////////////////////////////////////////////////////////(

int main()

{ 

int T;

scanf("%d", &T);

while(T--) {

int N;

scanf("%d", &N);

long long sum = 0;

for(int i = 0; i < N; ++i) {

long long data;

scanf("%lld", &data);

sum += data;

}

printf("%d\n", N - (sum%N == 0 ? 0 : 1));

}

    return 0;

}

Spoj FANCY

LOGIC:

For this problem we will try a mathematical approach first analyze given examples that how we can apply mathematical formulas for given input.

N = 12345
there is only one way to represent this string which is One 1, One 2, One 3, One 4, One 5

N = 11112
there are 8 way to represent this string which are :
        One 1, One 1, One 1, One 1, One 2
        One 1, One 1, Two 1, One 2
        One 1, Three 1, One 2
        Four 1, One 2
        One 1, Two 1, One 1, One 2
        Three 1, One 1, One 2
        Two 1, One 1, One 1, One 2
        Two 1, Two 1, One 2
in above example we can see that 2 occurred 1 time so  there is only 1 arrangement for 2,
now analyze for 1 , 1 occurred 4 time so we can represent it in 8 ways , now question is why?
as we know we can decompose 4 in 8 ways like:
       1 + 1 + 1 + 1
       1 + 1 + 2
       1 + 2 + 1
       1 + 3
       4
       2 + 1 + 1
       2 + 2
       3 + 1
       so here problem is in how many ways we can split K where K is some number here K = 4
Well this standard problem and you can find solution using two methods 1. Pattern recognition 2. Combinatorics

1. Pattern recognition :-
               N = 1      Ways  -> 1
               N = 2      Ways  -> 2
               N = 3      Ways  -> 4
               N = 4      Ways  -> 8
            we can find Ways using pen paper and by looking pattern we can say that it can be 
            2 ^ (N - 1)     ::where  ^ is power sign
            but this is trial and error method and no proof of its correctness 

2. Combinatorics:-  
              N = 1    Ways   ->   0 C 0 = 1
              N = 2    Ways   ->   1 C 0 + 1 C 1 = 2
              N = 3    Ways   ->   2 C 0 + 2 C 1 + 2 C 2 = 4
              N = 4    Ways   ->   3 C 0 + 3 C 1 + 3 C 2 + 3 C 3 = 8
              :: Where nCr mean ways to choose r items from n items  n! / (r! n-r!)   where '!' 
             mean factorial
             so for some N it will be (N - 1) C 0 + (N - 1) C 1 + ..... + (N - 1) C (N - 1) and we know                    that it is equal to 2 ^ (N - 1) (Need proof then google it ;) ) 
             Well why we choose N - 1 is homework for readers :D


Now we can find ways for single element which occurring continuously K time which is 2 ^ (K - 1)
but in our problem we have many elements which are occurring.
so suppose N = a1 a2 ....aK1 b1 b2 b3 ... bK2 c1 c2 c3 ... cK3
then first of all we will find 2 ^(K1 - 1) , 2 ^ (K2 - 1), 2 ^ (K3 - 1) independently all ways in which we can arrange and then we will multiply them because order will not change
so answer will be 2 ^ (K1 - 1) * 2 ^(K2 - 1) * 2^(K3 - 1).

Below you can see code also   

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
char Str[50];
scanf("%s", Str);
int len = strlen(Str);
int cnt = 0;
int ans = 1;
for(int i = 0; i < len; ++i) {
if(i == 0) {
cnt = 1;
} else {
if(Str[i] == Str[i - 1]) {
cnt++;
} else {
ans *= (1 << (cnt - 1));
cnt = 1;
}
}
}
if(cnt > 0)
ans *= (1 << (cnt - 1));
printf("%d\n", ans);
}
    return 0;
}


Happy Coding :)
       

Spoj PUCMM210

LOGIC:

As we already have our strategy first try to write brute force solution if you are unable to figure out optimized solution.
Here brute force solution will look like:

Function(N) {
          For i = 1 to N {
                F_value_at_i  += (i * i * i)
                S_value_at_i  += (S_value_at_i_minus_1 + F_value_at_i)
                Take mode if required
         }
         return S_value_at_N
}

so we can always call Function(N) for each test case so time complexity will be O(N * T)
and it can be huge because N is at most 10^6 and T is at most 10^5 so it will be timeout.

If we look at Function we can say that we are doing repeated work so to remove repetition we will precompute and keep in cache. (Basic of DP(Dynamic Programming) :) )

Below you can see code also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

#define MXN 1000000
#define MOD 1000000003
long long F[MXN + 2];
long long Sum[MXN + 2];

int main()
{
Sum[0] = F[0] = 0;
for(int i = 1; i <= MXN; ++i) {
long long temp = i;
temp *= i;
if(temp >= MOD) 
temp %= MOD;
temp *= i;
if(temp >= MOD)
temp %= MOD;
F[i] = F[i - 1] + temp;
if(F[i] >= MOD)
F[i] %= MOD;

Sum[i] = Sum[i - 1] + F[i];
if(Sum[i] >= MOD)
Sum[i] %= MOD;
}

int T;
scanf("%d", &T);

while(T--) {
int N;
scanf("%d", &N);
printf("%lld\n", Sum[N]);
}

    return 0;
}



Happy Coding :)

Spoj MAY99_3

Logic:

So when we start to solve a problem first approach should always be brute force solution if we have no idea about problem's optimized solution, so for this problem brute force solution will be a recursion function where we try all possible cases and if we get our expected solution then return YES otherwise go on.
Now here question is when we will stop or what will be our termination condition well in this problem if we reach again same condition then we stop.

pseudocode of recursive function:-

Function(Water_in_JugA, Water_in_JugB) {
              //We can fill any jug completely 
              Answer = Function(Fill_Full_JugA, Water_in_JugB)
              Answer = Answer or Function(Water_in_JugA, Fill_Full_JugB)
             
              //We can empty any jug entirely 
             Answer = Answer or Function(0, Water_in_JugB)
             Answer = Answer or Function(Water_in_JugA, 0)

            //Transfer as much water from Jug A to Jug B, till Jug A gets empty or Jug B is completely filled or vice versa
            
            Answer = Answer or Function(Fill_JugA_until_JugA_Full_or_JugB_empty, Water_in_JugB - how much water we use to fill JugA)
            Answer = Answer or Function(Water_in_JugA - how much water we use to fill JugB, Fill_JugB_until_JugB_Full_or_JugA_empty) 
  
}

Now someone will say hey it will take O(Limit_of_JugA * Limit_of_JugB)
and that mean it will be O(10^16) because at most Limit_of_JugA can be 10^8
and yes he is right.
Now again question arise that then how we can solve it well our solution is in brute force solution
try some cases using above function and analyze it.

................ (analyzing :P)

 so when we analyze our brute force solution most critical point here is third one transfer water from A/B to B/A which can be write down as F(A, B) -> F(min(A + B, A), B - min(A, A + B)) and using other two points we can always fill one of our jug so now if we can find domain of elements we can get in our brute force solution then we can insure that we can get solution or not.
look this sequence if you find any relation

try some examples for F(A, B) -> F(min(A + B, A), B - min(A, A + B))

F(2, 5) -> F(2, 3) -> F(2, 1)

F(5, 2) -> not a valid state

F(3, 9) -> F(3, 6) -> F(3, 3) -> F(3, 0)

so if you see sequence closely you get it solution right.
someone will say no its okay for more we will try to examine our equation

F(A, B) -> F(min(A + B, A), B - min(A, A + B))
as we know if A > B then there will be no more steps but we can swap B, A right
now again why? (read problem again and convenience yourself that we can :D )

so we can right that A < B
F(A, B) -> F(min(A + B, A), B - min(A, A + B))
and if A > B then
F(B, A) -> F(min(A + B, B), A - min(B, A + B))

now again try examples
F(2, 5) -> F(2, 3) -> F(2, 1) -> F(1, 2) -> F(1, 1) -> F(1, 0) -> F(0, 1)

F(5 , 2) -> F(2, 5) same sequence

F(3, 9) -> F(3, 6) -> F(3, 3) -> F(3, 0) -> F(0, 3)

now again we analyze this sequence we can say that F(A, B) -> F(A , KA - B) or vice versa
that mean we can get expected water in any jug if it is equal to any factor of their Limit's gcd
for more details on GCD  read  wikipage. :D

Below you can see code also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
int x;
int y;
int z;
scanf("%d%d%d", &x, &y, &z);
if(max(x, y) < z) {
puts("NO");
} else if (z % __gcd(x, y) == 0){
puts("YES");
} else {
puts("NO");
}
}
    return 0;
}


Happy Coding :)