Greetings Codeforces community!

We are excited to announce the **Constructor Open Cup 2024**, 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.

Put your knowledge and skills to the test in this 4-hour competition and stand a chance to walk away with a scholarship for a bachelor's degree in Software, Data and Technology (BSc SDT) at Constructor University, Germany’s #1 private university*!

__Constructor Open Cup timetable__

**February 1-7, 2024 | Practice Round**

Get familiar with the testing environment during this practice round.

February 8, 2024 at 2 PM (UTC) **|Main Round**

You will have 4 hours to complete a series of algorithmic programming tasks. 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 BSc SDT*
- exciting memorable gifts from Constructor University and JetBrains

*The winners who applied to the BSc SDT will receive an email to schedule the interview with Constructor University and JetBrains.

__What do participants say?__

“I was just surfing Codeforces blogs when I found a post about the Constructor Open Cup 2023. After discovering that I could have a chance to win a scholarship from JetBrains, I registered for the competition and placed among the top 20-30. The contest itself was very interesting, with different types of problems that allowed me to showcase my knowledge. I felt very honoured to receive a scholarship, and now I am one of the students in the BSc SDT program” – IMRUN, BSc SDT first-year student.

__How can I participate?__

- Register your details on the webpage.
- Finalize your registration at Codeforces using the link you receive in the confirmation email.
- If you have any further queries, please reach out to [email protected].

__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 scholarship for BSc SDT, please check Constructor University’s eligibility requirements.

**About the BSc SDT 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. 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. Constructor University aims to transcend the traditional academic approach by combining educational fundamentals with project-based pedagogy and the latest in digital tools. It equips the young professional elites with the right skills and knowledge to address today's challenges and thrive in the job market.

**About JetBrains**

JetBrains is a global software company that creates professional software development tools and advanced collaboration solutions trusted by more than 15 million users worldwide. Since 2000, we have built a product catalogue that covers all stages of the software development cycle, major technologies, programming languages, and educational processes.

The product range includes award-winning tools, such as IntelliJ IDEA, PyCharm, ReSharper, and PhpStorm, and productivity-enhancing team tools like YouTrack, TeamCity, and Datalore. JetBrains is the creator of Kotlin, the officially preferred language for Android™ development.

For more information, please visit the webpage.

The prices are really great and well thought.

Link for practice round??

As soon as you register through the Constructor Open Cup website, you will get an email with the Open Cup Codeforces page; please register there with the same email.

Practice round tasks will be available starting from February 1. Good luck! Looking forward to seeing you among the participants.

Is the codeforces round open to all or only for those registered on the website?

Practice and Final Round of the Constructor Open Cup 2024 is open for those who go through registration only. And it's not rated :)

I think there was no settings to change the password, it was very inconvenient to type a random password every time.

is this competition available to me if I'm from Russia?

It's Open Cup and everyone is welcome! The contest is open for all ages and skill levels. All you need is a passion for coding.

As one of the participants from the previous year, who had won the scholarship, I strongly recommend you to participate in this contest regardless you plan to study at the university or not. The tasks from this contest (it was earlier named as SIT Contest, actually such contests are held annually) are of high quality and will enforce your knowledge of competitive programming.

Up

I was wondering if there is any way to get access and upsolve the problemsets of the Practice & Final Round of last year's Open Cup ?

If you participated in the Consturcotr Open Cup 2023, you can still log in and upsolve the problems.

is the website of constructor open cup contest down? Because I can't access the webpage

If you mean Contestuctor Open Cup 2023, Codeforces competition page is available and you can access it only if you registered and participated last year.

If you speak about the Constructor Open Cup 2024 page, it is working.

Is this contest IOI-style or CF-style?

It is the same as the Codeforces rounds. Please, read https://codeforces.com/blog/entry/8790

Thank You

I have to do this competition during school

Nice problems in practice round.

I've already done them, and they are interesting.

Looking forward to participating in the main round.

Hope the problems can be a little harder than the practice round.

Could you help me with the H.GCD SET problem

just $$$x \cdot p_1,\; x \cdot p_2, ...$$$ where $$$p_i$$$ is th $$$i$$$-th prime.

Thank you,

I thought about this solution but how do I find primes without lookup.

In the status I saw someone submit a solution with ~~~~~ 0KB space ~~~~~

I was wondering how

I check, my solution is also $$$0$$$KB space. We just need only $$$n \leq 100$$$ primes, that's why the space is ~$$$0$$$.

did you predefine a list of first 100 primes ??

Of course no, but you can use Eratosthenes sieve for first $$$800$$$ numbers (Among them are more than $$$100$$$ primes) It still takes up extremely low memory

.

.

