Monthly Archives: October 2015

Spoj UCV2013A solution

Spoj UCV2013A solution. Spoj Counting Ids Solution.

Category: AdHoc, Maths

In this question, we need to sum Ni where 1<=i<=l. We need to sum taking their modulus with 100000007.

We use two variables to derive the answer.

We keep multiplying (and taking mod), then for each ‘i’ we add this answer to our finalAns variable.

Algorithm:

  1. Initialise finalAns=0, tempAns=1
  2. Multiple tempAns with N,(take mod)
  3. add tempAns to finalAns
  4. Repeat above steps for all i such that 1<=i<=l.

Spoj UCV2013A solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007

int main() {
   int n,l;
   LL finalAns,tempAns;
   scanf("%d%d",&n,&l);
   while(n && l)
   {
      tempAns=1;
      finalAns=0;
      for(int i=0; i<l ; ++i)
      {
         tempAns=(tempAns*n)%mod;
         finalAns=(finalAns + tempAns)%mod;
      }
      printf("%lld\n",finalAns);
      scanf("%d%d",&n,&l);
   }
   return 0;
}

Spoj VENOM solution

Spoj VENOM solution. Spoj Touch of Venom Solution.

Category: AdHoc

This article is contributed by SuperWoman.

In this question we need to print the value of time, till the guy survives.

Explanation:

We know that at time = 1,
H reduces by P and if H is still greater than zero, then in the subsequent step i.e. time=2, H can be replenished by amount A.

Value of P keeps increasing 2P, 3P and so on.
And this process continues till H becomes less than or equal to zero.
We have to output that unit of time at which the process stops.
It can be seen that such a unit of time will always be an odd number.

Time Health
Time=1 H-P
Time=2 H-P+A
Time=3 H-P+A-2P
Time=4 H-P+A-2P+A
Time=5 H-P+A-2P+A-3P
Time=t H – (1+2+3…+n)P – (n-1)A

Time and n follow the following relation:

t = 2n-1

To find  n we just need to solve the following equation:

      H – (1+2+3…+n)P – (n-1)A <= 0

=>       H – P(n)(n+1)/2 – (n-1)A <= 0

=>       2H – P(n)(n+1) – 2(n-1)A <=0

=>      Pn2  + n(P-2A) + 2(A-H) <=0

=>      n = (-(P-2A) ± (√(P-2A)2 – 8P(A-H)))/2P

Since time should obviously be positive we calculate:

n =ceil (-(P-2A) + (√((P-2A)2 – 4P(A-H))))/2P)

 

NOTE: We have taken adding and subtraction in one step,whereas in the given question they are counted individually, so when calculating the answer, the actual number of steps is to be doubled:

ans = n + n -1

1 is subtracted as in the final step only subtraction is done and addition is not done.

Spoj VENOM solution code:

Here is the working code:

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

int main() {
   int t,H,P,A;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d%d",&H,&P,&A);
      if(H<=P)
      {
         printf("1\n");
         continue;
      }	
      double term1 = P-2*A;
      double term2 = A-H;
      double SqrtTerm=sqrt( term1*term1 -8*term2*P);
      long long ans=0;
      ans=ceil((SqrtTerm-term1)/(2*P));
      
      ans+=ans-1;
      printf("%lld\n",ans);
   }
   return 0;
}

Spoj LENGFACT solution

Spoj LENGFACT solution. Spoj Factorial length solution.

Category: AdHoc, Number Theory

In this question, we need to print the length of N! or the number of digits in N!

There can be two cases:

  1. Base(trivial cases) for all N<=3, the ans is 1.
  2. For all N>3, we use the following approximation, that  gives the answer.
    ans=ceil( log10(2*pi*n)/2 + n*log10(n/ln10)).

Where log10() is the library function, and piln10 are constants.

Spoj LENGFACT solution code:

Here is the working code:

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

#define pi 3.141592653589793 
#define ln10 2.7182818284590452353 

int main() 
{ 
   int t; 
   long long int ans,n;
   scanf("%d",&t);
   while(t--)
   {
      ans=0;
      scanf("%lld",&n);
      
      /*The length of factorials 
      for numbers <=3 is 1*/
      if(n<3) 
         printf("1\n");
      else
      {
         /*This formula gives an approximate answer
         for the number of digits in the N!*/
         
         ans=ceil(log10(2*pi*n)/2 + n*log10(n/ln10)); 
         printf("%lld\n",ans);
      }
   }
   return 0;
}

