When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

MikeMirzayanov's blog

By MikeMirzayanov, 4 years ago, In English

Hello!

Together with colleagues Schaffhausen Institute of Technology we hold such an event. If you want to study in Switzerland, then perhaps this is your chance!

— Mike

Hello, Codeforces!

SIT

We are thrilled to announce a new SIT STAR Contest by the Schaffhausen Institute of Technology in Switzerland. The winners will have a chance to get a fully-funded Master’s scholarship in Computer Science and Software Engineering.

What is the SIT STAR Contest?

The goal of the SIT STAR Contest is to promote interest in the field of Computer Science and Software Engineering, give students an opportunity to demonstrate their knowledge of programming, and be considered for a fully-funded graduate scholarship. You can apply to the contest here!

The SIT STAR Contest consists of:

  1. June 1-7, 2020 | Practice: To familiarize yourself with the testing environment, you will first be granted access to a practice round. You can practice any time from 1st to 7th June 2020. This is an optional step but we highly recommend to take part in it. The results of this round won’t affect the final score.
  2. June 17, 2020 | SIT STAR Contest: The final round will take place on 17th June. The participants will be given 4 hours to complete it.
  3. June — July, 2020 | Interviews and Winners announcement: Top participants with the highest scores will be invited for the interviews with the professors from the Schaffhausen Institute of Technology.

The SIT STAR Contest will include 8-12 problems of various levels of difficulty in algorithmic programming.

APPLY→
Winners and prizes

Here is what we offer for the best candidates of the interview round:

  • Several scholarships with 100% tuition coverage for one of the Master’s programs offered by SIT
  • Multiple scholarships with 20% tuition coverage for one of the Master’s programs offered by SIT
  • Surprise gifts from Switzerland

The number of scholarships will be decided based on the quality of the candidates.

What is the SIT STAR Scholarship?

The SIT STAR Scholarship covers the full cost of tuition at the Schaffhausen Institute of Technology in Switzerland. The scholarships are available for any of the Master’s programs offered by SIT starting in September 2020:

  • MSc in Software Engineering and Digital Leadership (4 semesters)
  • Double degree in collaboration with Carnegie Mellon University (CMU) in Pittsburgh, the USA, and the National University of Singapore (NUS) in Singapore
  • Fast track: MSc in Software Engineering and Digital Leadership (3 semesters)

To be considered for the SIT STAR Scholarship you need to:

  • Have a bachelor’s degree in Computer Science or any other STEM field
  • Speak English at a level sufficient to pursue graduate studies
  • Be a resident of Eastern Europe (including Russia), South Asia or Southeast Asia

What is SIT?

SIT is located in Schaffhausen (Switzerland) and founded by entrepreneurs, led by scientists, and advanced by world-class researchers.

Students, academics, and industry need a new model of education for the challenges in today's hyper-connected, data-driven world. SIT bridges the gap between education, research, and applications for industry, unifying them in one institution. SIT research and education removes the traditional barriers between specialities and thrives on interdisciplinarity.

Why SIT?

The institute encompasses a global community of prestigious high-ranking science and technology universities, featuring some of the best teaching support in the world. The course offers the unique option of graduating with a dual degree from one of SIT's partner institutes — the Carnegie Mellon University (CMU) in Pittsburgh, United States, or the National University of Singapore (NUS) in Singapore.

The SIT International Master Program in Computer Science and Software Engineering prepares the technology leaders of the future. By combining in-depth technical education in computer science, software engineering, and other advanced technologies with training in management and decision-making sciences, it fills the needs of innovative companies for a new generation of leaders, both technically expert and management-savvy.

The SIT program is flexible and adapted to many different individual situations. It is available both onsite in Schaffhausen and in an online offering, as well as any onsite-online combination. It offers qualified students attractive scholarships and the possibility of a second year in one of our partner universities in Europe, the USA, and Asia.

What should I do to participate in the SIT Star Contest?

  1. Love solving programming challenges
  2. Fill out the contest registration form
  3. Register at Codeforces using a special link you will receive in the confirmation email. Please fill in the same email address you used in the registration form.

If you have any further queries, please reach out to [email protected]