Yeah I a am having trouble with this one as well

I don't want to know the answer, I'm just confused on the problem itself. Can someone explain the sample

`input, outputs`

given so I can better under the problem ?I need help with problem J. Give me a hint please

Try to maintain the set of points which still consistent with the given input

Are the problem from A to L ordered in increasing level of difficulty ?

Is there any master's scholarship?

Through the Constructor Open Cup 2024, it's possible to get a chance to receive scholarships for the BSc Software Data and Technology. More details can be found at this link.

but I am in my final year in b.tech (computer science and engineering), why the hell would I do bsc, if there is any option for scholarships in msc reply me, I couldn't find it in site

There are scholarships for Master's programs here. You can put your successful participation in the Constructor Open Cup in your CV when applying, but please note that through the Open Cup, it's not possible to get a full scholarship for the master's program, as it's done for the BSc SDT program.

Can someone give me a hand with problem L in the practice round? Here's what I've tried: (if you can please give me a hint or a different approach)

SpoilerFirst of all, we can divide the vertices of each graphs in "levels" of distance to the root. Root has level 0, some vertices with level 1, some with level 2, etc.

Then I think the sequences of levels as solutions to the equation $$$x_1 + ... + x_k = n - 1$$$, where $$$x_1, ..., x_k, k \in \mathbb{Z}^+$$$. And for each $$$(x_1, ..., x_k)$$$ I found how many graphs are related to it. My problem is that there are $$$2^{n - 2}$$$ sequences and so the time is (more than) exponential.

Ive also tried to express solution using the previous values but I always end with too many sequences and exponential time. If I did not mess up with the math then $$$f(5) = 123$$$ and searching in OEIS I dont found any bijection between this problem and those sequences

I haven't solved it either, but I was able to generate the answer up to n = 6.

SpoilerMy brute force solution gave me the sequence 1, 3, 15, 123, 1743. But yeah I don't make anything of this sequence.

Could someone give me a hint with

`K. Forum.`

I've tried reversely iterating through the appended elements.

Got a TLE at test 13. I've used an array of length

`2*10^5`

.I'm thinking of priority queue or a BST with DFS.

Can someone help me with this problem ?

Could someone help me with this problem please e

Offline query and iterate over the queries from right to left.

offline query ?

Yep

Using set (for me)

Thanks for contest! I am feeling that my perfomance is like green on cf. $$$H$$$ is interesing(solved), $$$I$$$ — i have no idea. $$$K$$$ if intended solution is

not$$$O(n \cdot divisors(n))$$$, the task is not bad. If the intended solutionis$$$O(n \cdot divisors(n))$$$ — time limit is too tight and annoying(mine solution with this asymptotics is $$$TLE$$$). In any case thanks for contest! The problems were quite interesting!I passed K with $$$O(n \cdot d(n) \cdot log)$$$

It's interesing, maybe i am just weak in implementation :)

TBH my $$$O(n d(n) \log n)$$$ was killed in K, so I remove $$$\log$$$ (sort -> handwritten unordered_map with hash) and got AC

Problem I - hintAfter the first $$$k$$$ rounds, the remaining players are the $$$n-k-1$$$ strongest players, and one player from $$$[1, k+1]$$$. How can we recalculate them in each round?

SolutionMaintain the possible remaining players from $$$[1, k+1]$$$ in a set. When the protected player in the next round is fixed (call that player $$$x$$$), everything is quite simple — eliminate all players from the set which are not $$$x$$$, and also add the next player into that set if there were elements other than $$$x$$$ in that set. When the protected player in the next round is not fixed, every player remains in the set, and we add the next player.

Thanks. got it!

Can you please share your solution for H?

Mine was counting number of ways with less than or equal $$$K$$$ operations (and then find exact number by subtracting).

For solving it I use $$$dp[n][k][x]$$$. Let the last number be $$$x$$$ and the second last number be $$$y$$$ now if $$$x > y$$$ then we must make $$$x - y$$$ new operations and otherwise the number of operations doesn't increase.

But it gets WA!?

Let $$$a_1, ..., a_n$$$ be an array of non-negative numbers. Lemma: Such an array can be obtained using $$$k$$$ operations if and only if $$$|a_1| + |a_2 - a_1| + ... + |a_n - a_{n - 1}| + |a_n| \leq 2k$$$ and $$$a_1 + ... + a_n \geq k$$$ and $$$max(a_i) \leq k$$$. Let's skip the proof. Note that if $$$a_1 + ... + a_n < k$$$ then the first condition is exactly true. So we only need to count the number of arrays with the condition $$$|a_1| + |a_2 - a_1| + ... + |a_n - a_{n - 1}| + |a_n| \leq 2k$$$, and then subtract the number of arrays with the condition $$$a_1 + ... + a_n < k$$$. The last is exactly Stars and bars. The first condition can be calculated by dynamic programming. ($$$dp[n][sumOfDifferences][last]$$$). My solution is $$$O(n^4)$$$, but it is quite fast($$$300 ms$$$ on max test). I think someone has even $$$O(n^3)$$$

