Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 4 года назад, По-английски

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!

Теги sit
  • Проголосовать: нравится
  • +333
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Awesome!

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Can I use C++ in this contest?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Do we have accesses to past contests problems ?

»
4 года назад, # |
  Проголосовать: нравится +117 Проголосовать: не нравится

I'm just disappointed that nobody asked The Question.

»
4 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +50 Проголосовать: не нравится

What is the world ranking of SIT?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    I even cannot find the wiki of the university.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Best contest for student Great opportunity to get scholarship

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Are there T-shirts?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Will there be editorial published?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Still waiting.....

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.