### 236A - Boy or Girl

It is a very simple problem, just count how many distinct chars in the input and write the correct answer.

### 236B - Easy Number Challenge

First of all we make a table of size a*b*c to store every number's d value. then just brute force though every tripe to calculate answer.

### 235A - LCM Challenge

It's a simple problem, but many competitors use some wrong guess and fail.

First of all we should check if n<=3 and then we should output 1,2,6. and if n is odd, the answer is obviously n(n-1)(n-2).

if n is even, of course we can use (n-1)(n-2)(n-3), so these three number wouldn't be very small compared to n. so just iterate every 3 number triple in [n-50,n] and update the answer.

### 235B - Let's Play Osu!

Let us take a deep look in how this score is calculated. for a *n* long 'O' block, they contribute *n*^{2} to answer.

Let us reformat this problem a bit and consider the following problem.

For each two 'O' pair which is no 'X' between them, they add 2 to score.

For each 'O',it add 1 to score.

We can see that these two problem are exact the same.

Proof:

for a *n* long 'O' block,there is *C*_{n}^{2} pair of 'O' in it and *n* 'O' in it.

2*C*_{n}^{2} + *n* = *n*^{2}.

So for each event(i,j) (which means s[i] and s[j] are 'O', and there's no 'X' between them).

If event(i,j) happen, it add 2 to the score.

So we only sum up the probability of all events and multiply them by 2.

Then our task become how to calculate the sum of all event(i,j).

We can see event(i,j) is simpliy .

Then we denote dp(j) as sum of all event(i,j) and i<j.

so dp(0)=0 and dp(j)=(dp(j-1)+*p*_{j - 1})**p*_{j}

### 235C - Cyclical Quest

This problem can be solved by many suffix structures.

I think suffix automaton is the best way to solve it because it is simple and clear.

So let us build a suffix automaton of the input string S.

And consider the query string x.

let us build a string t to be x concatenate x and drop the last char.

so every consecutive sub-string of t with length |x| is a rotation of x.

let us read string t with suffix automaton we've build, and every time take the first char out and add a new char,add the answer by the number of string equal to this current sus-btring of t(which is a rotation of x).

And one more thing,we should consider the repetend of x as well,

check my solution here:2403375

check this if you are not familiar with suffix automaton :e-maxx's blog

### 235D - Graph Game

First of all, let us consider the tree-case.

Let us consider the event like that: "when we select A as deleting point, B is connect to A" to be Event(A,B).

So any happened Event(A,B) would add *totolCost* by 1.

So we can just simply calculate the probability for every Event, and add them up.

let us consider how to calculate Event(A,B)'s probability.

Assume there's n vertices in path between A and B, the probability is simply 1 / *n*.

Let us try to prove it using induction.

First let us assume there's a connected sub-graph of the tree containing both A and B, if the sub-graph only has n vertices, then the event happen only if we select vertex A, so the probability is 1 / *n*.

Otherwise,assume it has x vertices there is two case: whether the selected vertex is on the path between A and B or not.

In the first case, the probability of Event(A,B) happen is 1 / *x* because if we don't select A, Event(A,B) will never happen.

In the second case, the sub-graph containing A,B has become smaller, so the probability is (*x* - *n*) / *xn*.

So add them up we can prove this statement.

Then we can solve the tree case by simply add up the inverse of every path's length in the tree.

And for the orginial case,there's at most 2 paths between A and B.

If there's only one path, then everything is the same with tree-case.

Otherwise, the path between A and B should pass the cycle in the graph.

Let us examine this case, you can see that there 2 types of vertex:

Vertex on path of A to cycle or B to cycle,they should not be selected before A because once they're selected, A and B lost connectivity,let us call them X.

Vertex on the cycle, they two path from A to B, each path contains a path in cycle, let us call them Y and Z.

So there's two possibility: X and Y are free when A is selected, X and Z are free when A is selected.

And we should subtract the case that X and Y,Z are all free when A is selected because it double-counts before.

So the probability is 1 / (*X* + *Y* + 1) + 1 / (*X* + *Z* + 1) - 1 / (*X* + *Y* + *Z* + 1).

Check Petr 's solution for the details: 2401228

And my C++ implementation: 2403938

### 235E - Number Challenge

Let us consider each prime in one step , the upper limit for *a*, *b*, *c* is recorded.

So if we fixed the power of 2 in each *i*, *j*, *k* like 2^{x}, 2^{y}, 2^{z} , then their upper limit become *a* / 2^{x}, *b* / 2^{y}, *c* / 2^{z}, and the power of 2 in their multiplication is just x+y+z.

Let us denote *dp*(*a*, *b*, *c*, *p*) for the answer to the original problem that *i*, *j*, *k* 's upper limit is *a*, *b*, *c*. And their can only use the prime factors which are not less than *p*.

Let the next prime to be *q*, so we can try to fix the power of *p* in *i*, *j*, *k* and get the new upper limit.

So we can do transform like this: *dp*(*a*, *b*, *c*, *p*) = sum of *dp*(*a* / *p*^{x}, *b* / *p*^{y}, *c* / *p*^{z}, *q*)·(*x* + *y* + *z* + 1)

Check my code here: 2404223

Also you can check rng_58 solution here: http://codeforces.ru/blog/entry/5600

If you have any problems, you can ask here :)