Good luck!

Tags sit
  • Vote: I like it
  • +333
  • Vote: I do not like it

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

Awesome!

Since the schedule is settled it would be nice to open a registration for the contests already :)

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

    The registration will automatically open 6 hours before the start of the practice round as per the Codeforces's policy. We are sure all will have enough time to register — the practice round will last for the whole week.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Can I use C++ in this contest?

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

    Yes, you can use C++. Please check the link in the section "The SIT STAR Contest consists of"on the contest's landing page for more details about the contest's rules.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it open to high school students? Because I can't find any rule against it

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

    Absolutely! We do not have any restrictions against high school students. However, to qualify for a scholarship, you will need to have a bachelor's degree. We still encourage you to take part in the contest!

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Why limited to "resident of Eastern Europe (including Russia), South Asia or Southeast Asia "?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    We are looking for opportunities to increase the number of participating regions in our next SIT STAR Contest. If you are interested in the SIT's master's programs, please check other scholarship opportunities here https://sit.org/admissions/#scholarship

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

      I mean, why is the residency a factor at all?

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can we just solve problems? Because I'm study at school.

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

    Yes, you can indicate in the registration form that you only want to solve the contest's problems. Kindly note you won't be eligible for an SIT scholarship as you will need a bachelor's degree to qualify.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Do we have accesses to past contests problems ?

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

    It is our first time organizing such a contest, that’s why there are no previous problems.

»
4 years ago, # |
  Vote: I like it +117 Vote: I do not like it

I'm just disappointed that nobody asked The Question.

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

What exactly does Eastern Europe include? Only Russia, Belarus, Ukraine, and Moldova?

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

    By Eastern Europe, we mean the following countries: Belarus, Bulgaria, Czechia, Hungary, Poland, Republic of Moldova, Romania, Russian Federation, Slovakia, and Ukraine. Please note that we decided to extend the geographic coverage of the SIT STAR Contest to the residents of EU/EFTA.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In typical competitive programming rounds, we are fully allowed to use the Internet — even directly copying any code which was available prior to the start of the round. Does the same policy apply in this contest as well?

I am also amazed at this very different approach for admitting students/providing scholarship compared to other universities. Hope this program continues next year as well when I graduate.

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

    At the practice round you can use what you want. The main competition on the 17th of June will be conducted as per Codeforces' rules.

    Thank you for your feedback! We are considering organizing the SIT STAR Contest next year and encourage you to take part in it this year as well.

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

Can you please add the Contest Link here so that we can enter contest easily MikeMirzayanov

»
4 years ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it

What is the world ranking of SIT?

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

    I even cannot find the wiki of the university.

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

    SIT is a private newly established university located in Schaffhausen, Switzerland. It is founded by entrepreneurs, led by scientists, and advanced by world-class researchers.

    The SIT MSc CS-SE program is an entirely new course. Joining us for the September 2020 intake would make you one of the first students to experience the program. Don't worry though, you can speak to some of our existing students, including those studying at our partner institutes. Please contact [email protected] for more details.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I filled out the contest registeration form more than 20 minutes ago, but I haven't received the confirmation email message at the email address specified in the form yet. What should I do?

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

    If u have already registered ,then go to gmail and u will see a message from noreply,there will be a 8 digit password.Remember the password and then click "our contest page",then u give your email and the password SIT institution gave u in gmail,then u will be faced to a 12 problems dashboard for practice,have a perfect preparation!!

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the information, but the problem is that I haven't received this email message yet. It is neither in the Inbox folder nor in the Spam folder of the email box.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        did u registered in mobile??Can u give me a screenshot of your gmail page??

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

          Thanks for tyring to help. I will contact the SIT team by email about this issue. I filled out the registeration from my laptop, and I have the auto-fill option of my Web Browser turned on. So, there is no chance that the e-mail address might have been mistyped.

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

            Check into All Mails or Spam folder as the same happened with me too

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

    Thanks for bringing this to our attention! We are checking internally and will get back to you asap.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

MikeMirzayanov Do we have any info as to what time of the day the contest on June 17 will begin? It's not written anywhere

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Best contest for student Great opportunity to get scholarship

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

