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,

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

readln( n );
                if n = 1 then Result( 1 );
                if n = 2 then Result( 2 );
                if n = 3 then Result( 6 );
                if odd( n ) then
                        res := n * ( n - 1 ) * ( n - 2 )
                else
                        begin
                                if n mod 3 = 0 then
                                        res := ( n - 1 ) * ( n - 2 ) * ( n - 3 )
                                else
                                        res := n * ( n - 1 ) * ( n - 3 );
                        end; 
                Result( res );

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

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

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:

So if they are i, 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]

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.

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

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

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

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? :)

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.

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

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

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.

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

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

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.

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

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.net/problemset/submission/235/52744967

In 235A LCM Challenge, (n-1)*(n-2)*(n-3) doesn't works when input is 10...

In 235A, I managed to solve the problem as follows in O(1):

1. If n = 1, ans = 1.

2. If n = 2, ans = 2.

3. If n is odd, ans = n * (n — 1) * (n — 2).

4. If n is even and divisible by 3, ans = (n — 1) * (n — 2) * (n — 3).

5. If n is even but not divisible by 3, ans = n * (n — 1) * (n — 3).

Here is my submission: 73660151

Idea of 235B was slick! YuukaKazami