There will be some surprising gifts from Switzerland :)

It seems that you logged in with your common Codeforces account. Please log out, use the credentials that we sent to you in the email.

The SIT STAR Contest is not rated.

You can participate in the SIT STAR Contest. Just add the name of your university by entering it in this field. There is such an option. Thanks!

I had same issue try to open the site from the first mail they sent for the verification

try this https://sitstar2021.contest.codeforces.com/

me too.

same with me.

Please make sure that you: 1) Registered here; 2) Received a confirmation letter with the credentials to log in. 3) Enter the data in the field without adding a space before or after;

Me, too. What happened?

Same with me . Help !

Please check the promotions folder or spam. You can send your email to messages and I will provide credentials to you there.

After registration for the contest, you should have received an email with the link and your credentials. If you can not find the email, please check the promotions folder and spam.

It's like Euclidean algorithm for GCD. Our task is in minimization of given pair (x, y) and we can do the following transformation in one operation: (x, y) -> (x, y — x). Of course we can do it only with x < y. Notice that the order of numbers in pair doesn't matter(if we have (a, b), then we also have (b, a)). Then, just find is it possible to get (1, 1) from (x, y). You can do it iteratively, with one easy optimization(try it by yourself)

The editorial was posted here https://drive.google.com/file/d/1CrBz9Ddk7LaLRhnjizUAo7IWv9JmOO-e/view

SIT STAR Contest editorial is already available on the Main tab of the Contest link.

We hope you liked the problems!

We can use one or two the most frequent numbers. While counting the numbers, try to avoid cases, when a[i] == b[i].

Yes, please, the SIT STAR COntest is opened for upsolving.

If you were registered for the Contest, you can now take part virtually.

To do this, please follow the link that we sent in the email, enter credentials from the email and start virtual participation.

Did you register for the SIT STAR Contest? If yes, please check your promotions folder or spam for the link and your credentials. If you still can not find the email with the link and credentials, please contact us via messages here.

Winners will be announced next week.

Thank you for your participation and interest in SIT! We hope you enjoyed the problems!

I am sharing my solution here, but note that it's for $$$O(|s|^2)$$$ which is a little overkill for this problem.

Suppose there are 1000 rows and the string s is "abc".

Now, let's consider how many solutions exist if you start at the first position of the first row. It's basically $$$2^{|s|-1} = 2^2$$$ (because you have two steps you can go from the first position: a->b, b->c; and in each step you can go either down or right).

Note that the number of solutions for row 2, 3, 4, 5.... 998 is the same as well. So you can just add $$$998 \times 2^2$$$ to answer for that.

Now, what about the rest? Consider row 999. In this case, the number of solutions is no longer $$$2^2$$$ as you can't go down twice. Note that there can be $$$|s|-1 = 14$$$ such rows at most. So for those, we can just do a DP where states are the number of rows left and the current position in string i.e. $$$O(|s|^2)$$$ complexity.

The DP formula is $$$DP[rowLeft][pos] = DP[rowLeft][pos+1] + DP[rowLeft-1][pos+1]$$$.

Here, the first term $$$DP[rowLeft][pos+1]$$$ represents going one step right, the second term $$$DP[rowLeft-1][pos+1]$$$ represents going one step down (this might be invalid, so that condition needs to be checked). The reasoning is like — when you go one step right or down, you are going into next position of string s, and when you are going one step down, you have one less rowLeft.

See how this will fit in constraints of the original problem even if $$$rowLeft \leq 10^4$$$? That's the idea shown in the editorial. Just instead of rowLeft, they used something like currentRow and incremented that instead of decrementing (will give same result).

Here's my code written based on the above idea.

My unofficial editorial for practice problem K