actually i m not able to get anything from your java code in cyclical quest Div-2 E . someone please explain it with the help of his c++ code

Thank You,

Oh...I think you should learn suffix automaton first if you want to understand it..I'll post some good materials about suffix automaton in the tutorials...after you learned suffix automaton, it's easy to solve this problem.

very very thank you..:)

I have better sol for Div 1.A only like this

Div 1.B, I think Ray030123 has better solution :)

yeah this is the perfect sol. for it..

Yes it is :)

Oh, thank you for translating my Python code here. * P.S. It's ray0(4)0123

yes, sorry :">

Please, can you tell why it's true?

If n mod 2 = 1 => res = n * ( n — 1 ) * ( n — 2 )

Of course it is, right ???

if n mod 2 = 0 { We can see that n and ( n — 2 ) have GCD is 2 => res = n * ( n — 1 ) * ( n — 2 )/2 It's is small, so we think about n * ( n — 1 ) * ( n — 3 ) But if n mod 3 = 0 we can see that the result is smaller :( So we think about ( n — 1 ) * ( n — 2 ) * ( n — 3 ) You should think more careful and then you will know why :D }

thank you

thank you !!

Thank you! :)

I dont think that ur saying if n mod 3 = 0 we can see result will be smaller is right, i think then n and n — 3 will no longer be co-prime in that case

How do you solve C using a different suffix structure? Say a suffix array.

Let us build a suffix array of s and concatenate those t-string made from x to its back.

then we can find each rotation's occur time in string s.

Could you give more detailed explanation of this solution, please?

How do we use suffix array to solve this problem?

Same question.

Firstly we should concatenate original string S and all the query strings (each doubled without last symbol), put different symbols between strings (e.g. 300, 301,..., it would be array of ints, not chars), then make a suffix array on that concatenated string. We will have 2 arrays — sorted suffixes of all the strings and lengths of common prefixes between them. Then we should build segment tree on the array of lengths to be able to quickly find minimum number on the any segment. Then iterate on the array of suffixes. For each suffix of query string we firstly should determine weather we use it (i.e. it is not equal to another shift of this query). We can determine it by getting the minimum number on the array of lengths between past occurrence of this query and current one. If we use it we should determine the number of suffixes of S that have common prefix with it not less than length of this query. We can calculate it by using binary search and segment tree (complexity O(log^2(n))) or by using treap (complexity O(log(n)))

Sounds nice. Did you try it though? I just coded it up, and can't get it to work in time. I construct the 3-million suffix array in 3 seconds and the rest of my code is O(n log n).

