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

×

[closed] Difficulty in understanding problem Game with String

Can anyone help me understand this problem:

http://codeforces.com/problemset/problem/930/B

I mean can't vasya ask all letters(which will give probability 1) ?

I know i am wrong,Please if someone could clarify the question.

Thanks in advance!!

Edit:Sorry to reopen it.But i am now having difficulty in understanding the approach for the question,also cant understand the editorial.And also can someone explain how the answer for string: bbaabaabbb is 0.1?

asked 16 Mar '18, 21:59

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

closed 19 Mar '18, 09:13

The question has been closed for the following reason "The question is answered, right answer was accepted" by vivek_1998299 19 Mar '18, 09:13


What I could gather from the statement was-

  1. Initially there is a string s shown to Vasya
  2. After this, its hidden and left rotated $k$ times. (final configuration as given in question).
  3. Now the first letter of the new string is uncovered.
  4. Vasya can uncover one more letter. If using these 2 positions, she can uniquely determine $K$ , she will win, else lose.

Eg, if string is abcdef. Say its left shifted to become defabc.

Initially the new string, to Vasya is like $??????$ , then the first letter reveals to $d?????$. She can uncover any letter and uniquely determine $K$.

For string tictic , initially its $??????$ , then first letter revealed $t?????$. If she opens up second letter, string will be $ti?????$ and $K$ can be either 0 or 3, i.e. cannot be uniquely determined. (IDK if Q allows K=0, its here just for example.)

link

answered 17 Mar '18, 00:41

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12065
accept rate: 18%

edited 17 Mar '18, 00:41

1

Thanx mate!! Sily me :)

(17 Mar '18, 00:50) vivek_19982996★

Let me try. Firstly as vatya know the first letter of every string so, better we calculate the answer for a particular starting character. Let us take all possible string starting with character 'a' and now he can uniquely identify a particular string iff there exist atleast one position in this string where there is a charcter which is not present in any other string i.e. if we make an [length][26] (for 'a') array where [i][j] denotes how many strings starting with 'a' has 'jth' character in ith position and if we get '1' in any [i][j] then we can say that we can uniquely determine a string by opening the ith position. So, for every position we have to find the maximum number of strings that we can identify if we open that position! Now for this, for a particular position i we can iterate over all 26 characters and count how many of them are 1's (as we can uniquely identify those many strings by opening the ith position). And then we have the data how many string we can identify by opening the ith position, we can simply take max and report the answer.

Now, do this for all possible 26 starting characters(as he knows 1st character in advance so, he is allowed to change his strategy (which position to open) accordingly!).

link

answered 18 Mar '18, 13:34

pk301's gravatar image

3★pk301
62710
accept rate: 16%

Thanx mate !! Really need to work hard in probabilty.

(19 Mar '18, 08:27) vivek_19982996★
1

yes! same here.

(19 Mar '18, 16:46) pk3013★

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:

×640
×242

question asked: 16 Mar '18, 21:59

question was seen: 392 times

last updated: 19 Mar '18, 16:46