### techgig0's blog

By techgig0, 6 months ago, The challenge consists of 3 problems with score distribution of 20-50-100

#### 20 score problem:

You have a square matrix $n$, initially empty, and you have to perform $k$ operations on it. For each operation you are given $1 \leq r \leq n$ and $1 \leq c \leq n$ and you have to fill all cells in row $r$ and all cells in column $c$. For each $k$ queries you have to output empty cells remaining.

Input:
$n$ $k$
$r_1$ $c_1$
$.$
$.$
$.$
$r_k$ $c_k$

Example:
3 2
1 2
1 1

#### 50 score problem:

You are given $n$ coins and you have to use these to make a number as large as possible. You can use digits $[1-9]$ which has some cost given to you.

Input:
$n$
$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ $x_8$ $x_9$

Example:
100
4 6 2 7 9 15 76 14 3

#### 100 score problem:

You are given a range $[l, r]$ in which you have to output $k_{th}$ lucky number. A lucky number is defined as a number whose binary representation contains $101$.

Input:
$l$ $r$ $k$

Example:
10000 9487474746 507 By techgig0, 15 months ago, Can anyone help with this problem: https://www.hackerrank.com/challenges/fighting-pits/problem. I have searched over internet but couldn't find any content related to it.

I have also tried understanding editorial but it has gone over my head. Any resource, approach(with proof) or problems related to it will be appreciated. By techgig0, 15 months ago, Since the problems of the contest were pretty good, I think it needs a dedicated blog for post contest discussions. Please share the problems in comments as I haven't read all the problems(or provide screenshots).

One of the most interesting problem was: Given an array of $A$ of size $n$, you are allowed to reverse a subsequence atmost one time. You have to output maximum non-decreasing subsequence in the final array.

Constraints : $1 \leq n, A[i] \leq 50$

 Sample Input Sample Output 5 45 28 45 3 48 5 By techgig0, 16 months ago, A special palindrome is a palindrome of size $n$ which contains at most $k$ distinct characters such that any prefix of size between $2$ and $n-1$ is not a palindrome.

You need to count the number of special palindromes.

For example, abba is a special palindrome with n = 4 and k = 2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.

If n = 3 and k = 3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So the answer will be 6.

Input format

A single line comprising two integers and

Output format

Print the answer to the modulo $10^9+9$.

Input Constraints

$1 \leq n \leq 10^5$

$1 \leq k \leq 10^5$

 Sample Input Sample Output 3 2 2 4 3 6

Source

Please help with this problem as I can't find any good tutorial over internet and the code/solution provided is different than from what I thought. I don't even understand how states are defined in this. By techgig0, 18 months ago, 