Difficulty in understanding problem Game with String

general
,
1

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?

1 Like
2

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.)

2 Likes
3

Thanx mate!! Sily me :slight_smile:

1 Like
4

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!).

1 Like
5

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

6

yes! same here.

1 Like