ConstructorU's blog

SIT & JUB STAR Contest 2022
By ConstructorU, history, 2 years ago, translation, In English
SIT

Hello, Codeforces!

We are thrilled to announce the dates of our annual online programming competition, the SIT & JUB STAR Contest 2022, organized by the Schaffhausen Institute of Technology (SIT) in Switzerland and our partner Jacobs University Bremen (JUB) in Germany.

Winners will have the chance to receive exciting prizes, including a full scholarship for Master in Computer Science and Software Engineering program.

What is the SIT & JUB STAR Contest?

The goal of the SIT & JUB STAR Contest is to promote interest in the field of Computer Science and Software Engineering, giving participants an opportunity to demonstrate their knowledge of programming. It is also a winning ticket for full scholarship to a master program. To participate, click here.

The SIT & JUB STAR Contest 2022 timetable

April 16 15:00 (UTC), 2022 | Practice Round: An opportunity to familiarize yourself with the testing environment. You can practice any time from April 16 to 5 minutes before the Final Round. This is an optional step but we highly recommend taking part in it. The results of this round will not affect your final score.

April 26 08:00 (UTC), 2022 | SIT & JUB STAR Contest: The contest starts at 8 am, UTC, on April 26. You have 4 hours to complete all requested tasks, which include 8 to 12 problems of various levels of difficulty in algorithmic programming.

DATES | Interview Round and Winner Announcements: Participants with the highest scores will be invited for the interview round with professors from SIT and Jacobs University Bremen. Winners will be notified by email.

Apply Now→

Prizes

Several prizes are offered to the top candidates:

  • Full scholarships for the Master in Computer Science and Software Engineer program offered in Switzerland and Germany
  • Other scholarship options available
  • Some exciting gifts from Switzerland and Germany!

Who can participate?

Everyone is welcome! The contest is open for all ages and skill levels, all you need is a passion for coding.

To be eligible to win the full scholarship, please consult the following guidelines.

How can I participate?

  • Fill out the contest registration form here.
  • 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]

About the Master in Computer Science and Software Engineering

Our 2-year hybrid Master in Computer Science and Software Engineer brings the latest must-knows in science, tech and business, through lively lectures by renowned field leaders and hands-on lab activities. With this program, go from studying in Schaffhausen in Switzerland, known for its excellence in IT science and technology, to Bremen in Germany, a vibrant campus for English-speaking students, with a rich academic tradition. Click here to learn more.

About SIT and Jacobs University Bremen

SIT is a global institution dedicated to promoting Science, Education and Technology. Headquartered in Schaffhausen, Switzerland, SIT is a growing ecosystem comprised of a non-profit component, with education and research, as well as commercial technology spin-offs, consulting services, a start-up incubator and investment funds.

Thanks to its two English-language campuses – in Bremen, Germany and in Schaffhausen, Switzerland – SIT offers interdisciplinary university programs to students from around the globe with flexible learning models. With a research-centric approach and an entrepreneurial mentality at its core, the SIT education ecosystem is a gateway to the next generation of digital leaders.

We look forward to seeing you show off your programming skills on competition day.

Good luck!

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

Comments Comments (58)
| Write comment?
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

"the following guidelines" link in the "Who can participate?" section doesn't work it seems

→ Reply
»
2 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Is it rated ?

→ Reply
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

haven't received confirmation email yet, filled the registration form 5 minutes ago

→ Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Have SIT obtained an accreditation yet?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated??

→ Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Is prewritten code allowed?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Registered 20 minutes ago — haven't received confirmation email yet...

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    For every pair of rows $$$(i, j)$$$ compute the number of rows $$$k$$$ such that $$$a[i][k] = a[j][k] = ch$$$ separately for every letter $$$ch$$$. Then the answer is the sum $$$\binom{cnt}{2}$$$.

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

    Here with a bit of twist. We can store the array for each alphabet

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J? I spent quite some time but couldn't come up with anything fast enough. Turned out H was much easier for me.

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

    How to solve H ?

    For J, define $$$len[u]$$$ is the longest step we can take from $$$u$$$ to leaf node by moving down (that is $$$len[leaf] = 1$$$ and $$$len[nonLeaf] = max(len[v_1], len[v_2], ..., len[v_k]) + 1$$$ for $$$v_i$$$ are children of $$$u$$$

    Observe that to pick a node we choose to teleport, we can pick any unmarked node $$$u$$$ with maximum $$$len[u]$$$ and move all the way down to its child to the leaf (obviously we need to move to a child with the largest $$$len$$$). And after taking down, simply mark all of its path to the leaf. Do this for each teleportation

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      For H, consider the value a-b instead. You want to maximise sum of (a-b) of the best m people in the bus. You can use a fenwick tree to maintain it.

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

        I actually use a different idea and get wrong answer (but not sure why)

        Here's my idea :

        • Maintain the people inside the bus (e.g. we can use data structure such as set)

        • Each time a new people enter a bus, I check : If that person is better sitting ($$$a_i > b_i$$$), then I put this person to the seat, otherwise I put that person to standing

        • If at some point our seat size is larger than $$$m$$$, we remove them with the most $$$a_i - b_i$$$ (to minimize the "loss")

        • If at some point our seat size is smaller than $$$m$$$, then some standing person might be able to fill the seat. I pick those with the most $$$b_i - a_i$$$ (because this will improve our score) except when the difference of them is $$$< 0$$$ it's better to make that person to keep standing

        I got WA on test 19, not sure if I had the wrong idea or implementation

        Here's my code Code

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

      The problem can be simplified to summing standing bonus for everyone and maintain a set of biggest at most $$$m$$$ $$$sit-stand$$$ bonus where $$$sit > stand$$$

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

      For H maintain a segtree that performs the following two operations:

      • Decrease all elements in a range by -1
      • Count the number of positive elements in a range

      Now sort the passengers by increasing $$$a_i - b_i$$$ and greedily assign them seats.

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

        1. What range do we need to decrease and count the number of positive elements in? What's the intuition behind it?

        2. What do you mean by "greedily assign them seats"?

        Thanks

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

        I think we can solve this without any segment tree, we can just use TreeSet. I maintained two sets, one for passengers who are already seated and one for passengers who are waiting for their seats. (Only passengers who have a>b, will be on this list). Initially when passenger boards in bus, either he will be standing or in a waiting queue. And if a person is leaving the bus we will just check whether the above person was standing or in waiting or was seating, based on the state we will remove the happiness from our current happiness. In the end, we will try to optimally arrange seats, if there are empty seats then we will allot seats to the waiting passenger according to the priority of (a-b), till we have no remaining seats. And also we may also want to remove some already seated person and give it to some waiting people. based on the value of a-b.

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

      Here is an implementation of H using only multisets, no Fenwick/Segment Trees.

      You want M greatest (positive) values of a - b to be sat down — simply keep multisets of these values for who is stood up and who is sat down, at each stop add and remove the relevant people, and then fix the multisets so that they once again represent the desired groups of people. Also maintain the current sum of the b values (let's call this curr_b) for all passengers on the bus, and the current sum of the a - b values for those sat down (let's call this curr_diff easy to update as people change position). After each stop, the happiness is just curr_b + curr_diff.

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

    Starting from the leaf with the deepest depth, mark all nodes as visited as you go up, until you reach another visited node, then store the number of nodes as a path. Do it from deepest to shallowest.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    For each vertex calculate longest path from it to some leaf and to which vertex you should go to achieve this. Now let's have a heap, initially with only vertex 1, where vertex at the top has longest path. On each step we take vertex from the heap, go through the path and add all adjacent vertices to the vertices on the path that are not themselves on the path. When heap is empty we pad answer with ns

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      This is so clever, I used lazy segtrees like a mad man!

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

      I did this too. Here is my implementation of J in this exact way if anyone wants to look while the contest solutions appear to be hidden. Note that I store for each vertex a "best child" in array b since that allows me to marked the used vertices really easily, and ignore them thereafter in the priority queue.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, Great problems, Thank you! Will there be an editorial?

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I wonder whether there is a place to judge my code after the contest? I passed the sample just five minutes after the contest finished, only found out that I can't submit it :(

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I love the problemset! Thanks for the great contest experience! Will we be able to upsolve this contest (in Codeforces Gym for instance)?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve L and M? For L, I tried cheesing with bitsets but doesn't work :(

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

    For L I tried mobius transform to count each subset scares how many bandits. Looks correct, but failed at test 14. Not sure why.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 11   Vote: I like it +8 Vote: I do not like it

    For L fix the hero you're going to use then iterate over multiples of $$$t_i$$$ for that hero, for each bandit in that hero's way get a mask of other heroes such that those heroes' $$$t_j$$$ don't divide this bandit's position all submasks of this mask can't be considered so to check if a mask can be considered you just need to use SOS DP.

    For M binary search the answer and solve it in a backwards manner starting from any index this way you need to check that you will arrive at index $$$i$$$ in $$$answer - t_i$$$.

    You can use $$$DP[L][R][Side]$$$ where $$$DP[L][R][Left] = min(DP[L+1][R][Left] + cost(L,L+1), DP[L+1][R][right] + cost(L,R))$$$ and same for right.

    This way

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    For M have a dynamic programming with state "what smallest time I can finish task i and still need to finish all tasks from i (not including) to j (including)." You start with dp[0, n — 1] = max(t[0], abs(x[0])) and dp[n — 1, 0] = max(t[n — 1], abs(x[n — 1])) and from dp[i, j] you can go to either dp[i +- 1, j] or dp[j, i +- 1] (where + or — before one depends on direction from i to j). Answer then min dp[i, i] for all i.

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

    For L I enumerate a hero i to deliver the treasure and enumerate all possibilities of the heroes who scare bandits in $$$O(2^{m-1})$$$.Now we need to count how many bandits on the i-th hero's path will be scared away in this state.We can use the principle of inclusion and exclusion to calculate.So the final time complexity is $$$O(m^2\times2^{m-1})$$$.

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

      I don't think my approach is the best, if there is someone better than me,please teach me.Really thanks.

      → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it -7 Vote: I do not like it

    I use segment tree. We know that if we have solved $$$x$$$ number of problems, it means we can pick any unsolved problem with the least amount of time from $$$[1, 2x+1]$$$

    After we pick the optimal problem, we can update the segment tree point (e.g. the problem time) to infinity (so we make sure to not pick it again since it's been solved)

    I think heap is possible as well to solve this

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    keep a priority queue. Each round, push in next two problems, and pop one with min time. Count the sum until reach tot time. That makes it always satisfy the request.

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

    Priority queue is also fine. Here is my implementation.

    Basically every time you solve a problem, you can add two more to the PQ (until you've added everything). If you can't solve any problems, you have to exit. If you can, it's obviously advantageous to solve the shortest allowed problem (hence the PQ).

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

    Just maintain a priority queue of eligible subjects(it basically represents the exams that you haven't taken till now but you can take them at any time). let's say we have taken count exams till now then we can add the ith exam to the above priority queue only if(i-(count+1)<=count+1). If we can't add the curr subject to the queue, then we have to pick a minimum duration subject exam from the queue. Do this till you have some remaining time.

    → Reply
»
2 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Unfortunately, the full editorial is not ready by this moment. You can access the partial editorial here (missing problems: I, J, M). We will post the full editorial as soon as it's ready.

Thank you for participation! We hope you enjoyed solving the problems.

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

    This was an excellent contest — very enjoyable problems. Thanks.

    → Reply
»
2 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Is the difficulty of the problems too low?I feel the difficulty is close to div3.

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Relatively clean solutions in rust for all problems — link

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

I could not participate because the mail arrived 1 hour and 30 minutes late after several attempts trying to enroll

→ Reply
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Will we be able to upsolve the problems ? Currently "submit problem" isnt working

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When will the results be published?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone get any prizes , or was anyone contacted ?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are deeply sorry for such an intransparent situation with the gifts and for not contacting you sooner. We could not finish sending out gifts for the contest prizewinners, and we had to cancel a lot of parcels because of the global rebranding of the university. It was unclear till the last moment if we could send out old merchandise, so it took a lot of time to clear the procedure. We want to make it up to you and will contact you to clarify the postal details once again.

    We will prepare parcels along with the presents for Constructor Open Cup 2023 future winners. We apologize again and want to ensure everyone gets their present from us.

    → Reply