Topcoder SRM 800 div2 medium

Topcoder achieved a milestone by arranging 800 Single Round Algorithm Matches (SRM) to the coder all over the world. Topcoder arranged a virtual party before this 800th match. Among this 800 matches, I participated in over 150 matches. (See my Topcoder profile). Thank you Topcoder for helping me improve my coding skill.

Let’s get back to the problem. This problem was worth 400 points. Please take a look at the problem statement as I am not gonna repeat the problem statement.

Look at the above picture to visualize this problem. As like this picture, our goal is to get letter ‘c’ (cherry) in all reels.

Key insights from this problem:

There are maximum 5 reels.

Each reel has maximum 10 fruits (or letters) in a circular fashion.

From these two constraints, we know that there could be maximum 10*10*10*10*10 = 10^5 different display strings you will see based on positions of the fruits although two different configurations might end up with same display string as there could be duplicate letters in a reel.

My approach for this problem is to play the slot machine rounds and keeping track of configurations in a map or dictionary. If a configuration repeats before getting a jackpot, that basically means the game entered into a cycle and we can return “impossible” in this case. Each configuration corresponds to a set of position indices of current display letters from all reels. Now the question is – how to store these configurations in map? My approach is to use unique letters to denote each index across all reels. For example ‘a’ is for index 0, ‘b’ is for index 1 and so on. The good thing is we will never run out of letters to represent indices as there would be maximum 10 letters (meaning 10 positions) in each reel. Remember that, this configuration letters are different from the letters in each reel.

After each round of play, we have to adjust the positions for next round. See the code below for a better understanding of my approach.

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

class SlotMachineHacking {
public:
int win(vector reels, vector steps) {
map uniq_configs;
string jackpot = ""; //jackpot string: all 'c'
int i,j,k;
for(i = 0;i<reels.size();i++)
{
jackpot = jackpot + 'c';
}
int cnt = 0;
int n = reels.size();
int pos[n]; //indices of current display letters for all reel strings
for(i=0;i<n;i++)
{
pos[i] = 0;
}
auto newpos = [&pos, &reels, &steps](int n){
int i;
for(i=0;i<n;i++){
pos[i] = (pos[i]+ steps[i])%reels[i].size();
}
};
while (true){
string curr_display = "";
newpos(n);
for(i=0;i<n;i++)
{
curr_display += reels[i][pos[i]];
}
if(curr_display == jackpot)  //current display matches jackpot
return cnt;
string curr_config= "";
for(i = 0;i<n;i++){
curr_config = curr_config + char(('a'+pos[i]));
}
if(uniq_configs[curr_config])
return -1;
uniq_configs[curr_config] = 1;
cnt += 1;
}
return -1;
}
};

In the above code you will see a c++ closure defined.

Another approach is to run the simulation for 10^5 times without keeping a map

more specifically,

number of rounds, R = Length(reels[0])*Length(reels[1])*…..Length(reels[n-1]);
n is total number of reels.

So if you don’t hit jackpot during this many rounds, you will never hit jackpot. Because if you do not enter into cycle during this many rounds, you will cycle in the very next round (i.e R+1‘th round)

References

1. image source

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?