### techgig0's blog

By techgig0, 10 days 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, 9 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, 10 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, 11 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, 12 months ago, , 