Spoj HUBULLU solution

Spoj HUBULLU solution. Spoj Hubulullu solution.

Category: Game Theory

In this question, the player who starts always wins the game.

Explanation:

  • It is trivial for N = 1.
  • For N > 1, assume that the first player will lose (the game starts with a losing state). This means all possible moves will lead to a winning state. Let’s pick 1. Now, it is the second player’s turn. Let x be the number he will pick to win this game. Consequently, the state after these 2 picks is a losing one. Note that by picking x at the first turn, the first player can also reach this losing state. This contradicts our above assumption.
    Hence, the first player always wins the game.

Spoj HUBULLU solution code:

Here is the working code:

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

int main() {
   int t,i,j;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d",&i,&j);
      
      /*Checking who starts the game*/
      
      if(j)
         printf("Pagfloyd wins.\n");
      else
         printf("Airborne wins.\n");
   }
   return 0;
}

Spoj BEENUMS solution

Spoj BEENUMS solution. Spoj Beehive Numbers solution.

Category: AdHoc, Pattern

If you just take a pen and paper and start drawing the beehive (or if you just see the given cases along with the problem), you will get to know that the numbers we are interested in are of the form 6*N +1 .
On further analysis, you will find that the exact form of such numbers is :

beenums(n) = 3n(n+1) +1 , where n>=0.

What we do, we first check if the given number is of the form 6N+1, if yes then we we run a loop for i(from 0 to N/6 both inclusive).
If any i, satisfies the given above formula, in that case we print “Y”,
else we print N.

Algorithm:

  1. Check if number is of the form 6*N+1.
    1. if yes, then run loop for i from 0 to number/6, and test if number is equal to the value of the above formula.
      If yes print ‘Y’ and break.
    2. if we reach an i > number/6, then we print ‘N’
  2. else print ‘N’.
  3. Repeat till input is -1.

Spoj BEENUMS solution code:

Here is the working code:

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

int main() {
   int n;
   scanf("%d",&n);
   while(n!=-1)
   {
      /*if number is of the form
      6*N+1 */
      if((n-1)%6==0)
      {
         int i;
         /*Checking for formula*/
         for(i=0; i<=n/6; ++i)
            if(((3*i*(i+1))+1) == n)
            {
               printf("Y\n");
               break;
            }
         if(i == n/6 +1)	
            printf("N\n");
      }
      /*Not of form 6*N+1*/
      else
         printf("N\n");
      scanf("%d",&n);	
   }
   return 0;
}

Spoj STAMPS solution

Spoj STAMPS solution. Spoj Stamps solution.

Category : AdHoc, Sorting

Here we are given a value which we have to attain, and an array of small number of stamps that different people can lend us.

Algorithm:

  1. Sort the array of stamps.
  2. Initialise Sum=0,
  3. start adding arr[i] to sum , starting from end of the array.
  4. Repeat point 3 till, either all values are added, or sum>=required value.
    If you break when we reach the required sum, then keep track of the index at which we break.
  5. Check if sum>=val, if yes print N-index-1
    else print “impossible”.

Spoj STAMPS solution code:

Here is the working code:

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

int main() {
   int t,n,val,caseCount=0;
   scanf("%d",&t);
   while(t--)
   {
      caseCount++; //to take care of case numbers
      scanf("%d%d",&val,&n);	
      int arr[n];
      for(int i=0 ; i<n ; ++i)
         scanf("%d",&arr[i]);
      
      /*STL sort function*/
      sort(arr,arr+n);
      
      /*Starting from end we start adding 
      arr[i] to sum, till either all values
      are added or we have gathered what 
      we required*/
      
      int i=n-1,sum=0;
      for(; i>=0 ; --i)
      {
         /*we break if sum is greater 
         than required value*/
         if(sum>=val)
            break;
         sum+=arr[i];
      }	
      
      /*Using given output format*/
      if(sum>=val)
         printf("Scenario #%d:\n%d\n",caseCount,n-1-i);
      else	
         printf("Scenario #%d:\nimpossible\n",caseCount);
   }
   return 0;
}