I have read your solution,It seem 3-million suffix array is too slow. well, There is a way using only 1-million suffix array construction.

You just construct the suffix-array of the string S. Then for each query x,binary-search the position in SA in O(logn+|x|),then you need add a char at the front to x and delete a char at end of it.

if we know the position of x in SA, then cx's position(means add a char at the front of x) can be calculated in O(log n) as well, when comparing cx to a suffix,you first compare the first char, then compare x to the suffix' next suffix(which we already know).

Yeah, this back-stepping method (x -> cx) is what I've been missing during the contest. I'll try to code it up later. Thank you!

My Div1A problem got accepted but I have no idea about the proof of the solution... can anyone provide me some??.........

In 235B, what do you mean by:

I means if the two 'O' in the pair have indexes i and J.

in div 2 problem C i am not able to understand why 50,,,,, why to check for triplet having greatest lcm in the range [n-50,n]

me, too. i've checked only triplets with n..n-5 at most and it get AC. Well, thanks to the author for good problemset (esp. for me, learning Math), but i expected to see some more strict manual with good explanation, why it goes well. "good" brute force is not the answer, you know...

50 is the upperbound, it is a aproximation solution. You can use 100 too.

in Problem "Lets play Osu", i am not able to understand what to do from the editorial... if u are writing the editorial make sure that u explain well and not 2 line explanation,,, learn something from Topcoder.com on how to write good editorials,,, being red doesnt mean that everyone is as experienced as u ..... we need good guidance.

So we had some sort of common problem (all wars come from it, i assure you) — "mis-", "not-" and "not full-" "-understanding". Please dont get me wrong.

Oh...I'll try to make it more clear today...But your handle say you're a red coder though :)

in India programming is not as good as in Russia or china or japan... but i assure u if i get good guidance i would definitely do better... can u give me ur Email id or Facebook Link so that i can contact u when having some trouble.. :)

http://ask.fm/WJMZBMR

anyway...I don't think born in India is an excuse, Actually I learned programming all from internet resource in English.As you are an India, I bet your English is better than mine.Just work harder bro.

Can you provide an English paper about suffix automata ?? Thank you . Chinese paper is also OK for me :)

http://fanhq666.blog.163.com/blog/static/8194342620123352232937/

I can't understand suffix tree, it's so hard for me....

Shouldn't the in solution for 235B be a ?

sorry,fixed

What happens after 235D — Graph Game is extended to a normal graph?

I think then it is totally unsolvable.

To the least you can use a O(2^n) dp instead.

But It can be solved in cactus, and the first version of this problem is on cactus, I think that is too hard so I simplify a bit.

orz))))

In Problem "Let's Play Osu!":

"It can be interpreted as, 2*number of pair of 'O' in this 'O' block + number of 'O' in this 'O' block."

What was the motivation for this? Or is it just experience? :)

Well, some thoughts just came out...It is hard to give a exact motivation...

If you are looking for proof for the statement, then n^2 = (1+1+1....n times)^2 = 1^2 + 1^2 +..n times + 2 * (all combinations of 1s...nC2 times) However, I can still not see an O(n) approach using the explanation. I wish if someone can show me an implemented solution using the above insight.

I solved the problem using the observation, that if an O is added at the end and we know the expected value(let say, X) of Os at the end then the score would increase by (X+1)^2 -X^2 = 2*X + 1

http://www.codeforces.com/contest/235/submission/2408731

http://www.codeforces.com/contest/235/submission/2408690

These are the link of my submission for Div1 problem E. The first one is Accepted and the second one is getting TLE. But the only difference of the solutions is that I called from last prime to the first prime in the first and in the second one was the reverse(From the first prime to the last).... the rest solutions are the same... but I have no Idea why it is happening so.... Am I missing something obvious?

If you have time, please comment part of your code. I solved some simple tasks using Suffix Automaton (those described in e-max blog) but it seems that you are augmenting the data structure. I can't understand the meaning of "nxt" nor "repetend".

