techgig0's blog

By techgig0, 4 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -30
  • Vote: I do not like it

By techgig0, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By techgig0, 5 years ago, In English

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

LeaderBoard

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By techgig0, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it

By techgig0, 5 years ago, In English

Hey Codeforces! I recently viewed this post on facebook and found this to be pretty interesting idea. The idea is to create small online groups to help and push each others. This is benefitial especially for people having rating upto 1800(in my opinion). If anyone is interested can visit this link for more details.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it