HackerRank Combinatorics – Lexicographic paths

Challenge: Lexicographic paths

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734651

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/lexicographic-steps/problem

Cerinta

Krishnakant is standing at $(0,0)$ in the [Cartesian plane](http://en.wikipedia.org/wiki/Cartesian_coordinate_system). He wants to go to the point $(x,y)$ in the same plane using only horizontal and vertical moves of $1$ unit. There are many ways of doing this, and he is writing down all such ways. Each way comprises of few $H$ moves and few $V$ moves. i.e. moves in horizontal and vertical direction respectively. For example, if Krishnakant wants to go to point $(2,2)$ from point $(0,0)$, $HVHV$ is one of the possible ways.   

Given the value of $K$, he wants to know lexicographically $K^{th}$ smallest way of going to $(x,y)$ from $(0,0)$.   

**Input Format**  
The first line contains an integer $T$ , i.e., number of test cases.  
Next $T$ lines will contain integers $x$,$y$ and $K$.  

**Output Format**  
For each test case, print lexicographically $K^{th}$ smallest path.  

**Constraints**  
$1 \le T \le 100000$  
$1 \le x \le 10$  
$1 \le y \le 10$  
$0 \le K < \text{number of paths}$ 

**Sample Input**  

    2
	2 2 2
	2 2 3


**Sample Output**  

    HVVH
	VHHV


**Explanation**

All the paths of going to $(2,2)$ from $(0,0)$ in lexicographically increasing order:<br><br>

$0.  HHVV$<br>
$1.  HVHV$<br>
$2.  HVVH$<br>
$3.  VHHV$<br>
$4.  VHVH$<br>
$5.  VVHH$<br>

Cod sursa

//lexicographic-steps.cpp
//Lexicographic paths
//Weekly Challenges - Week 9
//Author: derekhh

#include<cstdio>
using namespace std;

int n, m;
int c[21][21];

void init()
{
	for (int i = 1; i <= 20; i++)
	{
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; j++)
			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}
}

int main()
{
	init();
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int k;
		scanf("%d%d%d", &n, &m, &k);
		int cx = 0, cy = 0;
		while (cx != n || cy != m)
		{
			int nH = n - cx, nV = m - cy;
			if (nH == 0)
			{
				printf("V");
				cy++;
			}
			else if (nV == 0)
			{
				printf("H");
				cx++;
			}
			else
			{
				int temp = c[nH + nV - 1][nH - 1];
				if (k >= temp && temp > 0)
				{
					printf("V");
					k -= temp;
					cy++;
				}
				else
				{
					printf("H");
					cx++;
				}
			}
		}
		printf("\n");
	}
	return 0;
}