Connection Status:
Competition Arena > Decipherability

Decipherability

SRM 649 · 2015-01-29 · by tozangezan

SRM 649 · 2015-01-29 · by tozangezan · String Manipulation
Class Name: Decipherability
Return Type: String
Method Name: check
Arg Types: (string, int)
Problem Statement

Problem Statement

You have a string s that contains at least K characters. Cat Snuke will remove exactly K characters from the string. Afterwards, Snuke will show you the new string and you have to guess the original indices of all removed characters. You win the game if you guess all of them correctly.

For example, suppose that s="snuke" and K=2. Snuke removed two characters and showed you the string "nue". In this situation you can easily deduce that Snuke must have removed the characters s[0] and s[3]. You announce that the indices of removed characters are 0 and 3, and you win the game.

You are given the String s and the int K. Return "Certain" (quotes for clarity) if you can always be sure to win the game, regardless of which characters Snuke removes. Otherwise, return "Uncertain". Note that the return value is case-sensitive.

Constraints

  • K will be between 1 and 50, inclusive.
  • The length of s will be between K and 50, inclusive.
  • Every character in s will be a lowercase letter ('a'-'z').
Examples
0)
"snuke"
2
Returns: "Certain"

This is the example from the problem statement. As all characters are unique, you can always determine the indices of the erased ones.

1)
"aba"
1
Returns: "Certain"

Snuke will show you one of the strings "ba", "aa", and "ab". In the first case you can be sure that he erased the character at index 0. The second and the third string correspond to indices 1 and 2, respectively.

2)
"aba"
2
Returns: "Uncertain"

If Snuke shows you the string "a", there are two possibilities: either he erased the characters at indices 0 and 1, or the characters at indices 1 and 2.

3)
"abcdabcd"
3
Returns: "Certain"
4)
"koukyoukoukokukikou"
2
Returns: "Uncertain"

Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Decipherability with a public method string check(string s, int K) · 118 test cases · 2 s / 256 MB per case

Submitting as anonymous