You are not logged in. Please login at www.codechef.com to post your questions!

×

RKABOL02 - Editorial

PROBLEM LINK:

Practice
Contest

Author: ravikiran0606
Editorialist: ravikiran0606

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

RECURSION, BACK-TRACKING

PROBLEM:

Given an integer N and a string S of length N. We need to generate a number with N+1 digits such that the following contraints holds true,

1) If the (i)'th character of the string is I, then (i)'th digit in the number > (i+1)'th digit in that number.
2) If the (i)'th character of the string is D, then (i)'th digit in the number < (i+1)'th digit in that number..
3) All the digits of the number are distinct and non-zero.

EXPLANATION:

In this question, its very easy to find one of the cases for -1 that for all N>=9, the answer is always -1 since there are only 9 non-zero distinct digits from 1 to 9. Thus we can find solution only if N<=8. If the length of the string is N, we need to generate a number with N+1 digits with the given contraint. We can solve this using recursion and backtracking by trying all possible combinations of digits of length N+1 with the given constraint and print the lexicographically smallest one. If no solution exists we can print -1. The expected complexity is O(9n).

AUTHOR'S SOLUTION:

Author's solution can be found here

asked 13 Mar, 19:36

ravikiran0606's gravatar image

4★ravikiran0606
41
accept rate: 0%

edited 15 Mar, 13:37

admin's gravatar image

0★admin ♦♦
19.3k348495534

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,005
×1,484
×19
×19
×19

question asked: 13 Mar, 19:36

question was seen: 91 times

last updated: 15 Mar, 13:37