Hello, Codeforces!

Welcome to the think-cell Round 1 supported by think-cell, which will start on 17.02.2024 17:35 (Московское время). It will be a combined rated round for both divisions. All problems were authored and prepared by Elegia and satyam343.

We would like to thank:

• errorgorn for round coordination and help with preparation
• KAN for helping with the preparation of problems
• Alexdat2000 for Russian translation
• GoatTamer and Non-origination for discussing problems with us while our proposal was in review and testing the round.
• Kaitokid, antekb, vgtcross, riano_, mtw, AboAbdoMC, Vladithur, BERNARD, milind0110, conqueror_of_tourist, Um_nik, gamegame, htetgm, brobat, LucaLucaM, the_hyp0cr1t3, tibinyte, 18o3, ExpensiveAC, MateiKing80, udhavvarma03, Non-origination, RDDCCD, Kuroni, Brovko, LipArcanjo, andrei_boaca, nok0, oursaco, ffao, prvocislo, SmolBrain, dario2994, brunovsky, tabr, PurpleCrayon, IceKnight1093, aryanc403 and Golovanov399 for testing the round
• MikeMirzayanov for great systems Codeforces and Polygon.

You will be given $$$9$$$ problems and $$$3$$$ hours to solve them. One of the problems will be divided into two subtasks. One of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!

We hope you'll like the problemset!

UPD 1 : The score distribution is $$$500 - 1000 - 1500 - (1250 + 1000) - 2500 - 2750 - 3500 - 3500 - 5000$$$.

Congratulations to the winners!

1. cnnfls_csy

2. Geothermal

3. Benq

4. gyh20

5. Ormlis

6. jiangly

7. tourist

8. ksun48

9. Petr

10. maroonrk

Congratulations to the first solves as well!

• A : SSerxhs

• B : SSerxhs

• C : M_A

• D1 : hitonanode

• D2 : hitonanode

• E : ksun48

• F : MAOooOAM

• G : gyh20

• H : maroonrk

• I : Kapt [upsolved]

UPD 2: Editorial is out.

And now a word from our round partner – think-cell:

think-cell is the leading data visualization software for business presentations. Our mission is to offer the most intuitive user interface for generating complex data-driven charts and slides, while at the same time ensuring seamless integration with Microsoft Office. We work on challenging visualization problems, reverse-engineer Microsoft’s code, and reinvent how slides are created. think-cell is the only German company funding the C++ ISO committee delegation, so there is a good chance that components we invent will find their way into the standard.

Right now, we are looking for smart, creative C++ engineers with a solid theoretical background to join our engineering team.

Highlights of the role:

• We use the latest C++ features as soon as the compilers support them.
• We’re not afraid of advanced template metaprogramming or macros when they avoid code duplication or lead to cleaner, more readable code.
• We prefer algorithms and ranges (esp. ours!) over raw loops.
• We take the time to deliver perfect code.
• We love refactoring and modernizing old code and introducing our own libraries.
• If we can do better than the standard library, we write our own!
• If we have done something cool, we talk about it at C++ conferences.
• If we are missing a C++ language feature, we write a proposal and present it to the C++ standard committee.

Here is what we offer:

• A competitive salary from the start and a raise to EUR 130,000 annually after only one year.
• Full support with relocation to Berlin or the option to work fully remotely.
• An apartment for the first month if relocating to Berlin.
• Lifestyle-friendly working hours, no deadlines, no overtime.
• No scheduled meetings.
• An international team of brilliant minds.
• A flat organisation with respectful colleagues and plenty of room for your ideas.
• A working environment that is driven by the strive for excellence.

Already convinced?

P.S. don't forget to check out our developer blog to learn more about our commitment to the tech world!

Join think-cell Round 1 that will start on 17.02.2024 17:35 (Московское время) for a chance to challenge your skills among other developers and win the following prizes.

- First place: Apple iPad Air (10.9-inch iPad Air Wi-Fi 256GB),
- Second and Third place: Apple Watch (Apple Watch Series 9 GPS + Cellular, 41mm Aluminum Case with Solo Loop),
- 4-50 places: think-cell branded socks
- 200 additional socks will be distributed randomly among the rest of the participants who solved at least one problem and for whom this is not the first rated round!

Thank you, think-cell, for sponsoring the Standard C++ Foundation and challenging our Microsoft compiler team with complex C++ code.

Herb Sutter, President of the Standard C++ Foundation

think-cell is a fast-paced software company in Berlin, Germany, with a focus on developing graphics products that stand out from the crowd. More than 1,000,000 users world-wide rely on our software for their daily business as it makes creating graphical presentations so much easier, faster and more enjoyable. Among our customers are many renowned consulting companies and large international corporations.

We do not have to make compromises with regard to code quality and beauty, because think-cell is highly profitable. We are willing to go the extra mile of developing sophisticated algorithms and refining our user interface, and we are proud of our many happy customers. The fact that the company is owned and managed by seasoned computer scientists certainly contributes to a working environment that makes exceptional developers come and stay.

About our software

