Dear Codeforces,

Today, Schaffhausen Institute of Technology in Switzerland is opening SIT STAR Contest to promote interest in Computer Science and Software Engineering. The final round is scheduled for February 10, but you can already sign up and practice for the big day. In this contest, you get to solve up to 12 challenges in algorithmic programming in just 4 hours and a chance to study at SIT with a full scholarship!

**When?**

**February 1-7, 2021 | Practice Round**You can already try the testing environment. Although not obligatory, this step will help you feel more confident during the actual contest. The results of this practice round won’t affect your final score.**February 10, 2021 | SIT STAR Contest**Join the final round on February 10 at 8 am UTC. You will have 4 hours to complete the tasks.**June — July 2021 | Interviews and Winners Announcement**The participants with the highest scores will be invited for an interview with the Professors from SIT. Based on the results of the interview, you may be offered a full scholarship for MSc in Computer Science and Software Engineering at SIT.

**In SIT STAR Contest, you can:**

- solve mind-blowing algorithmic problems efficiently and fast
- get noticed by top-level science and tech leaders from SIT
- win surprise gifts from Switzerland
- compete for SIT STAR Scholarship

We offer several full scholarships and several tuition waivers for MSc in Computer Science and Software Engineering. To learn more about the program, click here.

SIT STAR Contest is open to everybody. Everybody can participate in the contest for free.

**However, if you are competing for the SIT STAR Scholarship prize, you should:**

**Have a bachelor's degree in Computer Science or any other STEM field, or be in the final year of your studies.****Speak English at a level sufficient to pursue graduate studies.**

**Meet SIT**

Schaffhausen Institute of Technology is founded by entrepreneurs, led by scientists, and advanced by world-class researchers. Based on a blended education model, SIT brings knowledge through science and shapes next-gen digital leaders. To learn more, head to http://sit.org.

Good luck!

I'm getting "Specify correct handle or email" when I entered login and password from the email.

Same here.

For my case that was just spaces after email. I was copying my login and there was a space

Please delete all the spaces after entering your email. It should work. Thank you!

i am not getting an email even after specifying details correctly?

what should we select as the university if our university name isn't there?

also what is that discipline column?

If it's gmail email, please check the "Promotions" section of gmail account. If no, please feel free to send a direct message and we will check your registration.

In the University field, you can choose a university from the list or write the name of the university. It's possible to enter university names there as well.

To the Discipline field, please enter a discipline of your degree, like Computer Science, Applied Mathematics, etc.

What's the approximate difficulty level of problems in the contest? Div 1 or 2?

The tasks are different, from simple ones to more difficult ones. We'd say it contains problems of Div 4, Div 3, and Div2.

Perfect, thanks! Looks like a nice combination!

Did anyone got any confirmation mail after signing up ?

We have sent a personal message to you to check your registration. Please reply.

Some of the participants already started a practice round, which means they received the confirmation email with their credentials.

Hey, I did not receive the confirmation mail after signing up. It's been 4 hours. Can I know how long would it take for the confirmation mail to come?

You should receive the confirmation email in several minutes.

Please send an email with which you registered to the chat with us, we will check your registration. We've already sent a message to you there.

i would like to partipicate but ,I like many other contestants will not be able to compete due to school/university/work. isn't it better to shedule it for sunday or saturday?

(Should/ When can) we expect an editorial to be rolled out for the practice round?

Editorial will be just for the main round (Contest itself). If you have any questions about the tasks of the practice round, you can ask and discuss them here after February 7.

Please do test your system before

Div3contests.30K+programmers participated last time, but due to queue issue it was declared unrated. It should not happen again. We hardly get oneDiv3contest in a month.This seems to be a good way to bring like-minded individuals together.

Can we discuss the problems for the practice round here or is it not allowed?

Please, start to discuss problems of the practice round after February 7.

We will open a practice round for upsolving after February 7, that you can submit all the problems and practice as much time as you want.You probably meant February not January.

Thanks and fixed! :)

Since the practice round is over now. Can we expect editorials.

Editorial will be just for the main round (Contest itself). If you have any questions about the tasks of the practice round, you can ask and discuss them here.

Hello SITstarContest, why the wrong answer on sample test 1 is treated as a penalty?

Thanks.

How to solve L in practice round?

Let’s suppose we’ve a fibonacci sequence with F0 = a and F1 = b. The first few terms of this sequence are: a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b... and so on. We can notice that the coefficient of F0 and F1 follow as: {0, 1}, {1, 0}, {1, 1}, {1, 2}, {2, 3}, {3, 5}, {5, 8}. Easy to notice that each term is a sum of previous 2 terms. Let's call these pairs as restricted pairs (i.e. the possible pairs of coefficient's in a fibonacci term)

