### SITstarContest's blog

By SITstarContest, history, 3 months ago, translation,

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?

1. 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.
2. 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.
3. 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.
Sign Up→

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.
Sign Up→

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!

• +221

 » 3 months ago, # |   +3 I'm getting "Specify correct handle or email" when I entered login and password from the email.
•  » » 3 months ago, # ^ |   +3 Same here.
•  » » » 3 months ago, # ^ |   0 For my case that was just spaces after email. I was copying my login and there was a space
•  » » » 3 months ago, # ^ |   +5 Please delete all the spaces after entering your email. It should work. Thank you!
•  » » » » 3 months ago, # ^ |   0 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?
•  » » » » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   0 What's the approximate difficulty level of problems in the contest? Div 1 or 2?
•  » » 3 months ago, # ^ |   +15 The tasks are different, from simple ones to more difficult ones. We'd say it contains problems of Div 4, Div 3, and Div2.
•  » » » 3 months ago, # ^ |   +8 Perfect, thanks! Looks like a nice combination!
 » 3 months ago, # |   0 Did anyone got any confirmation mail after signing up ?
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 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?
•  » » » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   0 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?
 » 3 months ago, # |   0 (Should/ When can) we expect an editorial to be rolled out for the practice round?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +12 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.
 » 3 months ago, # |   -10 Please do test your system before Div3 contests. 30K+ programmers participated last time, but due to queue issue it was declared unrated. It should not happen again. We hardly get one Div3 contest in a month.
 » 3 months ago, # |   0 This seems to be a good way to bring like-minded individuals together.
 » 3 months ago, # |   0 Can we discuss the problems for the practice round here or is it not allowed?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » 3 months ago, # ^ |   0 You probably meant February not January.
•  » » » » 3 months ago, # ^ |   0 Thanks and fixed! :)
•  » » » 2 months ago, # ^ |   0 Since the practice round is over now. Can we expect editorials.
•  » » » » 2 months ago, # ^ |   0 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.
 » 3 months ago, # |   +6 Hello SITstarContest, why the wrong answer on sample test 1 is treated as a penalty?Thanks.
 » 2 months ago, # |   0 How to solve L in practice round?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 2 months ago, # ^ |   0 Great solution! Thanks!:DI was not thinking about the property of Fibonacci numbers, but furiously trying to force the time into the limit using algorithms :(
•  » » » 2 months ago, # ^ |   0 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
 » 2 months ago, # |   0 How to solve F ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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. codeif(a==1) puts("2"); else if(a==2) puts("12"); else if(a==3) puts("112"); else if(a==4) puts("2112"); else if(a==5) puts("22112"); else if(a==6) puts("122112"); else if(a==7) puts("2122112"); else if(a==8) puts("12122112"); else if(a==9) puts("212122112"); else if(a==10) puts("1212122112"); else if(a==11) puts("11212122112"); else if(a==12) puts("111212122112"); else if(a==13) puts("1111212122112"); else if(a==14) puts("11111212122112"); else if(a==15) puts("211111212122112"); else if(a==16) puts("1211111212122112"); else if(a==17) puts("11211111212122112"); else if(a==18) puts("111211111212122112"); 
•  » » 2 months ago, # ^ |   0 or just finding sequence here https://oeis.org/A053312
 » 2 months ago, # |   0 Anyone help how to solve problem G?
•  » » 2 months ago, # ^ |   0 Its a simple application of Principle of inclusion-exclusion.
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 How to solve H ??
•  » » 2 months ago, # ^ |   +1 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: Code is here/** * author: said_v15 **/ #include #include using namespace std; using namespace __gnu_pbds; typedef tree, rb_tree_tag, tree_order_statistics_node_update> oset; typedef long long ll; #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define forn for(int i=0;i>questions; while(questions--) { int n,k; cin>>n>>k; string s; cin>>s; if(n==1) { cout< se; for(int i=0;i del; vector add; while(k--) { del.clear(); add.clear(); if(!se.size()) break; for(auto &x: se) { int pos=x; if(pos==0 || pos==n-1) { s[pos]='*'; del.pb(pos); continue; } del.pb(pos); s[pos]='*'; if(s[pos+1]=='.') add.pb(pos+1); if(s[pos-1]=='.') add.pb(pos-1); } for(auto &x: del) se.erase(x); for(auto &x: add) se.insert(x); } cout<>questions) // cout <<"Runtime is: "<
•  » » » 2 months ago, # ^ |   0 Thanks !
•  » » 2 months ago, # ^ |   0 can be implemented with O(n) solution Codeimport java.io.*; import java.util.ArrayList; import java.util.StringTokenizer; public class codeforcesSIT_H { private static void solve(FastIOAdapter ioAdapter) { int n = ioAdapter.nextInt(); int k = ioAdapter.nextInt(); char[] a = ioAdapter.next().toCharArray(); int start = -1; int end = -1; ArrayList list = new ArrayList<>(); for (int i = 0; i < n; i++) { if (a[i] == '*') { if (i == 0 || a[i - 1] == '.') { start = i; } if (i == n - 1 || a[i + 1] == '.') { end = i; list.add(new int[]{Math.max(0, start - k), Math.min(n - 1, end + k)}); } } } if (!list.isEmpty()) { ArrayList res = new ArrayList<>(); res.add(list.get(0)); for (int i = 1; i < list.size(); i++) { if (list.get(i)[0] - 1 <= res.get(res.size() - 1)[1]) { res.get(res.size() - 1)[1] = list.get(i)[1]; } else { res.add(list.get(i)); } } for (int[] re : res) { for (int i = re[0]; i <= re[1]; i++) { a[i] = '*'; } } } for (int i = 0; i < a.length; i++) { ioAdapter.out.print(a[i]); } ioAdapter.out.println(); } public static void main(String[] args) throws Exception { try (FastIOAdapter ioAdapter = new FastIOAdapter()) { int count = 1; //count = ioAdapter.nextInt(); while (count-- > 0) { solve(ioAdapter); } } } static class FastIOAdapter implements AutoCloseable { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter((System.out)))); StringTokenizer st = new StringTokenizer(""); String next() { while (!st.hasMoreTokens()) try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } int[] readArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } long nextLong() { return Long.parseLong(next()); } @Override public void close() throws Exception { out.flush(); out.close(); br.close(); } } } 
 » 2 months ago, # |   0 It is asking me to be group memeber of some group before I practice the contest. Am I missing something here ?
 » 2 months ago, # |   0 could someone kindly explain I,J,K problems?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +1 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/ZXu2pAPrFor 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
•  » » 2 months ago, # ^ | ← Rev. 4 →   +1 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.
•  » » » 2 months ago, # ^ |   0 K was my favourite!
 » 2 months ago, # | ← Rev. 3 →   +1 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
•  » » 2 months ago, # ^ |   +8 Well I still would've wasted more than half of it!