sorry for troubles and thank you.

It's just a kmp-algorithm to get the repetend of the query x_i

thank you for your answer. i broke my mind for hours until i came up with a solution. after that, i went back to your code and could understand almost everything.

I tried that link on suffix automatons. I translated it with Google Translate. I could not understand what this means:

-------- Consider any non-empty substring t line s . Then called the set of endings endpos (t) set of all positions in the line s In which the end of the lines with t .

We will call two substrings t_1 and t_2endpos Equivalent if their sets of endings are the same: endpos (t_1) = endpos (t_2) . Thus, all non-empty substrings s can be divided into several classes according to their equivalence sets endpos . --------

I get it that "line s" means "string s". I am confused as to what is meant exactly by endpos(t). Does it mean all suffixes which end with 't'? And what is the significance of two substrings being endpos equivalent?

Thanks.

Please could anyone shed more light on the Let's Play Osu problem...I still haven't gotten the main idea...

Thank You!!!

Same problem with me.... Please someone explain deeply how to solve Let's Play Osu....

I am very busy this week(I'm a high-school student and have to go to school)...well,I'll do it tonight...

thats ok :)

pls explain one thing , in Lets Play Osu problem we have to consider each pair of O's so why u said consider only those pair of O's having no X between them....,

I tried a lot but did not understand the editorial of 235E Number Challenge. Somebody please explain in detail.

the same question.

Excellent idea on problem D in Div2. Is there any background? I don't think I can come up with this idea if I didn't see ti before.

WJMZBMR, your English is not very good. I'm hardly understanding what you meant in the post.

Dude, despite his english he has written a decent editorial and clarified everyone's doubts in the comments. You cannot expect everyone to know good English. It's just another language!

You are right, dude. I want too much.

your contest has nice problem !

if in the problem A wanted to find the ressult with 4 distinct number what would be the result????????

Check this, it is for general case k numbers.

http://ideone.com/DJiFpV

I dont understand how to handle the sizes of the DP in div 1 E. I see the numbers get smaller fast so sizes dont need to be 2000 for each but i have no idea how to code it. I dont know Java and each other submission i have checked was using the other solution. Can you help a bit?

http://codeforces.com/contest/235/submission/2400848

Thanks! Map is a cool thing i guess B)

