Topcoder TCO’21 Round 2B – Combinatorics problem

Problem link:  Alternate Odd Even

Problem summary:

Find the K’th number from a positive increasing sequence of numbers such that their digits in a number alternate being odd and even.

Key facts:

1. Any digit from 1-9 can sit at the Most Significant Bit (MSB) position. For all other position, the number of digits that can sit there is always 5. Those 5 digits come from two disjoint lists. List1 = [0, 2, 4, 6, 8] or List2 = [1, 3, 5, 7, 9]
2. From fact 1 we can deduce that, the number of unique numbers that can be generated having d digits is: 9*5^(d-1)

My Approach:

First, find the number of digits that the K’th number will have:

It is smallest d such that

Let’s define N based on the d we just defined:

It is now evident that, the N’th smallest number having d digits is the answer of our problem. Now the question is: how do we find the N’th smallest suitable number having d digits? We can start iteratively starting from MSB (position d-1, LSB position is 0). In every bit positions we try eligible digits in increasing order and see how many numbers we can make with i’th position containing a digit say 4. The purpose of this calculation is to identify a digit in every i’th position such that our N’th smallest number will definitely have that number.

My code during the contest and it passed system test.

Topcoder Data Science Marathon Match 126

You can check the details of this marathon match in topcoder site: https://www.topcoder.com/challenges/82eb883d-85e9-442f-b0eb-91631d3d2a8f?tab=details

Problem Summary

You are given a 2D grid containing few holes, number blocks and empty cells. Your task is to move numbered cells to any hole using Slide or Move operations. Along the way, your goal is to maximize game score based on certain defined rules.

My Approach

My approach was to use simulated annealing (SA). In every iteration of the SA, I swapped the position of two numbered cells from an ordered list of numbered cells. This ordered list represents the order in which I want to move/slide blocks to holes one by one and one at a time.

Now my score boosted up after few optimization on baseline SA.

1. When you move a block to hole, move it using shortest number of operations.
2. Instead of always choosing two random number blocks I fixed one index, which is the last number block index in previous iteration where the process stopped due to Z <= 1 (score multiplier, see description) or no way to move that block
3. Instead of having a random initial order of blocks, I used a greedy approach to sort the block based on shortest moves first, then based on block value.

A demo of my solution for one of the test cases is below.

My code and along with other resources (including other competitor’s approaches) of this match can be found in my Topcoder repository

Here is another blog article on this match.

Some contestants used Beam Search in this match. Here is the wiki book link for that.

How to fix: Topcoder java applet won’t open in Ubuntu

I have been using Topcoder java applet (ContestAppletProd.jnlp) for SRM competitions for over a year in Ubuntu 18.04. Suddenly, one day it stopped working showing me the following error.

To solve this issue, open java security configuration file using following command:

sudo vim /etc/java-*-openjdk/security/java.security

then search for a line similar to the following and comment it out and save the file (:wq command in vim).

jdk.jar.disabledAlgorithms=MD2, MD5, RSA keySize < 1024

If you do that, your jnlp file will open fine with this dialog and you have to prompt that you trust this jnlp file and trust topcoder.com (haha)

Reference:

1. https://unix.stackexchange.com/questions/143805/running-unsigned-javaws-code

SRM 802 DIV2 Hard by DP

Problem description here DisjointDiceValues

We will solve it by considering Alice’s win probability. Let’s denote it by P(Alice).

P(Alice) = (number of events where Alice wins) / (total events)
total events = 6^(A+B)

We will use DP to calculate the number of events where Alice wins.

Consider an array of (A+B) elements where first A elements are the dice values drawn from Alice and last B elements are the dice values from Bob. We will fill out these elements recursively and at the same time we will have two bitmasks to represent unique dice values found by Alice and Bob respectively.

So the dp state will look like this:

dp[index][maskAlice][maskBob]

This dp state answers the question of “How many events are possible where Alice wins given that index number of elements have already been filled up and Alice has picked up certain unique values represented by maskAlice and Bob has picked up certain unique values represented by maskBob?”

Base Case: index = A+B, and (maskAlice & maskBob) > 0. Meaning we filled up all A+B elements and there is a dice value common in Alice and Bob’s elements.

My code after contest: (it passed all sample tests)

#include<bits/stdc++.h>
using namespace std;
#define forl(i,a,b) for ( i = a; i < b; i++)

long long int dp[20][130][130];
int n,m;

bool iscommon(int m1, int m2){
    int i;
    forl(i,1,7){
        if((m1&(1<<i)) and (m2 &(1<<i)))
            return true;
    }
    return false;
}