Is there a way we could submit solutions in practice mode?

How to solve G and H

GFor each color $$$i$$$, prepare an array $$$pos[i]$$$, where $$$pos[i][j]$$$ is the position of the $$$j$$$-th card of color $$$i$$$. Iterate on the color that will give us the result, and process it in $$$O(m)$$$, where $$$m$$$ is the number of cards of that color. There are two basic cases:

either we bring $$$k$$$ cards of color $$$i$$$ together by putting all other cards between them on top of the deck, so we are looking for the minimum value of $$$pos[i][j+k-1] - pos[i][j]$$$;

or we take several (let's say $$$x \in [0, k - 1]$$$) first cards of that color, keep them on their positions, bring $$$k-x$$$ other cards of color $$$i$$$ to the top, and then bring all cards of other colors between them and before them on top — so we are interested in the minimum value of $$$pos[i][x] - x + (k-x)$$$, or just $$$k$$$ if $$$x = 0$$$

HCalculate the number of arrays that can be obtained with $$$k$$$

or lessoperations. This can be done with the dynamic programming of the form $$$dp[i][j][x]$$$ — we considered $$$i$$$ first elements of the array, "opened" $$$j$$$ segments where we add $$$1$$$, and $$$x$$$ is the value of the last element (i. e. the number of segments that are still "opened"). In this dynamic programming, $$$j$$$ will be the minimum possible number of segments that are used. So the sum of $$$dp[n][j][x]$$$ for all $$$x$$$ will be the number of arrays such that $$$j$$$ is the minimum possible number of operations to obtain them.However, this way we count a bit more than we need, because we also count the arrays that can be obtained with less than $$$k$$$ operations, but cannot be obtained with exactly $$$k$$$ operations. These are all arrays with sum less than $$$k$$$, and they can be counted with simple combinatorics or another dynamic programming

How do you compute all the arrays with sum less than $$$k$$$ to exclude from the dp?

You can have DP[sum], and when traversing n, you will traverse possible sum and the value that you would put at this index. In short, you update DP_NEW[possible_sum+value] += DP[possible_sum]. In the end, you are interested in sum(DP[0]...DP[[k-1])

[Deleted]

This is called "hockey stick identity" (because if you highlight the corresponding elements in the Pascal triangle it will look like a hockey stick), and there is a slight modification of your argument that gives the single binomial coefficient, namely: let's say we put $$$n$$$ splitters between $$$(k-1)$$$ balls. Then $$$a_1$$$ is the number of balls before the first splitter, $$$a_2$$$ is the number of balls between splitters $$$1$$$ and $$$2$$$, and so on, $$$a_n$$$ would be the number of balls between splitters $$$(n-1)$$$ and $$$n$$$, and all other balls (probably zero) go nowhere (because we are allowed to have less than $$$k-1$$$ balls).

Or we could just convert the system $$$a_1 + \ldots + a_n \leq k-1$$$ with $$$a_i \geq 0$$$ into the system $$$a_0 + a_1 + \ldots + a_n = k - 1$$$, $$$a_i\geq 0$$$, and you have already explained how to count the solutions.

Ah I see. Thanks everyone. I think I missed the observation where an array will use $$$< k$$$ segments only when the sum is less than $$$k$$$

I can't solve K、L, when the Tutorial ~

The official editorial will be posted in about 24 hours.

Great! I am doing practice round

When the results will be published?

Results will be announced by the end of this week.

The editorial is available here.

Model solutionsABCDEFGHIJKLWill you publish sample implementations or tests?

Or can someone publish their implementation on the problem K?

Added model solutions to the comment with the editorial

Thanks :D

What was the solution for problem L. Roads from the Practice Round? I never could figure that one out.

Hint 1Try to make a tree

Hint 2We can only add an edge between two nodes in the same depth on the tree

Hint 3Now try to make an array of size $$$N-1$$$ to fill $$$d_2, \ldots, d_N$$$ where an element on that array must be $$$\ge$$$ previous element

Hint 4The number of arrays can be counted using DP

Hint 5The number of possible graph can be made can be counted using a fact that :

• the number of ways to add edges between nodes on the same depth

• the number of ways we can placed a new node into the existing tree

Full Ideahttps://hackmd.io/@fonmagnus/BJLXS-A5a