10311089 Is Hasmap necessary? I couldnt make thıs code any faster? I only faıls the 2000 2000 2000 input B(

Can you tell me about the proof of LCM challenge problem ?

I can't understand the div1B idea Could someone explain it me please?

someone?

ok u.u

Does the A question have a solution that is not O(N^2)?

Question A, can be done in O(n).

Can u explain to me how to do it?

Use a set or an array to keep track whether you have seen a character before.

The editorial includes almost no explanation at all for the div2 E / div1 C problem except for telling that suffix automaton may be used and we should construct a string $$$t$$$ that is $$$(x + x)$$$ but doesn't include the last char.

Here is my approach for the problem using suffix automaton:

Note: The terminology used will be in reference to this article for suffix automaton.

We start by building suffix automaton on $$$s$$$. Let $$$t$$$ be the string as mentioned above for the query string $$$x$$$. As noted, a substring of length $$$|x|$$$ of $$$t$$$ is a rotation of $$$x$$$.

Firstly, we precompute a $$$dp$$$ table using the SA: $$$dp[i]$$$ = No. of terminal nodes reachable from the $$$i$$$-th node. This will tell us how many suffixes can be attached to the current substring when we are at node $$$i$$$, which will give us the no. of times the current substring occurs as a substring in $$$s$$$. This is because a substring is just a prefix of some suffix and $$$dp[i]$$$ tells us exactly how many suffixes can be attached to the current substring to make a suffix, such that the current substring will be a prefix for them.

Now, let's have $$$2$$$ pointers (indices) $$$i$$$ and $$$j$$$ in $$$t$$$, $$$j$$$ points to the next char in $$$t$$$ that needs to be concatenated to the current string and $$$i$$$ tells us that we are considering the substring of $$$t$$$ starting at position $$$i$$$. To get all cyclic shifts, we iterate $$$i$$$ from $$$0$$$ to $$$(m-1)$$$. When we are at $$$i$$$, we'll have to extend our substring to include char $$$t[j]$$$ and drop the char $$$t[i-1]$$$. To drop the $$$(i-1)st$$$ char, note the $$$minlen$$$ of the current node, using the fact that $$$minlen(cur) = len(link(cur)) + 1$$$. If $$$minlen(cur) \le len$$$, the substring $$$t[i..j-1]$$$ will be found at the cur node, and we do not need to move to any other node. If however, $$$minlen(cur) > len$$$ (more precisely, $$$minlen(cur) == len + 1$$$), the substring $$$t[i..j-1]$$$ cannot be found at the current node, so we follow the suffix link to go to the node where it will be found and set that to the new cur node. After dropping $$$t[i-1]$$$, the string we have corresponds to $$$t[i..j-1]$$$. So, its length, $$$len = (j - i)$$$.

Now, we will try to extend our current string to be of length $$$m = |x|$$$ (if possible). That is, while $$$(j - i) < m$$$ and there is a transition possible from state $$$cur$$$ corresponding to $$$t[j]$$$, we'll make the transition and set $$$cur$$$ to the node at the other end of the transition. After that, we'll check to see if we have found a string of length $$$m$$$ or not. If $$$(j - i) < m$$$, we did not find the string of length $$$m$$$ starting at $$$t[i]$$$ to be present in the SA (or in the string $$$s$$$), so we continue our procedure by incrementing $$$i$$$ to consider the next substring. If however $$$(j - i) == m$$$, we have found the string starting at $$$t[i]$$$ in $$$s$$$, so we add $$$dp[cur]$$$ to the answer.

There is one technical detail missing in the above explanation. Consider the case when a substring is occurring more than once as a cyclic shift. For example, if $$$x =$$$ "$$$aa$$$", then $$$t[0..1] = t[1..2] =$$$ "$$$aa$$$". So, the substring "$$$aa$$$" would get counted twice, however we need every substring exactly once in the answer. To avoid this, note that for two $$$m$$$ length strings to be identical, we must be at the same state in the SA when considering these two strings. This follows from the properties of SA, since a state can correspond to atmost one string of length $$$m$$$. So, we may keep a set of visited states and if $$$cur$$$ state has already been visited, we do not add $$$dp[cur]$$$ to the answer to avoid overcounting.

Here is my solution using this idea: 51809558

I developed the following intuition for Div1 A. Our final aim is to reduce the number of common factors between as large numbers as allowed so as to get the largest LCM. So, firstly, if the numbers are <= 3, we have no choice but to output 1, 2 (1 * 2), 6(1 * 2 * 3) respectively. Now n can be either even or odd. We know that no two consecutive odd numbers have a common factor other than 1. So, in case n is odd, we can go ahead and output n * (n — 1) * (n — 2). Clearly, n and n — 2 don't share any common factor here, nor does n — 1 have a common factor with either of these ( also not that n — 1 will be even while others are odd).

Now when n is even. If we go like odd numbers and output n * (n — 1) * (n — 2), we might be wrong due to the following reasons.

n and n — 2 actually share a common factor, which is 2.

So should we go and output n * (n — 1) * (n — 3) then ? NO. What if n was divisible by 3 too ? Now, we are actually including n and n — 3, that both share 3 as a common factor, and thus will end up with a wrong answer ! So, there are two sub cases: 2.1) n is divisible by 3. If that is the case we output (n — 1) * (n — 2) * (n — 3). Clearly n — 1 and n — 3 are odd and don't share any common factor, nor does n — 2, which is even. 2.2) n not divisible by 3. In this case we can easily go ahead with n * (n — 1) * (n — 3) !

I hope this helps.

My code: https://codeforces.com/problemset/submission/235/52744967