Our focus is on business slides (as opposed to more artful, open-ended applications) because they offer great potential for automation of the layout tasks traditionally performed by PowerPoint users themselves. There are plenty of challenges, from a solid understanding of what makes a good layout, to algorithms that produce an aesthetically pleasing output fast enough for interactive slide design, to an intuitive and unobtrusive graphical user interface that supports our original approach to slide layout, to solid technical solutions for automatic bug reporting and updates, to compatibility with third-party software on the computers of over a million users.

Here are some highlights of what we have done.

Language

• Everything we do is C++. Even our customer portal is written in C++. There is some Assembler glue code where necessary, and our build scripts are written in Python, but other than that, think-cell is all about C++.
• We closely track the latest versions of our compilers, Visual C++ and Xcode, so we can always use the latest C++ standard features as soon as they become available.
• We fund the working group for programming languages of the German Institute for Standardization (DIN). Some of our employees are members of this committee and vote in the ISO/IEC C++ international standardization process.
• We sponsor the Standard C++ Foundation, helping them to promote the understanding and use of modern Standard C++ on all compilers and platforms.

Library

• We use Boost throughout our code, e.g., Boost.Spirit for parsing.
• We have our own range library, in the same spirit as Boost.Range or Eric Niebler’s range-v3, but we go further, for example, by unifying internal and external iteration. We gave a talk about it, and most of the code is public.
• We develop our own cross-platform library to support Mac and Windows with a single code base.
• We have our own reference-counting and persistence libraries to save and restore whole object trees.
• We have an extensive bug-reporting infrastructure. Assertions and error checks stay in the release code, and our software automatically reports bugs to our server. The server analyzes the bug, categorizes it and files it in a database that all developers can access. If an update fixes the bug, the user can download the update directly from a bug response web page.

Algorithms

• think-cell was founded on the idea of an algorithm for automatic slide layout, and we are still on an exciting journey towards that ambitious vision. You can see our most recent release in action!
• We developed a new algorithm for automatic point cloud labeling that allows labels to be positioned away from the actual points.
• We developed a new algorithm for automatic column chart labeling.
• We are working with John Forrest – author of the linear solver CLP – to make his simplex code faster for our kinds of problems.
• We developed many generic data structures that are not in C++ or Boost, such as partitions.
• Our software not only produces charts, it can also read them off print and digital images. For our chart recognition tool, we rely on OpenCV and the Leptonica Image Processing Library.

Reverse engineering

• We do lots of reverse engineering with the disassembler IDA from Hex-Rays to achieve things that are not possible through the documented Microsoft Office API.
• We have probably written the best function-hooking engine out there. Each time out software starts, we patch the Microsoft Office executables in memory. Rather than hard-coding patch addresses, we search for small chunks of assembly code to protect against minor changes in the executables.

Watch our CTO Arno answering FAQs

Arno Schoedl (think-cell founder & CTO) and Volker Schöch (Senior Software Developer) answer frequently asked questions about applying and working at think-cell as a C++ developer.

About this job

We are looking for smart, creative developers with a solid theoretical background. Our team’s backgrounds range from 15+ years of commercial experience in various fields to fresh graduates in Computer Science, Physics and Mathematics. A university degree or work experience with C++, in combination with a fresh and creative problem-solving approach, would be ideal for this role. As all our recruitment steps are task-based, the selection is based on the skills demonstrated during our tests.

You will mostly work independently and will be responsible for the whole range of tasks involved in implementing a new feature. You should be able to look at a problem from the user's perspective and discuss abstract concepts with fellow developers. We expect each of our developers to do architecture, design, implementation, customer feedback and bug fixing, rather than splitting these activities between several people. We thus put everyone in control of their own work.

At think-cell, there are no deadlines or scheduled meetings. A feature is ready to be released when you are convinced that you have implemented the best possible solution. Meetings take place as needed, and only the people actually involved in the topic are required to attend. At any time in the process, ideas, suggestions and criticism from anybody in the hierarchy are welcome and are seriously considered. We want to hear your ideas, even if they mean that we have to change a lot of code to make things better.

We have published several scientific articles in the areas of artificial intelligence and computer graphics, and we will encourage you to do the same. We sponsor visits to conferences and have close relationships with universities and research institutes across the U.S. and Germany.

think-cell encourages a healthy work-life balance. We do not work at night or on weekends.

We pay very competitive salaries and offer our developers EUR 130,000 annually after one year of employment. If necessary, we will go out of our way to help you relocate to Berlin, and we will do what we can to help you acquire a work permit. You should be able to communicate effectively in English. Knowing German is not required, but we will arrange and cover to costs of German lessons, if desired.

Join us as a C++ developer

Location: Berlin, Germany or remote

Do you believe in beauty when it comes to programming? Do you have a vivid interest in elegant algorithms? Are you fluent in C++? If so, we would like to meet you. Here is what we offer in a nutshell:

• A wide array of extremely challenging C++ development tasks
• An international team of brilliant minds
• A working environment that makes this team stay and grow
• Enough time to make sure that every detail of your solution is perfect
• A flat organization and plenty of room for your ideas
• No scheduled meetings
• Family-friendly working hours, no deadlines, no overtime
• Support for relocation
• A competitive salary from the start and a raise to EUR 130,000 annually after only one year