[Tutorial] Cartesian tree and some related problems The Cartesian Tree is a useful concept for solving some problems which revolve mainly about thinking of the range of maximality of elements. It also provides a sort of "persistance" to the algorithm of monotonic stack, if you will. In this blog, we will learn what a Cartesian Tree is, how to construct one and solve some related problems to strengthen our understanding. Let's begin! <hr> #### What is a Cartesian Tree? Let's consider an array $a$ where all values are distinct. The Cartesian Tree for the array $a$ is a binary labeled tree build recursively from the function $get(l,r)$ which constructs our desired tree from the subarray $l...r$. Now let's define $get(l,r)$ - First root the tree at index $i$ such that $a_i = min(a_l,a_{l+1},...,a_r)$. Note that because all values are distinct, $i$ will always be unique. - The aforementioned index will become the root of the Cartesian Tree. It's left and right subtrees will be recursively generated by $get(l,i-1)$ and $get(...

Full text and comments »

Wunder Fund Round 2016 Editorials I hope you enjoyed the contest! Let me know if you find any errors below. Thanks for participating. Short solutions: - Slime Combining: You can just do what's described in the statement. Or, maybe you can do something with the binary representation of the number. - Guess the permutation: Find out where 1 should go. Then, find out where 2 should go, and so on. - Constellation: Start with a triangle and break it up. Or, choose a point and look at angles. Or, sort by x coordinate. - Hamiltonian Spanning Tree: Two cases: X > Y and X <= Y. For X > Y we can almost always avoid the spanning tree edges. For X <= Y we can do something greedy. - Robot Arm: Make a segment tree on segments. A segment is basically just a linear transformation, which can be described with three numbers. - Double Knapsack: Make the problem harder. Let's say I want a consecutive sublist of both lists that have equal sums. Then use pigeonhole principle to get an answer. - Combining Slimes: Use conditional e...

Full text and comments »

UTPC April Fool's Contest 2026 Editorial The [prophecy](https://codeforces.me/blog/entry/127899) is true: "Hopefully we will have many more years :)" [A &mdash; Captcha](https://codeforces.me/gym/106452/problem/A) Author: [user:m7a1g5i8k8a1r4p0,2026-04-02] <spoiler summary="Solution"> Just print the number of circles in the image. There are `7` if you include the circles in `i` and `?`. </spoiler> <spoiler summary="Feedback"> - Best Problem Ever - Incredible Problem - Amazing Problem - Great Problem - Good Problem </spoiler> [B &mdash; Right or Wrong?](https://codeforces.me/gym/106452/problem/B) Author: [user:m7a1g5i8k8a1r4p0,2026-04-02] <spoiler summary="Solution"> The title implies that you should check if the 3 numbers are "right" or not. You can do this by checking that $a$, $b$, and $c$ form the side lengths of a right triangle, with $c$ as the hypotenuse. </spoiler> <spoiler summary="Feedback"> - Best Prob...

Full text and comments »

Solutions to Codeforces Beta Round #32, A, B, C, D A. Reconnaissance The solution to this problem is straightforward. As it is stressed that (i,j) and (j,i) are different, we can adopt a nested-2-loop to enumerate all the feasible combination of i and j, and check whether the difference of height satisfy the condition or not. B. Borze The problem is simplified since it is guaranteed that the given sequence is valid Borze code. We can enumerate the letters from the first one, and implement the decoding according to the following rules: Rule 1): whenever we meet a '.', decode it as "0" and move to the next letter; Rule 2): whenever we meet a '-' and the next one is '-' as well, decode it as "2" and skip the next letter and move directly to the one following it; Rule 3): whenever we meet a '-' and the next one is '.' as well, decode it as "1" and skip the next letter and move directly to the one following it; C. Flea Note that at first the flea is at the center of the cell, and no matter how it jumps later, it sho...

Full text and comments »

I got tired of forgetting who my friends were on CF, so I built a tool to fix it. Hey Codeforces, A few months ago, I realised I had a really annoying problem. I was scrolling through the standings after a round, trying to see how my batchmates and a few seniors did, and I completely blanked on half their handles. Between keeping track of college friends, study groups, and a few friendly rivals across CF, AtCoder, and LeetCode, it was getting impossible to remember who was _xX_dragon_slayer_99_Xx_ and who was _math_wizard_007_. I was basically keeping a mental spreadsheet just to figure out who to discuss problems with. I couldn't find a good existing solution, so I decided to just build one for myself. It’s a Chrome extension called **Constellation**. Initially, I just built it to do one thing: swap out cryptic handles with real names right on the page. But as I kept using it, I kept adding little features that I found myself wishing I had during my own contest prep. I’ve been using it for a while now, and it’s honestly been such a massive quality-of...

Full text and comments »

Variation of Boomerang Constellations ( Hackercup qualification round problem) [From the problem statement](https://www.facebook.com/hackercup/problem/910374079035613/) ( Contest is over) ~~~~~ Two boomerang constellations are distinct if they are not made up of the same unordered pair of line segments ~~~~~ What does above mean? _How to solve this problem if the restriction is changed to "if they are made up of same Ordered pair of the line segment" **instead of "unordered"** ( without hashmap to keep track that we have see it earlier ) ?_

Full text and comments »

2012 ICPC Kanpur Problem | CONSTELLATIONS Can anyone help me to solve this problem [CONSTELLATIONS](https://icpcarchive.ecs.baylor.edu/external/62/6290.pdf) Thanks

Full text and comments »

☆Welcome to my BLOG❤This is my first artical☆ I've been trying to create my own blog for a long time,and I'm going to share my opinions about some problems on Codeforces.This blog is kind of the Minute Book of every step on my trip of solving programming problems;and I want to intruduce myself first: My Name: GTJ→Garfield Tuzki Jacihociyl Nationality: China Sex: Male(it should be boy...) Age: 13 Constellation: Libra Grade: Grade 2 in middle school(Grade seven) Birthday: 19th of Oct. in 2000 Blood Type: B Religion: Buddhism(but I still eat meat...) What Do I Like: Tuzki,Magic Trick,Interesting Problems or Puzzles,Delicious Food,Buying Thing,Programming, Cracking Keywords,Rubic's Cube,Illusions...... What Do I Hate: QQ,MSN,MailBox,IE,Windows xp,Linux,Pascal，Pointer,Naming Something...... Um,This is my information;if you want to contact me,This is my mailbox(although I hate both qq and mailbox,I still has a qq mailbox...): [email protected]...

Full text and comments »

Please, help: Wunder Fund Round 2016 Constellation: my local/PC output differs from codeforces' On my PC this code outputs 1 9 3 for test№15. But in codeforce another output Here is my submition: http://codeforces.me/contest/618/submission/15669012 I think this is because of doubles, but I'm not sure. Could smb point my mistake, please?

Full text and comments »