I have registered for the contest. But still I am unable to practice on the platform through the login details provided in the mail. Please help

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

What time will the contest take place on (UTC + 7)

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

I have registered for the contest and also i have got the password but when i click the link it says that i am not a group member and also it say access denied.What can i do?

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

    Sorry for the inconvenience. Could you please dm us your email address to check internally?

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

    It's happening because probably you have auto-login enabled on codeforces. Just logout and then signIN again with your sitstar credentials that you received on your mail.

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

Where is the link to the practice contest? It should be available from 1st June.

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

    "...1st July."
    1st June

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

    You will receive the link once you register for the contest. Please note that the practice round is already on till 7th June.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I've received an email along with the password but can't log in. It says access denied. This page is unavailable during the special event. My email: [email protected]

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

        Please check your direct message inbox here on Codeforces.

»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Only div2 D problem statement was kinda confusing.remaining all problem statements are crisp and enjoyable.

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

This was not at all a good contest the time limit for Problem B was too strict and the problem statement for Problem D was literally Shit.

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Are there T-shirts?

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

    xd please reply im serious i want to farm tshirts :(

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

      No, we do not offer T-shirts. There will be other small gifts from Switzerland. The goal of the SIT STAR Contest is to promote interest in the field of Computer Science and Software Engineering and provide an opportunity to the best candidates to interview with SIT professors for a fully-funded scholarship.

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

According to the announcement, the practice contest will last for one week but at the contest page, it is showing 2 months....?

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

    Due to frequent requests, the practice round is extended until 14th June 2020.

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Was the contest postponed 1h or is it just my imagination?:))

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

    I got the same impression. It might have been an incorrect timeanddate link in the first reminder letter.

    Sad, I woke up an hour early :(

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

    The contest was not postponed, it started as planned at 8 AM UTC. Apologies for the time and date link issue. We hope you managed to join the SIT STAR Contest! Good luck!

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem L is nice, although well-known (see here for 3D-case and page 4 for specifically 2D).

First you split everything into squares:

┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐
└┘└┘└┘└┘└┘└┘└┘└┘└┘└┘
┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐
└┘└┘└┘└┘└┘└┘└┘└┘└┘└┘
┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐
└┘└┘└┘└┘└┘└┘└┘└┘└┘└┘

Then you generate random spanning tree on them and break walls between neighbours:

┌┐┌────┐┌────┐┌────┐
││└─┐┌┐││┌──┐││┌┐┌─┘
│└──┘││└┘│┌─┘└┘││└─┐
└─┐┌─┘│┌─┘└───┐│└─┐│
┌─┘└─┐│└───┐┌─┘└─┐││
└────┘└────┘└────┘└┘

It doesn't cover all possible Hamiltonian cycles, but we don't need it either, just some seemingly random is enough. To generate uniformly distributed random spanning tree, you may assign each edge random value and find the MST. Or just random shuffle all edges and do something similar to Kruskal's algo, it will do the same thing.

Problem K was also interesting. Can anybody prove that comparing $$$t_a + \max(d_a, t_b + d_b)$$$ and $$$t_b + \max(d_b, t_a + d_a)$$$ maintains total order on the dish set? It's not obviously transitive.

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

    The comparison can be reduced to the condition of sorting by decreasing $$$d_{i}$$$ if not mistaken (consider two cases).

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

    Another intuitive way than applying cases,

    Consider only $$$t_a + t_b + d_a$$$ and $$$t_a + t_b + d_b$$$, one of them is the largest among the four values that you have. Simply avoid this number. If $$$d_a > d_b$$$ put $$$a$$$ before to avoid $$$t_a + t_b + d_a$$$ otherwise $$$b$$$ must be before $$$a$$$

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

Will there be editorial published?

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

Problem K was dp right?? States are obvious but first we will have to sort on pre(t[i])+d[i]. How to solve it? My logic was to find dp (dp[i][j] = min cost to select j elements till index i) then backtrack to find elements.

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

    I had binary search on the answer + sorting with "neghboring" comparator + dp[n][k] = what is minimum total t[i] if we don't exceed answer on choose k elements among first n.

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

    If you iterate in reverse, (let $$$dp_{i,j}$$$ = min cost to select $$$j$$$ elements from $$$i$$$ to $$$n-1$$$) you can solve it in $$$\mathcal{O}(nk)$$$

    Spoiler
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Good contest, especially for beginners. Upto problem F, problems were easy. Problem G and H were somewhat interesting. Problem I and J were again easy (J was not exactly easy problem on its own, but it took only a simple search to find the solution).

Could not solve K and L, but both seem very interesting.

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

    Can you explain how to solve H and J? Thank you :)

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

      Problem H: First observe that , the answer(k) is the maximum of all f(i) , where f(i) = number of elements between [x[i] , x[i]+d) in the sorted array. You can find this first sorting the array & then using simple binary search / lower_bound in C++ vector. Assigning the frequency was somewhat tricky. To do this , iterate from left to right in the sorted array & do the frequency % k ;

      Problem J: U need to find the euler circuit of that graph. So for every edge (a,b) add the edge (b,a) also if this edge is not added already in the graph. Then apply hierholzer's algorithm to find the euler circuit of that graph.

      Sorry for my bad english.

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

      For problem J, you could just search "visit every edge twice" and you would find that the solution is to construct the adjacency list for a directed graph with edges in both directions, and then run the algorithm for finding Euler circuit in a directed graph. In short, just search effectively.

      Problem H is rather implementation heavy and a lot of details need to be taken care of. Basic idea is to sort the array in ascending order. Now for each X[i], you binary search for X[i] + d. Let pos be the index returned using lower_bound (C++), then all elements in positions [i,pos) need to be colored differently. This is still O(n^2), but can be optimised to O(n log n) by storing the index of the last colored position, and coloring only after that, as well as maintaing a set (C++) of unused colors. Once you are done processing position i, color of position i needs to be inserted back into the set.

      Hope this helps.

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

        Yes, I was able to get till the point of storing index of last colored position. But couldn't think of maintaining set to fill unused colors. Thank you :)

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

