.

someone famous proved that there are unprovable facts

great book that teaches you how to solve problems similar in nature to the aforementioned problem: https://www.softouch.on.ca/kb/data/Art%20and%20Craft%20of%20Problem%20Solving%203E%20(The).pdf

got it from: https://mirror.codeforces.com/blog/entry/101561?#comment-901775

that wont work for every problem you come across

https://mirror.codeforces.com/contest/1634/problem/B

https://mirror.codeforces.com/contest/1864/problem/C

https://mirror.codeforces.com/contest/1909/problem/B

https://mirror.codeforces.com/contest/1682/problem/C

https://mirror.codeforces.com/blog/entry/122791#comment-1089143

lets say x=16 y=3 k=1, clearly we are left with x=17

lets say x=16 y=3 k=3, 16->17->2->1, and x became <y

the idea is: after every deletion x decreases from what it was originally even if it increased a little before getting to a multiple of y. and if x always decreases then after some time it must go to 1, after that it loops from 1 to y.

prove?

We need to count the number of strings which have the pattern as a substring. So the strings would have the given form: s1+PATTERN+s2 (+ concatenation). Now we just need to count the different ways we can make s1 and s2 using the letters A-Z, depending on their size. Now lets see how their size depends on Q(i).

let:

the indexes begin from 1

m1=|s1| m2=|s2| (|string|=size of string)

m = |PATTERN| n = |the whole string|

then for each Q(i)

=> m1 = (i-1) +1 (from index 1 to the first index of the pattern)

=> m2 = n-m1-m

Now lets see how many unique strings we can make with size k and 26 unique characters. For the first position we have 26 options, for the second 26 and for the i position 26 options. Then we multiple like such: 26*26*26... }k times = 26^k (you can think of it like picking a lock, the number of different combinations can be computed similarly)

Now we just compute for each Q(i): (26^m1)*(26^m2) and add up the result.

And that's our answer.

Maybe the number of people that solved the problem during the round would help determine the difficulty. The first thing that comes to mind is to use the cf api, I actually made a script a while back for this but there may be a better way to accomplish this.

I would go for something like this: Lets define Q(i) to be a string with the pattern as substring at the i-th position. Now all you have to do is to count the sum of variations possible for the i-th Q(i) if we only replace the characters not belonging to the pattern. It's more like a math problem if you ask me (combinatorics). Sorry if I had made a mistake or you didn't understand my suggestion.

Can you recommend a website to practice math related problems?

Congratulations! I am so happy for you.

I don't know why my solution is not getting accepted.

150167854

Any ideas?

same

I don't care either