ConstructorU's blog

By ConstructorU, history, 3 weeks ago, translation, In English

Greetings Codeforces community!

CU

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
Register now!

*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.

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

The prices are really great and well thought.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Link for practice round??

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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 ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is this contest IOI-style or CF-style?

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

I have to do this competition during school

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you help me with the H.GCD SET problem

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            did you predefine a list of first 100 primes ??

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      .

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

        Yeah I a am having trouble with this one as well

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

          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 ?

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

            I need help with problem J. Give me a hint please

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

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

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

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

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Is there any master's scholarship?

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

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

Spoiler
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Spoiler
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 solution is $$$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!

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I passed K with $$$O(n \cdot d(n) \cdot log)$$$

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it
    Problem I - hint
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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!?

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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)$$$

»
13 days ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve G and H

  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it +16 Vote: I do not like it
    G
  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it
    H
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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])

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 5   Vote: I like it -7 Vote: I do not like it

        [Deleted]

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          use some formula (I don't know its name right now if anyone knows it comment below)

          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.

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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$$$

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    The official editorial will be posted in about 24 hours.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Great! I am doing practice round

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When the results will be published?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Results will be announced by the end of this week.

»
12 days ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

The editorial is available here.

Model solutions
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will you publish sample implementations or tests?

    Or can someone publish their implementation on the problem K?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Hint 5