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.
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 master-office@sit.org
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!
"the following guidelines" link in the "Who can participate?" section doesn't work it seems
Fixed. Thank you!
It is not fixed. You just need to delete the dot "." in the end of the link.
Is it rated ?
The SIT & JUB STAR Contest is not rated.
haven't received confirmation email yet, filled the registration form 5 minutes ago
UPD: Got it after 10 minutes
Have SIT obtained an accreditation yet?
Is prewritten code allowed?
It is the same as all Codeforces rounds. Please, read https://mirror.codeforces.com/blog/entry/8790
Registered 20 minutes ago — haven't received confirmation email yet...
How to solve E?
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}$$$.
Here with a bit of twist. We can store the array for each alphabet
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.
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
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.
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
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$$$
For H maintain a segtree that performs the following two operations:
Now sort the passengers by increasing $$$a_i - b_i$$$ and greedily assign them seats.
What range do we need to decrease and count the number of positive elements in? What's the intuition behind it?
What do you mean by "greedily assign them seats"?
Thanks
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.
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 theb
values (let's call thiscurr_b
) for all passengers on the bus, and the current sum of thea - b
values for those sat down (let's call thiscurr_diff
easy to update as people change position). After each stop, the happiness is justcurr_b + curr_diff
.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.
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
This is so clever, I used lazy segtrees like a mad man!
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.Hello, Great problems, Thank you! Will there be an editorial?
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 :(
I love the problemset! Thanks for the great contest experience! Will we be able to upsolve this contest (in Codeforces Gym for instance)?
How to solve L and M? For L, I tried cheesing with bitsets but doesn't work :(
For L I tried mobius transform to count each subset scares how many bandits. Looks correct, but failed at test 14. Not sure why.
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
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.
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})$$$.
I don't think my approach is the best, if there is someone better than me,please teach me.Really thanks.
How to solve G?
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
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.
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).
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.
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.
This was an excellent contest — very enjoyable problems. Thanks.
Is the difficulty of the problems too low?I feel the difficulty is close to div3.
Relatively clean solutions in rust for all problems — link
I could not participate because the mail arrived 1 hour and 30 minutes late after several attempts trying to enroll
Will we be able to upsolve the problems ? Currently "submit problem" isnt working
When will the results be published?