After finishing all the cakewalk DP problems on topcoder DIV-2 250 (lol they were just 3 :P) trying my hand at the DIV-2 500 DP Problems the problem attempted currently was :-srm 619 div 2 500 

here a basic simulation of the problem was to be done with the key element being location of position to be erased for the elimination (it was (current_position+(i^3)-1)) :-

//The code 

class ChooseTheBestOne 

{

    public:

int countNumber(int N) {

vector<int>dp(N,0);//create a vector<int> for employees

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

{

dp[i]=i+1;//initialize the elements

}

long long int cp=0;//please note it is of 64 bit type

for(int i=1;dp.size()>1;i++)

{

cp=cp+pow(i,3)-1;

if(cp>dp.size()-1)

{

 cp=cp%dp.size();

}

dp.erase(dp.begin()+cp);

}

return dp[0];

 }

};

It didn't work the first time though because if you declare cp as integer type it would overflow it which was the fault with my solution in the beginning but a little bit of editorial glancing rectified it . Also a huge relief that end sems got over and the discrete maths paper was .... was.... let's just not talk about it :P but still one of my lab practicals remain. Anyways if you wanna check out the problem set i am attempting check out this link :- LINK DP PROBS DIV 2 500  

Recursion greatly minimizes the effort sometimes, like here in this question (on topcoder):- Thepalindrome
instead of any DP (although on the statistics page it was written to be dp ) a simple recursive approach can be applied :- algorithm/code

//header files
//class declarations
int find(string s) 
{
 int ret=rec(s);
 return (s.size()-ret)+s.size();
}
int rec(string s)
{
 string k=s;
 std::reverse(k.begin(),k.end());
 if(k==s)
 {
  return s.size();
 }
 else
 {
  s.erase(s.begin());
  return rec(s);
 }
}
and about the endsem  of discrete maths i am not sure :P anyways gotta sleep now  :)

Easy/Cakewalk DP on topcoder :- PROBLEM LINK SRMCARDS
naive approach would be
algorithm :-
BEGIN 
//declare a boolean array ar[500]
//initialize elements with false 
for i in range (0,cards.size())
    ar[cards.begin()+i]=true  
for i in range (0,500)
    if ar[i]== true
       then ar[i-1]=false
            ar[i+1]=false
count=0
for i in range (0,500)
    if ar[i]==true 
       then count=count+1
       
return count  
END 

it was very clear how to consider states in this problem and approach from other end is also equally correct i also feel that ar[i-1]=false can be omitted , 1D -DP is very clear now but lets face some more questions ah that hackerrank question still undone :(
end sems almost over Discrete structures paper remains for tomorrow and haven't even touched it properly :P just being a bit lazy with acads .

learning DP with baby steps this problem of topcoder div2 250 SRM 467 is probably the easiest DP on topcoder PROBLEM LINK SUPER SUM
a basic O(n^3) algorithm does the desired job of filling a DP matrix
algo in pseudocode
declare a matrix ar[15][15]
[parameters k and n have already been passed]
for i in range (0,15)
     ar[0][i] = i
for i in range (0,15)
     for j in range (0,15)
           for k in range (0,j)
               ar[i][j]=ar[i][j]+ar[i-1][k]
              
return ar[k][n] 

code:-
class ShorterSuperSum {
public:
int calculate(int k, int n) {
int ar[15][15];
memset(ar,0,225*sizeof(int));
for (int i=0;i<15;i++)
{
 ar[0][i]=i;
}
for(int i=1;i<15;i++)
{
for(int  j=0;j<15;j++)
{
 for(int k=0;k<=j;k++)
 {
  ar[i][j]+=ar[i-1][k];
 }
}
}
return ar[k][n];
}

};

but here the job was easy as the states have been clearly defined still having trouble in doing a DP problem in which you start thinking from scratch but will do it asap :)

Introduction to programming end semester test ended...... my exam went just fine (neither good nor bad) , but there is a sad news, i could not qualify the qualification round of Yandex Algorithm. Yes, I couldn't even solve a single question so feeling a bit low, will try harder next year for a good rank :) Anyways back to learning some standard algorithms as well as coding, and main focus right now would be learning dynamic programming, yes i haven't done that hackerrank question of DP yet, and more to mention  a discrete mathematics end semester test is due on 28th need to learn a bit of that too. right now would be experimenting with some other people's solutions , and trying to learn something new.         

