Greetings Codeforces community!
We are excited to announce the Constructor Open Cup 2023, our annual online programming competition organized by Constructor University and JetBrains.
What is the Constructor Open Cup 2023?
Constructor Open Cup is an online contest organized by Constructor University and JetBrains, the global leading tool provider for developers, to promote interest in computer science, data science, software development, and software engineering. You'll have to race against the clock to solve real-life programming challenges.
Put your knowledge and skills to the test in this 4-hour competition and stand a chance to walk away with a scholarship for the Bachelor's degree in Data Science and Software Development at Constructor University, Germany’s #1 private university*!
Constructor Open Cup timetable
- March 23-29, 2023 | Practice Round
Get familiar with the testing environment during this practice round. We highly recommend this optional step. Don’t worry: it won’t affect your final score!
- March 30, 2023 at 2 PM (UTC) | Main Round
You will have 4 hours to complete a series of algorithmic programming tasks of various difficulty levels.
Registration closes 1 hour before the start of the contest.
Prizes and Winner Announcement
The top candidates will receive exciting prizes, including:
- Chance to get scholarships for the Bachelor’s degree in Data Science and Software Development*
- Exciting memorable gifts from Constructor University and JetBrains
We're looking forward to seeing your programming skills on competition day, and we wish you the best of luck.
*The winners who applied to the BSc program in Data Science and Software Development will receive an email to schedule the interview with Constructor University professors and JetBrains.
Can I participate?
Everyone is welcome! The contest is open for all ages and skill levels, all you need is a passion for coding.
To get the chance for the JetBrains scholarship for Data Science and Software Development program, please check Constructor University’s eligibility requirements.
How can I participate?
- Register your details here.
- Register at Codeforces using the Login/Password you receive in the confirmation email.
- If you have any further queries, please reach out to [email protected].
Why should I join the Constructor Open Cup?
Previously known as ‘STAR Contest’, the competition attracted more than 1,600 contestants across 82 countries over the past three years. Renamed to Constructor Open Cup in 2023, this contest welcomes all regardless of age, qualifications, or skill level.
By participating in the Constructor Open Cup, you will:
- Get recognized by top science and technology leaders
- Pit your algorithmic problem-solving skills against competitors from other countries
- Get a chance to get a full scholarship for BSc program in Data Science and Software Development
Don't miss out on this exciting opportunity to challenge yourself and showcase your talents. Join the Constructor Open Cup today!
About the BSc Data Science and Software Development program
This program prepares talents to become tomorrow’s elites in software development, programming languages, data analysis, and machine learning. You will benefit from the latest insights and knowledge from top industry partners and get the right skills needed for these rapidly changing industries. Through real-world projects, the practice of the latest technologies, and the close mentoring of industry experts, you will gain a unique experience that sets you up for successful career opportunities. Learn more about the program here.
About Constructor University
Founded in 2001 as a private, English-language campus university, it repeatedly achieves top results in national and international university rankings. Its more than 1,600 students come from over 110 countries, and around 80 percent have moved to Germany to study. Research projects at the University are funded by the German Research Foundation, the European Union's Framework Program for Research and Innovation, and global leading companies.
About JetBrains
JetBrains creates intelligent software development tools used by over 15.9 million professionals and 90 Fortune Global Top100 companies. Its lineup of more than 30 products includes IDEs for most programming languages and technologies, such as IntelliJ IDEA, PyCharm, and others, as well as products for team collaboration, like JetBrains Space. JetBrains is also known for creating the Kotlin programming language, recognized by Google as the preferred language for Android development. The company is headquartered in Prague, Czech Republic, and has offices throughout the world. For more information, please visit https://www.jetbrains.com/
Why do I need to enter my name and phone number to register?
As well as exactly one citizenship and exactly one education level among "High School Student", "University Student" and "Already Graduated". Seems like it's aimed at admissions only: secondary school students and high school graduates are either excluded or forced to provide inaccurate information.
Is this the same contest as SIT & JUB STAR Contest 2022? It's been almost 1 year since I've been told that I would get a reward for it but there weren't any news.
ConstructorU, Is the contest rated (if held on codeforces)?
No, it is held in another subdomain(https://constructor2023.contest.codeforces.com/) of codeforces. Hope we can also practice in gym after the contest is end. And provide editorial please.
How to see practice round ?
I can't find the rules. Is it allowed to use prewritten code? Will it be ok to post a screencast of my participation on YouTube after the end of the contest?
The contest rules about third-party code are the same as on regular Codeforces rounds, read https://codeforces.net/blog/entry/8790.
We kindly ask you not to publish the screencast on YouTube. These problems may be used in the educational process in the future.
After the contest, an editorial will be published for all the participants in the Codeforces group blog and you may discuss the problems in the comments.
Are we allowed to discuss the problems here?
Sure!
Is there a tutorial for today's contest ?
Yes, it will be published on the Constructor Open Cup 2023 page tomorrow or Saturday. Please stay connected.
Where the result will be published ?
Solved A-K, got 7th place in the contest.
Difficulty (by my feeling): A-B --> d2A, C-E --> d2B, F-G --> d2C, H-I --> d2D, J-K --> d2E
Maybe L can be solved by listing all partitions of numbers not greater than 45 (there are at most 540635 different partitions accroding to OEIS — A000041 ), but I can only come up with O(m*(A000041[r_max])^2) solution.
How to solve I ?
Binary search + greedy
I can't see the greedy approach
Hello. About today's contest's problem L:
I think there are less than $$$432894$$$ states. So for each query we can create a graph where for each state there's a node. Set answers for all of the previous states that are valid(i.e. their sum is $$$r_{prev}$$$). now run bfs. After doing this for all of the queries, just select the best answer from valid nodes. Our algorithm ensures that if the final node is valid, then all previous states are valid too. This will run in $$$O(m*432894*C)$$$ where C is the complexity for transforming a state to an int value(to assing it to a node later). If C comes from a very fast hash table, this might fit in the TL.
EDIT: oops, the number of edges is much greater than 432894(smth like 6493410)
To obtain a solution in $$$O(m \cdot P)$$$, where $$$P$$$ is the number of partitions, when moving from the $$$i$$$-th layer of dynamic programming to the $$$(i+1)$$$-th one, we can build a tree where vertices represent different partitions, and the parent of a vertex is the partition we get by discarding the topmost plate. Then, $$$dp_{i+1,j}$$$ is equal to the minimum value of $$$dp_{i,k} + dist(k,j)$$$, where $$$dist$$$ represents the distance in the tree. We can calculate it for all partitions with tree dynamic programming in two steps: in the first step, we traverse the tree and "pull" the values up the tree, and in the second step, we "push" the values down the tree.
You can also try some shortest paths algorithms on this tree, but most of them are too slow.
I think you underestimate the difficulties of harder problems. Problem F is basically 1190C - Tokitsukaze и дуэль , which is 2300 and d1C.
They are completely different problems
I guess the main idea of F and 1190C is the same, but implementing that idea in 1190 is way harder. So I don't think F is that difficult.
The problem K, both practice and contest problem, are very nice graph problem. I recommend everyone to practice these two problems if you have time. Very beautiful.
My contest result, passed 10/13, waste a lot of time on problem I and G, if not, probably I can finish J.
Difficulty estimate: A:800, B:800, C:1100, D:1000, E:1100, F: 1500, G:1600, H:1700, I:2200, J:2400, K:2100, L>2500, M>2500.
Really good contest, thanks for it. It's a shame for me to solve only 8 problems out of 12, spent too much time on F (just stupid mistake took time to fix it) and C (I thought that "several" means 2 or more:)).
By the way, how to solve I, L and K?
yeah me too I thought "several" means 2 or more it costs me 3 WA
I: binary search on the answer. Create another array with updated $$$a_i$$$. Now it's always optimal for each ride to carry as many people from the suffix as possible
K: for k=1 the answer is obvious.
for k=3 we can always get answer=0 with only 3 colors: for each connected component color its nodes in two colors, but if there is a node that it has a neighbour with the same color, change the color of this node to 3. there may be only one cycle in the component, so this is always correct.
for k=2, for each component find the cycle. if there is no cycle, color the component in two colors the usual way. Otherwise, find the pair of adjacent nodes in the cycle with the lowest cost if they are in the same component. Color them in color 1, and color all other nodes starting from these two.
I forced push all the edges into a heap and check each of them in order, passed in 800ms …
I don't have a chance but I am still interested. How many people get a scholarship?
Seems like you got not bad place (I came even lower) and still have chances (there are many people who didn't come to get scholarship), hope never dies:). Anyway, you can also try passing programming test (see "Financing" page at their website).
How do you know his place, and how do you know that he still has chances?
There are many people who participate here every year. Yes, maybe, someone decided to get scholarship, but I don't think that there are many of these people. So I think that there are still chances even with 80th place (you can also see the website of contest, "What the participants are saying" and one guy wrote that he received scholarship with "getting about 70th place").
About place — there is name and surname in Codeforces profile, knowing name, you can see the place.
Thanks for info!
Can H be done by greedy? or is DP the only way?
I think DP, and don't believe it can be solved by greede(but i can be wrong). Am i true that you mean DP on masks? (all subsets of last 7 numbers)
yes, I solved it with masks but I was confused to how many people solved it.
ConstructorU how many of top participants receive gifts? The top 100? Top 50? Top 10?
The amount of upvotes means a lot :)
Top 103 (everyone with >= 8 tasks)? It would be really nice if they decide to do in that way
Highly doubt that. I think maybe top20 contestants will have a change for scolarship
I said about "Exciting memorable gifts from Constructor University and JetBrains". But yes, I highly doubt too
Sorry. For gifts my predictions are top50
.
When will the announcement about winners be made?
We will try to do it in the upcoming days, but there are Easter holidays around the corner, so if it is not this week, then at the beginning of the next week!
Seems like they sent e-mails to potential winners of scholarship (they invite to interview).
Did they send it to everyone? I did pretty bad imo, I still got the mail
Hello, I asked a question regarding the scholarships(on your email) 5 days ago. When should I expect an answer?