Tiling Spoj 2530 and related

Time to Tile some Dominoes

http://www.spoj.com/problems/M3TILE/

http://www.spoj.com/problems/GNY07H/ (M4TILE)

http://www.spoj.com/problems/M5TILE/ (M5TILE)

(M3TILE) : https://gist.github.com/swapcoder/6738962
(M4TILE) : https://gist.github.com/swapcoder/6738982

i will explain the (M4TILE) and posted (M4TILE) and (M3TILE) codes , last one i will post later

problem can be broken up into 3 subproblems

Sub problems
Check code for related recurrence relations

UVA 10810 Ultra-QuickSort

Basically same as 11495. Just Read question carefully
and read hint related 11495.

QuickSort

Generalised QuickSort Code
Hoares and simple partition and Randomised Quick sort

uva11495 Bubbles and Buckets

The counting inversion can be done in O(n^2) with the naive algorithm.
But it will not suffice. So we need (nlogn). Counting the inversion in merge function of merge sort is good idea too do this. while merging if second array is having small element then the elements remaning in first array all have conflict with this element so add that and thats it.
or

create binary search tree ,step by step go on inserting the elememnts, and with every node keep track of nodes that are right side of current node and
while inserting increment  the current nodes right count if inserted element falls to right (that is it is greater than current node element).and else if falls to left(that means inserted element is smaller than current node and there are right_count_of_current_node no of element greater than inserted element that are before inserted element so add that count) add right count to answer.

 Solution with first strategy:

UVA 696 How Many Knights

Easily find pattern after two,three test cases.  
But really interesting to see when either rows are 2 or columns are 2.

  

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define fi(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define fd(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define rep(i,n)  for(int i=0;i<n;i++)
//stl
#define sz(a) int((a).size())
#define pb push_back
#define all(c) ((c).begin(),(c).end())
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<string,int> si;
typedef pair<int,ii> iii;
typedef vector<si> vsi;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef map <string,vs> msvs;
typedef map <string,int> msi;
typedef map <string,string> mss;
#define INF 1000000000

int main()
{
   
        while(1)
        {
            int r,c;
            scanf("%d %d",&r,&c);
            if(r==0 && c==0)
            break;
   
            else if(r==1)
            printf("%d knights may be placed on a 1 row %d column board.\n",c,c);
           
            else if(c==1)
            printf("%d knights may be placed on a %d row 1 column board.\n",r,r);

      
            else if(r==2 || c==2)
            {
                int r1=r,c1=c;
                int mul=r*c,fb,y;
                fb=mul/4;
                y=mul%4;
                if(fb%2==0)
                {
                    printf("%d knights may be placed on a %d row %d column board.\n",fb*2+y,r,c);

                  
                }
                else
                {
                    int a2=ceil((float)fb/2);
                    printf("%d knights may be placed on a %d row %d column board.\n",a2*4,r,c);

                }
                  
              
            }
          
            else
            {
                if(c%2==0)
                {
                    printf("%d knights may be placed on a %d row %d column board.\n",(c/2)*r,r,c);
              
                }
                else
                {
                    int a1=(r/2)*c;
                    int a2=ceil((float)c/2);
                    if(r%2==0)
                    printf("%d knights may be placed on a %d row %d column board.\n",a1,r,c);
                    else
                    printf("%d knights may be placed on a %d row %d column board.\n",a1+a2,r,c);
              
                }
            }  
        }


    return 0;
}

HR Red John is back

https://www.hackerrank.com/contests/101july13/challenges/red-john-is-back

Easy solution with the little dp and prime with very mild constraints

uva 10892 LCM Cardinality

Easy lcm problem , where need to store all divisors of the n (no given) and then exploit bruteforce to find lcm of which pair of the divisors is equal to n (number given)

UVA 10717 Mint

Simple Prime number problem with sieve involved. Else part is brute force. Learn to use brute force seeing limits.

UVA10539 Almost Prime Numbers

Another easy one for prime number. Here u have to deal with the figures
after getting all primes just brute force . the no will be not large so u can afford it.
the exponential function grows very fast therefore no of almost prime are less(within computation limits)

UVA543 Goldbach's Conjecture

It is easy problem related to prime number
use sieve of erotheses

POJ 2663 Tri Tiling

Solution

DP practice problems

Chest of Drawer Practice DP

Chest of Drawers - Problem D of ACM World Finals Warmup

2008

You are given a chest of drawers with N drawers, which

can be locked.

You want to have exactly S secured drawers.

But not all locked drawers are secure.

A locked drawer is secure:

If it’s either the top drawer.

If the drawer directly above it is locked aswell.

Constraints:

0 <= N <= 65

0 <= S <= 65

You have to count how many ways you can locked N

drawers to give you S secure drawers.

I will publish answe later


Try this POJ 2663
 

Prime problems

Learn about prime number from any standard book or competitive programming book.then  try to code basic algorithms like sieve for finding prime then try KPRIME,PRIME1,LEVY,PPERM,RESQ on codechef these are very simple and interesting problem and also their editorial is avalable . So,that u can surely learn something. I will add some other problem title related in somedays.

836 Largest Submatrix

The 2D range sum DP problem recurrence relation same as 836
only change is we have to consider submatrix wih max 1's and (not maxsum)
have a look at condition on line no 106

11242 Tour de France

This is complete search problem only catch in this problem to fix and round the ouput note cout at the end

435 Block Voting

This is problem of Complete search.Though problem statement is not clear it can be understood with the test case.It states to find no of winning combination including particular party. Search all combinations

10360 Rat Attack

This is easy backtracking problem which can be solved in O(n*d^2) complexity.
But this could also solved in 1025^2 using dp using range sum.
take input and make entries in dp[1025][1025];
Preproccess the 1025x1025 array using :
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];
then, use recurrence relation to find max
        dp[i+d][j+d]-dp[i+d][j-d-1]-dp[i-d-1][j+d]+dp[i-d-1][j-d-1]; for all (i,j) between d+1 to 1025-d

10363 Tic Tac Toe

This is easy problem but there is one catch multiple winning are allowed(as it is not mentioned in problem) , i tried both ways and got AC on commenting that condition (line : 121 in following code)

573 The Snail

This is very simple problem but to avoid complications of floating point just multiply with the 100