Hey Codeforces,

Don’t miss tomorrow’s SIT STAR Contest 2021, organized by the Schaffhausen Institute of Technology (SIT) in Switzerland to promote interest in Computer Science and Software Engineering.

The online coding contest will be happening tomorrow on February 10, from 8:00 to 12:00 am UTC.

During the event, you will face 12 or 13 algorithmic programming challenges of increasing difficulty (Div 4, Div 3, Div 2). The contest is open to all, and you can sign up for free here.

**Why participate?**

Apart from being a fun coding experience, SIT STAR Contest 2021 is the easiest way to enroll in a fully-funded master’s program in Computer Science and Software Engineering at SIT. The prizes at stake range from small souvenirs from Switzerland to tuition waivers for master’s students to full scholarships the cover both tuition and living expenses.

Note that you must hold a bachelor’s degree or be in the final year of your studies to join SIT in September 2021.

Don’t miss your chance to continue your studies at SIT!

**More about SIT**

Schaffhausen Institute of Technology is founded by entrepreneurs, led by scientists, and advanced by world-class researchers. Based in Schaffhausen, Switzerland, SIT drives knowledge through science across many projects. In particular, SIT Master’s offers a blended degree in Computer Science and Software Engineering that you can attend in person, online, or as a mix of both.

I really liked the questions in the practice round, which did not require high-level algorithms, but had a substantial difficulty and were very fun to solve:)

Waiting for the main contest!

Yeah they were pretty good problems.

This looks interesting! Another step towards being Hokage of Coding!

Will there any prizes for top participants, like t-shirts or other souvenirs?

There will be some surprising gifts from Switzerland :)

Which top of people will have gifts?

ANIME NOT GUT!!!

When i enter the SIT codeforces contest it tells me that the access is denied — Will it be open for people some min before the contest ?

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.

will the contest be rated?

The SIT STAR Contest is not rated.

What was the intended solution for Problem K?

Was it SCC+combinatorics or not?

In either case, could someone please share the solution!?

UPD:Got the solution, thanks!I couldn't find my university when registering

So if my university is not in the list I can't participate ?

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 am try to login with the credentials provided in the mail. But it says wrong username or password. Please help!

Please delete spaces after your email. It should help

I don't think that it's an issue with the e-mail address. I entered it by hand few times.

I can't able to log in. It is showing "Suspicious activity registered". How to solve this?

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

Thanks, It worked.

I'm trying to log in but it says "Suspicious activity registered. Repeat your action in a few minutes.". What should I do?

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

Thanks!

I can't log in using provided password, anyone having the same issue?

me too.

Please try to delete all the spaces after the email. It should help.

Still can't login!!

Same

I can't either.

Same here.

I'm getting this SITstarContest

`Suspicious activity registered. Repeat your action in a few minutes.`

`Invalid handle/email or password`

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;

Can't login.

Suspicious activity registered. Repeat your action in a few minutes.

Me, too. What happened?

Please for entering the contest use the credentials we sent you in the email. When you enter credentials, please delete all the spaces after the email.

It should help.

It doesn't help

I'm copy/pasting the same but it still shows the same error: suspicious activity, and invalid handle/password

suspicious activity --> try in several minutes, probably you have tried to log in too many times.

invalid handle/password --> enter your email without any additional spaces, same for the password. Double-check this, it should work.

Why everytime it is showin

Access denied????Please send to the messages an email with which you try to register.

sent 5 mins ago... still noreply

Same with me . Help !

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;

try to login through the practice now mail and u will not get any suspicious activity problem.

I registered twice but didn't get any mail can someone help

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

where is the contest link???

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.

nice contest on constructive. my brain exploded

Contest was nice, but unfortunately, Problem M — Binary Strings was available on SPOJ.

willl there be prizes for top 70?

Will there be a Editorial?

And how to do the problem -> (a, b) becomes (a + b, b) or (a, a + b).

Just came up with a BFS solution, but that would TLE obviously.

do (a+b)/a while a!=0 or b!0 etc

You can notice, that if we have pair (a, b) (where a is less than b), on previous step we had a pair (a; b — a). If b — a > a, two steps ago we had pair (a; b — 2 * a), three steps ago — (a; b -3 * a) and so on. So you just add b / a to answer and go from pair(a; b) to pair (b % a; a). If a = 1, you add (a — 1) to answer and finish calculation, if a != 1 ans b % a == 0 than answer is -1.

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)

Thanks got it but how to prove that going from (x, y) to (x, y%x) will give the minimum possible answer ?

My Solution for E : https://pastebin.com/EF1M9G3V

The smaller the difference between x and y, the faster numbers will decrease, right? So when you are doing y = y % x, you will get y between 0 and x — 1. You can not get something more closer to x

Thanks.

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!

What is the solution to the problem Cards and Numbers?

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

Is it possible to submit for practice after the contest is over?

No, it seems we can't. It says

`'Contest is over.'`

UPD: you can submit now!:)

Try now

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

could you please enable viewing other people's submissions? thanks

do we have an online mirror for the contest ??

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.

How to be part of the group? I want to check the editorial but I can't view it. I am not able to find the invite anywhere. Where it was sent?

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.

I participated in the contest. I have the credentials. How to view using them?

Thanks, I got the editorial. Btw great problems. Will try next year again.

Please login the same way as you did for the Contest. There is a "Home" tab where we added the SIT STAR Contest editorial.

where i can find editorial ? I found https://sitstar2021.contest.codeforces.com/group/1HLBM0lmlk/blog pdf https://drive.google.com/file/d/1CrBz9Ddk7LaLRhnjizUAo7IWv9JmOO-e/view

How to be a part of the group? I can't see the editorial also don't get any mail.

Now I can see the editorial from home tab. But don't get any mail about the link and credentials.

When we will know about prizes and the free Master Degree program?

Winners will be announced next week.

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

Can you please allow us to view the submissions of other participants?

Can anybody show their solution to problem G? I read the editorial but still a little confused about it.

Thanks in advance.

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.

Please could you make the test cases visible for the Practice and Main contests, now that they are over?

In particular in the case of the Practice contest, in the absence of an editorial I am at a loss on question K. With no editorial, no access to others' solutions, and no visibility of test case 22 (which I keep failing), it's very difficult to know what I've done wrong.

Thanks

My unofficial editorial for practice problem K

Thank you!

Where to see final results of contest?