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

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

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
  • Проголосовать: не нравится

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

Awesome!

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

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

Can I use C++ in this contest?

»
6 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

Do we have accesses to past contests problems ?

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

I'm just disappointed that nobody asked The Question.

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

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

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

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

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

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

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

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

What is the world ranking of SIT?

»
6 лет назад, скрыть # |
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?

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

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

Best contest for student Great opportunity to get scholarship

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

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

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

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

»
6 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

Are there T-shirts?

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

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

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

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

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

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

Will there be editorial published?

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

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

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

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

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

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

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

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

  • »
    »
    6 лет назад, скрыть # ^ |
    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.

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

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

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

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

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

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

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

Still waiting.....