Spoj ACODE solution

Spoj ACODE solution. Spoj Alphacode solution.

Category: Dynamic Programming

Solution goes like this:

  1. Initialize an Array of Size N with 0 and element 0 as 1
  2. Loop through all the elements
  3. If it is a valid single digit number, Copy the previous element’s value to the current element (DP[i] = DP[i-1])
  4. If it is a valid two digit number, Add the previous to previous element’s value to the current element (DP[i] += DP[i-2])

We need to initialize array of size N+1, say dp[ ] with dp[0] = 1
Where ith element of array (dp[i] ) will represent the number of possible decoding using first i elements of input string.
So answer will dp[n].

Explanation:

DP[i] = DP[i-1] :
if ith character in the string makes a valid number(assuming 1-indexing for input string).
This is because we can append the character corresponding ith digit to the right of all possible codes , so we will get only as many number of codes as using i-1 elements of string.
Then we check for the two digit number, that can be made using ith , if this is a valid number ( is in range[1,26] ) then we can append character for this number to the right of all codes possible using first (i-2) elements of string, since we already used (i-1)th and ith  element to make this two digit  number.

for example : if input string is 25114.
25 can make 2 codes 2+5 and 25.
so appending next element  1, 251 can make 2 codes: (2+5)+1, (25)+1 .
and 51 is not a valid number.
The next 1 can be appended to (2+5+1)+1 and (25+1)+1,  making 2 codes only, but now 11  is also valid so 11 can be appended to the codes possible using 25 : (2+5)+11 , (25)+11 so these two ways are added using dp[i]+=dp[i-2].

Spoj ACODE solution code:

Here is the working code:

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

char str[5002];

int main() {
   scanf("%s",str);
   while(str[0]!='0')
   {
      int len=strlen(str);
      long long dp[len+1]={0};
      /*base case*/
      dp[0]=1;
      int i=1; //i for index
      while(i<len)
      {
         /*num is used to check if the 
         number formed using 2 digits is 
         valid character*/
         int num=(str[i-1]-'0')*10;
         num+=str[i]-'0';
         
         /*checking for valid 1 digit number*/
         if(str[i]-'0')
         {
            dp[i]=dp[i-1];
         }	
         /*checking for two digit number*/
         if(num>9 && num<=26)	
         {
            dp[i]+=dp[i-2<0?0:i-2];
         }
         
         i++;	
      }
      printf("%lld\n",dp[len-1]);
      scanf("%s",str);
   }
   return 0;
}

Spoj PAIRSUM solution

Spoj PAIRSUM solution.Spoj Sum of Pairwise Products solution.

Category: Dynamic Programming

In this question we need to print the value of

auau + au+1au+1 + au+1au + au+2au+2 + au+2au+1 + au+2au + … + avav + avav-1 + … + avau

What we do is :

  1. we use sum[i] to store sum of values of a0…ai.
  2. we use sumProd[i] to store (a0+a1 ..+…ai)*ai
  3. we store the cumulative sum of these products found in above steps.
    cumSumProd[i]= sumProd[0]+sumProd[1]+…+sumProd[i]

Now for non-zero value of ‘u’ the required answer can be calculated as

ans(u, v) = cumSumProd[v] — cumSumProd[u — 1] — (sum[u — 1]) * (sum[v] — sum[u — 1]).

For zero value of ‘u’, we simply print cumSumProd[v].

Spoj PAIRSUM solution code:

Here is the working code:

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

int main() {
   int n,m,u,v;
   scanf("%d",&n);
   LL arr[n],sum[n]={0},sumProd[n]={0};
   LL cumSumProd[n]={0};
   
   /*Base cases,
   so done different from loop*/
   scanf("%lld",&arr[0]);
   sum[0]=arr[0];
   sumProd[0]=arr[0]*arr[0];
   cumSumProd[0]=sumProd[0];
   
   /*Bottom-up DP*/
   for(int i=1; i<n ;++i )
   {
      scanf("%lld",&arr[i]);
      sum[i]=arr[i] + sum[i-1];
      sumProd[i]=sum[i]*arr[i];
      cumSumProd[i]=cumSumProd[i-1]+sumProd[i];
   }
   
   LL ans=0;
   scanf("%d",&m);
   while(m--)
   {
      scanf("%d%d",&u,&v);
      
      /*if u is non-zero*/
      if(u)
      {
         ans=cumSumProd[v]-cumSumProd[u-1]-(sum[v]-sum[u-1])*sum[u-1];
         printf("%lld\n",ans);
      }	
      else
         printf("%lld\n",cumSumProd[v]);
   }
   return 0;
}

