ConstructorU's blog

By ConstructorU, history, 3 years ago, translation, In English

Dear Codeforces,

SIT

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!

  • Vote: I like it
  • +221
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Same here.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Perfect, thanks! Looks like a nice combination!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone got any confirmation mail after signing up ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You probably meant February not January.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hello [user:SITstarContest,2021-02-03], why the wrong answer on sample test 1 is treated as a penalty?

Thanks.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve L in practice round?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone help how to solve problem G?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H ??

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can be implemented with O(n) solution

    Code
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could someone kindly explain I,J,K problems?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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$$$.

    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)$$$.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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