Now given a fibonacci number N, we can represent N as: a * x + b * y = N, where {a, b} is one of the restricted pairs. Since 1 <= N <= 1e9, we've the same constraints for a, b, x, and y. (1 <= a, b, x, y <= 1e9). There are less than 50 restricted pairs in given constraints.

So, we can iterate over all possible pairs of {a, b} and find number of solutions of the equation: a * x + b * y = N, with 1 <= x, y <= 1e9. This is a standard algorithm in Linear Diophantine Equations. You can read this here.

Click here to see my solution.

Great solution! Thanks!:D

I was not thinking about the property of Fibonacci numbers, but furiously trying to force the time into the limit using algorithms :(

Interesting solution. I just brute-forced for small $$$n$$$, printed out the "reverse Fibonnacci chains", and made some observations that led to a not-so-pretty recurrence formula, but hey it works lol

How to solve F ?

Generate all possible 2^n numbers and check them. You can generate them using bitmasking. Traverse from 0 to 2^n — 1. Let's assume the binary representation of current number is 00110001. Treat this number as: 22112221 i.e. traverse the bits of the binary representation of current number, if current bit is 0, change it to 2 and if it is 1, leave it as it is.

If you solve when n is small by hand, you can find some order between the numbers.

n is very small, so you can write all the solutions with conditional statements.

codeor just finding sequence here https://oeis.org/A053312

Anyone help how to solve problem G?

Its a simple application of Principle of inclusion-exclusion.

You can use principle of inclusion-exclusion, however a simpler-to-code way would be to note that the cost of an issue is only determined by its number modulo $$$\text{lcm}(2, 3, 5) = 30$$$. Thus you can precalculate the cost of an issue for each residue class modulo $$$30$$$, and use some math and prefix sums to find the answer.

How to solve H ??

Problem H is implementation. Just simulate the process in statement k times. Time complexity is number of not bad elements which is equal

n, multiply bylognbecause ofstd::set, so result time isO(n*logn). Code is here:Code is hereThanks !

can be implemented with O(n) solution

CodeIt is asking me to be group memeber of some group before I practice the contest. Am I missing something here ?

could someone kindly explain I,J,K problems?

For J: I used the "Binary Search on Answer" method. I wrote a function $$$F(x)$$$ that tells whether we can split array $$$A$$$ into $$$<=K$$$ segments each with a total time of at most $$$x$$$. If we have a number of segments $$$<=K$$$, we can split some of them up to make the number exactly $$$=K$$$. Obviously, if any of the $$$A_i s$$$ is $$$>x$$$, we can't have that $$$x$$$. Finally, the answer is the minimum such possible $$$x$$$. Complexity is $$$O(Nlog(S))$$$ where $$$S$$$ is the sum of elements of $$$A$$$.

AC Code for Jhttps://pastebin.com/ZXu2pAPr

For I: I think the technique is called line-sweep (correct me if I'm wrong). Basically, the only times that matter are the ones where changes are occurring i.e.

either some friend comes or someone leaves.There are exactly $$$2n$$$ such points of time. Pass through all of them in chronological order. Say the current time is $$$t$$$, then you will leave at time $$$t+m$$$. Now, if there are any friends such that $$$t$$$ lies between (inclusive) of entry and exit times, set their entry time as $$$min(t, time_{exit})$$$. That way we don't have to worry about including or excluding them as you slide the window. Finally, for each such time, calculate the number of friends in the window using their $$$time_{entry}$$$ and take the maximum overall such values. Complexity: $$$O(NM)$$$.AC Code for Ihttps://pastebin.com/BBt35kCZ

K: Generate a directed graph where edge $$$u \rightarrow v$$$ represents "tower $$$u$$$ will alert tower $$$v$$$". This graph can have up to $$$O(n^2)$$$ edges.

Then find the strongly connected components of the graph. There are several efficient $$$O(V + E)$$$ algorithms to do so; it can be a bit of a chore to implement, but it's worth having in your template. The AtCoder library also has an implementation.

Now a key observation is that if any tower in a strongly-connected component is alerted, all of them will be alerted. Additionally, there may be directed edges between components that will spread alertness between components.

Let $$$S$$$ be the set of towers that are initially alerted. If a strongly-connected component doesn't have any incoming edges from other components, at least one of the towers must be included in $$$S$$$. Thus if $$$k$$$ is the size of the component, the number of possible configurations for this component is $$$2^k - 1$$$ (as we "ban" the all-zero state). On the other hand, if there are incoming edges to a component, there is no constraint on its towers, as the incoming edges are guaranteed to spread alertness to it, thus the number of possible configurations remains $$$2^k$$$. The answer is the product of these values for each component.

K was my favourite!

Oh btw did anyone else notice that in practice problem J it's implied that there're over $$$10^9$$$ minutes in a day? :P

Well I still would've wasted more than half of it!