TOPCODER SRM 800 DIV2 MEDIUM (750 points)

Problem description here PoisonedSwamp

You should definitely know that this is a graph search problem. You can apply either DFS or BFS. However, the main challenge is to define the state meaning the vertex/node of this graph search problem. One key observation is that, you have to take poison count into consideration while you are visiting vertices/states.

So basically 3 parameters define a state: row number(x), column number(y), poison count acquired so far after stepping into cell(x,y) since the traversal started from cell(0,0). Another thing to note that, we don’t need to take care of poison count for more than 10 because the traveler is gonna die if he acquires >= 10 poisons.

I have implemented this using queue, in fact priority queue (it is not necessary as total state space is not so high). It is possible to solve this problem by a recursive dfs too.

My code during contest: https://community.topcoder.com/stat?c=problem_solution&rm=335435&rd=18497&pm=16768&cr=23058599

SRM 687 (div2 medium)

Problem description Quacking.

Problem summary:
You are given a string S that consists of letter q, u, a, c or k. Now you have to split S into several non-empty words such that each word is a sub-sequence of S and a single character at a particular index of S will be part of exactly one word. Again, each word should have pattern: (quack)^x; where string “quack” is repeated x (≥1) times.
You need to find the minimum number of words such that they follow the above constraints. Return -1 if it’s impossible to follow the constraints for any number of words.
For example if S = “quqacukqauackck”, we need minimum two words. Bold letters form “quackquack” and other letters form “quack”.

Solution:
This is a greedy problem. The idea is to iterate the string S for each word and maximize x (described above). Remember that x should be at least 1 for each word. To create repetition of “quack”, modulo arithmetic can be used or check when searching for “quack” have to restart. Return the number of words (number of iterations through string S) when all the letters of the input string S have been taken into account.

Code is given below:

#pragma comment(linker,"/STACK:16777216")
#pragma  warning ( disable: 4786)
#include <bits/stdc++.h>
using namespace std;
#define forl(i,a,b) for ( i = a; i < b; i++)
#define ms(a,b) memset((a),(b),sizeof(a))

#define MAX 2501
bool vis[MAX];

class Quacking {
    public:
    int quack(string s) {
        ms(vis,false);
        int n = s.size();
        int i;
        string in = "quack";
        int ans=0;
        while(true){
            int index = 0;
            bool all=true;
            int found=0;
            forl(i,0,n){
                if(vis[i]==false){ 
                    //character at index i has not been used in earlier iteration
                    if(s[i] == in[index]){
                        index++;
                        vis[i] = true; //now it is taken
                        if(index==5){
                            //restart searching for "quack"
                            index=0;
                            found++;
                        }   
                    }
                    all=false;
                }
            }
            //full repetition of "quack" is not found.
            //Example of this can be: quackq, quackqu, quac
            if(index != 0){
                return -1;
            }
            //all letters are taken
            if(all)
                break;

            //there are still some letters but not found any single instance of "quack"    
            if(found==0)
                return -1; 
                  
            ans++;
        }
        
        return ans;
    }
};

Code during contest

SRM 664 (div2 medium)

Problem description here.

Problem summary
You are given three piles of stones each containing A, B and C (1 ≤ A,B,C ≤ 500) stones respectively. In a single operation, you can choose any two piles that have unequal number of stones (X,Y with X < Y). Then you have to change Y by Y-X and change X by 2*X. After zero or more operations, is it possible to have equal number of stones in each pile?

Topcoder SRM 620 div2 500

You are given four integers a,b,c,d where 1 ≤ a,b,c,d ≤ 1000. Consider (a,b) as a pair. By using zero or more steps is it possible to get (c,d)?

From (x,y) you can either jump to (x+y,y) or (x,x+y) which is a single step.

Idea 1:

By applying BFS with queue you can solve this. Each state in queue is a pair of integers. Initial state is (a,b) that is given in the input. If anytime you can reach (c,d) which is given in the input, return “Able to generate”. Otherwise “Not able to generate”. rumman_sust has solved this problem in this way here.

Idea 2:

If we start from (c,d) and try to go back to (a,b) size of code becomes smaller with some intuition.

In pair (x,y) both x,y are positive according to input. From (x,y) if you jump to (x+y,y) then x+y will never be equal to y. Again From (x,y) if you jump to (x,x+y) then x+y will never be equal to x. So you can handle the trivial cases in the following way:

 if(a == c && b ==d)
return "Able to generate";
if(c == d)
return "Not able to generate";

from pair (c,d) if we go downward one step and get (x,y)
(x,y) = (c-d, d) if c>d
(x,y) = (c,d-c) if d>c
from (x,y) we will start the above process again. If anytime we reach (a,b) that is given in the input we are done. Otherwise Impossible.
Final code:

class PairGameEasy {
    public:
    string able(int a, int b, int c, int d) 
    {
          if(a == c && b ==d)
                  return "Able to generate";
         if(c == d)
            return "Not able to generate";
        while(c > 0 && d > 0)
        {
              if(a == c && b ==d)
                  return "Able to generate";
            if(c > d)
              c -= d;
            else
              d -= c;
        }
        return "Not able to generate";
    }

Idea 3:

This problem can also be solved by dp by keeping a 2D array.

naseef_cuet has solved this problem in this way which is quite easy to understand.

int A[1011][1011];
 
 
class PairGameEasy {
public:
  string able(int a, int b, int c, int d) {
 
      for(int i=0;i<=1000;i++)
        {
            for(int j=0;j<=1000;j++)
            {
                A[i][j]=0;
            }
        }
 
        A[a][b]=1;
 
        for(int i=0;i<=1000;i++)
        {
            for(int j=0;j<=1000;j++)
            {
                if(A[i][j]==1)
                {
                    if(i+j<=1000)
                    {
                        A[i+j][j]=1;
                        A[i][i+j]=1;
                    }
                }
 
            }
        }
 
        if(A[c][d]==1)
            return "Able to generate";
        else return "Not able to generate";
 
  }
};

My long boring code during contest is here.