What is wrong with the following solution for the problem K?

We do binary search on answer time T. It means that every dish must be finished cooking not later than T — d_i. Here we come to standard problem: each dish(task) has duration t_i and deadline T — d_i , looks exactly like e-maxx (translation ), doesn't it?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It looks like the idea is correct (by the way, very cool solution, we didn't think about that!), but there are several bugs:

    1) The e-maxx article states that "you still need to sort these jobs by their deadline, if you want to write down the plan explicitly", but you don't do it.

    2) Sometimes you write more than $$$k$$$ orders.

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

Unfortunately, I've completely forgotten about the contest (and there were no reminder emails or something). Can I now see the statements somehow? I cannot even see the final standings because I'm not registered to the contest.

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

    There actually were some reminders, although they were sorted out as promo in my inbox.

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

      The registration confirmation letter went to my promo folder, but at the moment I don't see any other letters about it there. Maybe I just don't see it, though

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

In Problem L sample case, it says that the longest equal substrings in FRFFLFLFFRFRFFFRFFFRFFFR have lengths of 11.

The longest that I can find are two FRFFFRFFFRs which are of length 10. Is this an error or am I missing something here ?

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

    The string is cyclic, so FRFFFRFFFRF should also be OK

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

Is there a way to solve the contest for practice purposes? I cannot find a way to access the contest now since I didn't register.

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

    Unfortunately, only registered users are able to practice virtually at this time.

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

What is the minimum rank required to get shortlisted for interview ?

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

    We do not have a fixed rank required to get shortlisted for interviews but consider 8-12 as a great achievement. We are currently analyzing the results and will notify you whether you have been selected for the interview round with the professors from the Schaffhausen Institute of Technology.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It's been almost 2 weeks and still haven't heard anything. When will the results be published regarding who's been selected for interviews?

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

    Everyone will be notified by the end of this week. Thank you for your patience.

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

Still waiting.....

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

    I think they have sent emails to everyone conveying their result. If you are using Gmail, the email might have landed up in Promotions category. Similarly there is also a Focused and other messages category in Outlook. Remember to search for SIT in all mail.