Well learning bit manipulation helped in today's codechef may-14 lunchtime solved 2/4 questions
1) problem 1 :- APPROX2
this was brute force O(n^2) algorithm to fit the time limit  :-) this is my solution
my solution
2) problem 2:- DIVSUBS
i was able to solve the problem partially ;-) 37/100 points i got i don't know why i got SIGSEGV at higher tests :(
my solution 2
and now some good news i stood 114th on the list

here is the  ranklist

yaay....... but still :P no studies for Introduction to programming end semester gotta study now

Bit Manipulation is black magic to me really i just cant figure out how sum of all subsets possible is obtained by it, so just decided to dissect the vexorian's editorial code
here is it
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

using namespace std;
#define FOR(i,a)    for(long int i = 0;i < a;i++)
#define REP(i,a,b)  for(long int i = a;i < b;i++)
static const int MAX = 100000 * 20 + 1;
bool poss[MAX];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int MinNumber(vector<int> S);
vector<int>S;
int temp,n;
cin>>n;
FOR(i,n)
{cin>>temp;
 S.push_back(temp);
}
int k=MinNumber(S);
cout<<k<<endl;
 return 0;
}
int MinNumber(vector<int> S)
{
    fill(poss, poss + MAX, false);
    int n = S.size();
    // All subsets:
    for (int mask = 0; mask < (1<<n); mask++) {
        cout<<"mask "<<mask<<endl;
        int sum = 0;
        for (int i = 0; i < S.size(); i++) {
            if (mask & (1<<i)) {
            cout<<"S[i] "<<S[i]<<" i "<<i<<endl;
                sum += S[i];
            }
        }
        poss[sum] = true;
    }
    int x = 1;
    while (poss[x]) {
        x++;
    }
    return x;
}

for input like :- 

3

1 2 3 

output is:-

mask 0
mask 1
S[i] 1 i 0
mask 2
S[i] 2 i 1
mask 3
S[i] 1 i 0
S[i] 2 i 1
mask 4
S[i] 3 i 2
mask 5
S[i] 1 i 0
S[i] 3 i 2
mask 6
S[i] 2 i 1
S[i] 3 i 2
mask 7
S[i] 1 i 0
S[i] 2 i 1
S[i] 3 i 2
7

7 is the least possible sum which cannot be generated by all the numbers of the sequence 

and i have trouble finding out how this code does it :P and i have an end semester due on monday RATS!!!!

Prefix sums did it for the second problem in codeforces div 2 round 248
Problem link :- problem 2
a code construct and algorithm will be uploaded later :P
but here is my source SOLUTION i hope i could have implemented this in the competition but hey ! rating didn't decrease as much as i thought it would  1279->1203 but still a pupil damn >:(  will try harder next time and that DP problem on hackerrank is bugging me still tommorow May LunchTime on codechef looking forward to it :)

Attempted codeforces Div-2 Round 248 couldn't even solve a single problem :'( very sad though I managed to look at other people's solutions on the site and got the concepts, but still my rating will go haywire :(
So problem 1 was basically ad-hoc  :- Problem 1 here
algorithm to deal with it  :-
BEGIN
input n
for i in range (1,n)
     input temp
     if(temp==100)
        hundredcount++
    else
       twohundredcount++
   [end of loop]
if (hundredcount%2==1) [if hundred count is odd]
   print("NO")
else if(hundredcount==0 and  twohundredcount%2==1)[hundred count is zero and two hundred count is odd]
  print("NO")
else
  print("YES")
END

Well intro to programming end semester due on monday and i am here desperately trying to learn dynamic programming :) DP to be very honest i don't get a clue at some points of time. trying to attempt a DP problem on hackerrank its easy and i don't get much of a clue . In the next post i hope to explain my approach about the DP. On USACO i am still stuck on brute force chapter hoping to search a dictionary in constant time.   

Hey there this is Gaurav Kumar feel free to reach me on facebook and Google+

FACEBOOK
GOOGLE+