Spoj DCEPC501 solution

Spoj DCEPC501 solution. Spoj Save Thy Toys solution.

Category: Dynamic Programming

Here,
The array val[] stores the value of each of the items.
The array dp[] stores the maximum money that Leonard can get by choosing toys from n1 to i.

Now, we use bottom-up DP and move through the array A from right to left i.e. from n1 to 0.
Let us see what decisions you can take while choosing a toy at the ‘i’th position.

  1. He chooses one toy in the sequence. So, in this case, the maximum money that Leonard can get is:
    value of the i item + max money he can get from the items from positions n1 to i+2
    = val[i]+dp[i+2]

    1. We choose i+2 here because i+1 item will be selected by Sheldon.
      Hence, the previous item selected by Leonard was the i+2 item.
  2. He chooses two toys in the sequence. So, in this case, the maximum money that Leonard can get is:
    value of the i item + value of i+1 item + max money he can get from the items from positions n1 to i+4
    = val[i]+val[i+1]+dp[i+4]

    1. We use i+4 here because i+2,i+3 are chosen by Sheldon.
      Hence, the previous item selected by Leonard was i+4,i+5. (take the first one in the two items).

3. Similarly, extend the logic to selection of three items.

Now, the maximum of the three cases will be dp[i].

Note: We declare and initialise(with 0,using memset() ) an array val[],d[] of size 7 more than what is required. This is done so as to  take care of case when 3 toys are chosen for i=n-1.

Spoj DCEPC501 solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long int

/*We use Bottom-Up DP.*/

int main() {
   int t,n,i,j;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      LL val[n+8],dp[n+8];
      
      for(i=0;i<n;++i)
         scanf("%lld",&val[i]);
      
      /*Initialising all dp[] array with 0
      Also, we make extra 7 places 0 in the
      */	
      
      memset(dp,0,sizeof(dp));
      memset(val+n,0,sizeof(LL)*7);
      
      for(i=n-1;i>=0;--i)	
      {
         /*Case when we take only 1 toy*/
         dp[i]=val[i]+dp[i+2];
         
         /*To check profit if we take 2 toys*/
         if(i+1<n)
            dp[i]=max(dp[i],val[i]+val[i+1]+dp[i+4]);
         
         /*To check for profit if we take 3 toys*/	
         if(i+2<n)	
            dp[i]=max(dp[i],val[i]+val[i+1]+val[i+2]+dp[i+6]);
      }
      
      printf("%lld\n",dp[0]);
   }
   return 0;
}

Spoj POCRI solution

Spoj POCRI solution. Spoj Power Crisis solution.

Category : Dynamic Programming,AdHoc

This problem is direct implementation of Josephus Problem.
The standard Dynamic Programming solution code for the Josephus Problem leads to Time Limited Exceeded error.
So, we modify the code by removing the addition from the loop and adding a statement after the loop (in the standard solution).

Also, since 1 is eliminated first and N is always >1 (N>=13 always), we need to modify the base case for ans(1,m)=0

We apply the Josephus problem solution repeatedly for different m (starting from 1), till we get the ans as 13.
We increment the value of before each iteration.

Spoj POCRI solution code:

Here is the working code:

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

int main() {
   int n,m,ans,i;
   scanf("%d",&n);
   while(n)
   {
      
      m=0;
      
   /*We repeat the Standard DP 
   Josephus Solution Till we get
   the answer 13.
   When we get 13 as answer, we 
   print that value of m.
   Here we consider the base case as
   0, because 1 is eliminated first.
   */
      do
      {
         m++;
         ans=0;
         for(i=2;i<=n-1;++i)
            ans=(ans+m)%i;
         ans+=2;	
      }while(ans!=13);
      
      printf("%d\n",m);
      scanf("%d",&n);	
   }
   return 0;
}