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.
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?
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 ?
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.
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.
Hello [user:SITstarContest,2021-02-03], 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.
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.
or just finding sequence here https://oeis.org/A053312
Anyone help how to solve problem G?
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 by logn because of std::set, so result time is O(n*logn). Code is here:
can be implemented with O(n) solution
It 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$$$.
https://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)$$$.
https://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.
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!