long long int doit(int ind, int mask1, int mask2){
    if(ind == n+m){
        return iscommon(mask1, mask2);
    }
    if(dp[ind][mask1][mask2] != -1)
        return dp[ind][mask1][mask2];
    long long int ans = 0;
    //fill Alice's elements
    int i,j,k;
    if(ind <n){
        forl(i,1,7){
            ans += doit(ind+1, mask1|(1<<i), mask2);
        }
    }
    else{//fill Bob's elements
        forl(i,1,7){
            ans += doit(ind+1, mask1, mask2|(1<<i));
        }
    }
    
    dp[ind][mask1][mask2] = ans;
    return ans;
}
class DisjointDiceValues {
    public:
    double getProbability(int A, int B) {
        long long int total = pow(6, A+B);
        n = A;
        m = B;
        int i,j,k,a,b;
        forl(i,0,20){
            forl(k,0,130){
                forl(a,0,130){
                    dp[i][k][a] = -1;
                }
            }
        }

        long long int r = doit(0,0,0);
        double ans = r;
        ans /= total;
        return ans;
    }
};

Concatenate files in Ubuntu

Case Study
After every Data science marathon match in Topcoder, the organizer provides all submissions of codes in a zip file. After extracting this file, you will see lot of individual submissions as zip file. So to see the solution of each submission, I had to unzip each submission and see the code as languages such as c++, python, csharp or c. This is time consuming. I wanted to combine all language specific submissions into a single file so that I don’t have to unzip back and forth to see code.

Solution

First I made a script to unzip all zip submissions into separate directories.

for file in *.zip
do
    directory="${file%.zip}"
    unzip "$file" -d "$directory"
done

The above code segment is stored as command.sh

The commands to execute this file:

chmod +x command.sh
./command.sh

These commands will unzip all zip files and put unzip contents in newly created directories.

Next we want to extract all c++ files in those sub-directories and concatenate all contents in a single file named allcpp.txt

The command for that is

find . -type f -name "*.cpp" -exec cat {} + >allcpp.txt

The same is for concatenating all python and csharp files:

find . -type f -name "*.py" -exec cat {} + >allpy.txt
find . -type f -name "*.cs" -exec cat {} + >allcs.txt

Reference:
https://stackoverflow.com/questions/2374772/unzip-all-files-in-a-directory/29248777
https://www.javatpoint.com/steps-to-write-and-execute-a-shell-script

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

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 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?

SRM 637 div2 medium (Greedy Approach)

Here goes the problem statement.

Problem summary
You are given a 2D grid which has exactly two rows and each row has m (say) columns which is up to 50. Each of the character in the grid cell is either ‘.’ or ‘#’. You have to find a path which will start from the first column and end at last column by following the ‘.’ characters only. Two adjacent cells must share an edge. The purpose is to choose a path that uses minimum number of ‘.’ characters.

Greedy solution

Position x represents the current position in the path

Let’s assume that current path position is x. The greedy approach is that path shouldn’t change it’s current row until it gets a ‘#’ character in its path. If the path is stuck at position y, then the opposite character in position p will never be a ‘#’ character. Otherwise there will be no path. But from problem statement, we know that there will be at least one valid path. It can be intuitively observed from the picture, total number of ‘.’ characters in the path from x to p(first from x to y directly and then from y to p) isn’t more than any numbers that counts the total number of ‘.’ characters in the path from x to p in any possible way.

Finding the Diameter of a tree (SRM 635 div2 hard)

In SRM 635, a problem (LonglongestPathTree) was set for division 2 hard which requires to find the diameter of a tree.

Finding Diameter of tree

To find the diameter of a tree, at first a dfs/bfs search is needed from any arbitrary node(for say ‘x’) to find a node(y) which is furthest from x with respect to cost. From node y, a second search is required to find the most expensive cost path in the tree.

Binary Search on answer (SRM 635 div2 medium)

Problem statement goes here

Problem sketch:

If we summarize the problem statement in one sentence: What is the largest value of t such that following inequality holds true.
t + t² ≤ d such that 1 ≤ d ≤ 10¹⁸

Solution Approach:

Brute force:

Brute Force approach can be of two types:

Type 1: We start from the smallest value of t i.e zero(0) and increase the value of t by 1 each time. The largest of of t that satisfies the inequality is the answer.

Type 2: We start from the largest value of t i.e d and decrease the value of t by 1 each time. As soon as the inequality holds true for a certain t, this t is the answer.

Unfortunately, these two approaches will time out because of large value of d.

Topcoder SRM 622 div2 500

Problem statement goes here

The main trick in this problem was to find a smallest integer(p) ≥ S, such that p is a power of 2(i.e 2ⁱ for i=0,1,2,…) . Only S is given

#define nearestPowerOfTwo(S) ((int)pow(2.0, (ceil)((log((double)S) / log(2.0)))))

My code during contest is given below:

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.