Gheal's blog

By Gheal, history, 8 months ago, In English

About a month ago, the 2023 edition of the Romanian Collegiate Programming Contest took place in Iasi as part of RCPCamp, an international ICPC camp organized in Romania by the Alexandru Ioan Cuza University of Iasi (UAIC).

The first day of RCPCamp was authored and prepared by myself, Juve45, lungualex00 and tibinyte.

We would like to thank the following people, who have played a pivotal role in making this contest possible:

The contest can be found here.

If you have any feedback regarding the problems, you can leave it here.

Full text and comments »

Announcement of RCPCamp 2023 Day 1
  • Vote: I like it
  • +42
  • Vote: I do not like it

By Gheal, 13 months ago, In English

As some of you might already know, this blog is inspired by my very good friend tibinyte's post, which you can find here.

The golden problems are my personal favourites, the green problems are pretty good and the red problems are not worth your time in my opinion.

Problem difficulty legend:

  • 1600? : the rating shown is just my estimate, and most likely innacurate
  • 2100* : the rating shown is the average of all the votes cast on the editorial regarding the difficulty of the problem
  • 2500 : the problem has this exact rating on codeforces

Infoleague problems

#
Date
Problem
Contest
Difficulty
Tags
Problem Feedback
Additional comments
1
November 20th 2021
MCLS
Infoleague Autumn 2021 Round 2, Div. 2
1200?
dp
N/A, I would give it a solid 6/10
This is the first problem I've ever set in a public contest, extremely standard.
2
November 20th 2021
Bordered Subarrays
Infoleague Autumn 2021 Round 2, Div. 1
1800?
data structures, binary search
N/A, I would give it a solid 9/10
Quite standard, but a very enjoyable problem with a really clean solution.
3
November 20th 2021
Birthday Nim
Infoleague Autumn 2021 Round 2, Div. 1
1900?
combinatorics, dp
N/A, I would give it a solid 8/10
I came up with the idea for this problem, and tibinyte solved it.
4
December 4th 2021
Mountains
Infoleague Winter 2021 Training Round
1500?
data structures
N/A, I would give it a solid 7/10
A neat, simple problem. Good practice problem for difference arrays.
5
December 4th 2021
Updating Inversions
Infoleague Winter 2021 Training Round
2200?
data structures
N/A, but I wouldn't recommend this problem ever/10
Boring, standard data structures problem with a stupidly low time limit.
6
December 4th 2021
Rubik String
Infoleague Winter 2021 Training Round
900?
greedy/dp
N/A, I would give it a solid 6/10
Meh
7
December 4th 2021
Xor Plains
Infoleague Winter 2021 Training Round
1600?
greedy, constructive algorithms
N/A, I would give it a solid 8.5/10
I initially came up with the idea for this problem back in 2020, probably one of my best problems from that time.
8
January 8th 2022
Make Sum Great Again
Infoleague Winter 2022 Round 1, Div. 2
1400?
binary search
N/A, I would give it a solid 7/10
Good practice problem for binary searching the answer.
9
January 8th 2022
Binary Search Search
Infoleague Winter 2022 Round 1, Div. 2
1800?
math
N/A, I would give it a solid 9.5/10
Magic solution, quite a fun problem to think about.
10
January 8th 2022
Plates
Infoleague Winter 2022 Round 1, Div. 2
1900?
bitmasks, brute force, dp
N/A, I would give it a solid 6/10
Almost a direct application of bitmask dp.
11
January 8th 2022
Touch
Infoleague Winter 2022 Round 1, Div. 2
2200?
greedy, constructive algorithms
N/A, I would give it a solid 9/10
This problem is deceivingly difficult and I would highly recommend you giving it a try.
17
March 30th 2022
Yet Another Constructive Problem
Infoleague Spring 2022 Round, Div. 2
1600*
greedy, constructive algorithms
N/A, I would give it a solid 7/10
I remember that writing the generator for this problem was horrible :)
18
March 30th 2022
Jump
Infoleague Spring 2022 Round, Div. 1
2000*
data structures, combinatorics
N/A, I would give it a solid 9/10
Generally an awesome problem
19
March 30th 2022
Bamboo Coloring
Infoleague Spring 2022 Round, Div. 1
2500*
trees, data structures, constructive algorithms
N/A, 9.25/10
Legendary problem, deceivingly difficult, also quite difficult to implement. Mega orz to anyone who manages to solve it using decremental connectivity (because I couldn't).
51
March 13th 2023
Adece
Infoleague PreOJI 11-12th Grades
2000?
combinatorics, math
N/A, 8.5/10
Pretty interesting problem, inspired by this.
52
March 13th 2023
Aproapecoliniare
Infoleague PreOJI 11-12th Grades
2100?
data structures, implementation, sortings
N/A, 7/10
Mainly an implementation task.
53
March 13th 2023
Retrotrees
Infoleague PreOJI 11-12th Grades
1600?
dsu, greedy, sortings, trees
N/A, 8.75/10
Fun problem.

Peppers++ and Moisil++

Without going into much detail, these are contests for middle and high school students from Romania.

The following problems are available in this group. The statements are unfortunately only in Romanian, in the contest materials section of each problem.

#
Date
Problem
Contest
Difficulty
Tags
Problem Feedback
Additional comments
12
February 23rd 2022
an
Peppers++ 2022, 5th Grade
800?
math
N/A, I would give it an 8/10
This problem is basically a math question.
13
February 23rd 2022
nkspells
Peppers++ 2022, 5-6th Grades
800?
math, brute force
N/A, I would give it a 6/10
This problem is identical to this one, except that, in my version, $$$a_{n+1}=a_n-\text{Min} \cdot \text{Max}$$$
14
February 23rd 2022
pdist
Peppers++ 2022, 6th Grade
1700?
math, brute force
N/A, 3/10
Trust me when I say that this problem is the most atrocious thing ever created.
15
February 23rd 2022
ardei
Peppers++ 2022, 7-8th Grades
1600?
greedy, sortings
N/A, 9.5/10

Brief summary of the statement:


Split an array $$$a_1,a_2,\ldots,a_n$$$ into $$$k$$$ subsequences such that their total cost is minimal. The cost of a subsequence is equal to: $$$\text{Max(subsequence)}-\text{Min(subsequence)}$$$.


$$$1 \le k \le n \le 5 \cdot 10^5$$$, $$$1 \le a_i \le 10^9$$$

16
February 23rd 2022
lacul
Peppers++ 2022, 7-8th Grades
1700?
dp, implementation, brute force, data structures
N/A, 6.5/10
Standard-ish 2-d prefix sum problem.
34
December 8th 2022
Cifra Pierduta
Moisil++ 2022, 9th Grade
800?
math, constructive algorithms
N/A, 5/10
Very easy problem for beginners. If you do not have access to see the problem, join the archive group. The statements are in the bottom right corner of the screen, under contest materials.
35
December 8th 2022
Match
Moisil++ 2022, 9th Grade
1000?
binary search, two pointers
N/A, 6.5/10
Classical problem designed to check whether the students know the basics of binary search.
36
December 8th 2022
Matematica
Moisil++ 2022, 9th Grade
1800?
number theory, math, implementation
N/A, 6/10
The intended complexity is $$$O(n \cdot \frac{\sqrt{x_i}}{log(\sqrt{x_i})})$$$ using a prime sieve and some additional observations.
37
December 8th 2022
Atat s-a putut
Moisil++ 2022, 10th Grade
1000?
data structures, strings
N/A, 7/10
Filler problem requiring basic prefix sum usage.
38
December 8th 2022
Lex
Moisil++ 2022, 10th Grade
1400?
implementation
N/A, 4/10
Another filler problem. Initially created in 2020 and inspired by really old Romanian OI problems.
39
December 8th 2022
Elcapoc
Moisil++ 2022, 11-12th Grades
900?
graphs, math
N/A, 9/10
This problem was supposed to be the div2A for both rounds #804 and #833, however it was rejected both times.
40
December 8th 2022
Enzero
Moisil++ 2022, 11-12th Grades
1800?
greedy, two pointers
N/A, 9.5/10
The best problem from moisil++ 2022 in my opinion.
41
December 8th 2022
Kentroizi
Moisil++ 2022, 11-12th Grades
1900?
binary search, dp, trees
N/A, 9/10
Kinda standard, but a really good problem otherwise.
42
December 9th 2022
Vraja
Moisil++ 2022, 5th Grade
1300?
math
N/A, 7/10
Challenging math problem for 5th graders (nobody solved it mid-contest).
43
December 9th 2022
Strehaia
Moisil++ 2022, 6th Grade
1400?
math, brute force
N/A, 8.5/10
Nobody solved this one during the contest, which really surprised me. Quite a neat problem.
44
December 9th 2022
Romanul adolescentului miop
Moisil++ 2022, 7-8th Grades
1400?
math, greedy, matrices
N/A, 5.5/10
Filler problem, named after a novel by the Romanian author Mircea Eliade.
45
December 9th 2022
Ion
Moisil++ 2022, 7-8th Grades
1800?
math, greedy
N/A, 8.5/10
Deceivingly difficult, a couple of edge cases, named after a novel by the Romanian author Liviu Rebreanu.
46
January 29th 2023
Divizorus
Moisil++ 2022, 5th Grade
800?
math, constructive algorithms
N/A, 7/10
Still cannot believe that nobody solved this during the contest :(
47
January 29th 2023
Oglinditus
Moisil++ 2022, 5th Grade
1600?
math, implementation
N/A, 2/10
Try this problem at your own risk, it's horrific
48
January 29th 2023
Piscinus
Moisil++ 2022, 6th Grade
1000?
math
N/A, 8/10
Cool problem.
49
January 29th 2023
Fibus
Moisil++ 2022, 6th Grade
1700?
math
N/A, 6.5/10
Filler problem
50
January 29th 2023
Votus
Moisil++ 2022, 7-8th Grades
1300?
implementation
N/A, 7/10
Old problem I came up with in 2020, the statement is the editorial.

FIICode

#
Date
Problem
Contest
Difficulty
Tags
Problem Feedback
Additional comments
20
May 14th 2022
Awesome Atek
FIICode 2022 Round #1
1000?
greedy, constructive algorithms, math
N/A, 7/10
Disclaimer: I did not write the statement.
TL;DR: Given $$$n,m$$$ and $$$s$$$, check whether an array $$$a_1,a_2,\ldots,a_n$$$ exists such that $$$1 \le a_i \le m$$$ and $$$\sum_{i=1}^n i \cdot a_i = s$$$.
21
May 14th 2022
Crazy Atek
FIICode 2022 Round #1
2000?
combinatorics, brute force, implementation
N/A, 8/10
The implementation for this problem is really funny, I highly recommend giving it a try.
22
May 15th 2022
Awesome Software
FIICode 2022 Round #2
1000?
brute force, number theory
N/A, 7/10
Decent problem, nothing more to add.
23
May 15th 2022
Boundless Software
FIICode 2022 Round #2
1600?
dp
N/A, 5.5/10
Meh

Codeforces Rounds

#
Date
Problem
Contest
Difficulty
Tags
Problem Feedback
Additional comments
24
July 4th 2022
The Third Three Number Problem
Codeforces Round #804 (Div. 2)
800
greedy, constructive algorithms, math
Participant score: 8.4/10
Cool problem.
25
July 4th 2022
Almost Ternary Matrix
Codeforces Round #804 (Div. 2)
900
bitmasks, constructive algorithms, matrices
Participant score: 8.22/10
antontrygubO_o said he liked this problem.
26
July 4th 2022
The Third Problem
Codeforces Round #804 (Div. 2)
1700
combinatorics, constructive algorithms math
Participant score: 8.59/10
My favourite problem from this contest.
27
July 4th 2022
Almost Triple Deletions
Codeforces Round #804 (Div. 2)
2300
data structures, dp, greedy
Participant score: 9.5/10
Overall a good problem.
28
November 12th 2022
The Ultimate Square
Codeforces Round #833 (Div. 2)
800
math
Participant score: 6.87/10
Truly a 7/10 problem.
29
November 12th 2022
Diverse Substrings
Codeforces Round #833 (Div. 2)
1400
brute force, implementation, strings
Participant score: 8.44/10
Quite the unusual problem.
30
November 12th 2022
Zero Sum Prefixes
Codeforces Round #833 (Div. 2)
1600
brute force, data structures, dp, greedy, implementation
Participant score: 9.05/10
I initially proposed this problem as a div2D since I only had the dp solution. Thanks to IgorI for finding the much more beautiful greedy solution.
31
November 12th 2022
ConstructOR
Codeforces Round #833 (Div. 2)
2100
bitmasks, chinese remainder theorem, combinatorics, constructive algorithms, math, number theory
Participant score: 7.14/10
My favourite problem from this contest and a very controversial one among the participants. The intended solution contains an unusual trick regarding modular inverses.
32
November 12th 2022
Yet Another Array Counting Problem
Codeforces Round #833 (Div. 2)
2300
binary search, data structures, divide and conquer, dp, flows, math, trees
Participant score: 8.72/10
This problem is directly inspired from RMI 2020's floppy and is the first problem featured in tibinyte's blog about cartesian trees :)
33
November 12th 2022
Circular Xor Reversal
Codeforces Round #833 (Div. 2)
3000
bitmasks, constructive algorithms
Participant score: 8.46/10
By far the hardest problem I've ever set. I initially came up with a solution using $$$2.5 \cdot n^2$$$ operations, and IgorI found a better solution using $$$1.5 \cdot n^2$$$ operations
54
May 28th 2023
Twin Permutations
Codeforces Round #875 (Div.1, Div. 2)
800
constructive algorithms
Participant score: 8.77/10
Decent problem.
55
May 28th 2023
The BOSS Can Count Pairs
Codeforces Round #875 (Div.1, Div. 2)
2000
brute force, data structures, math
Participant score: 5.72/10
This problem is unfortunate, nothing more to add.
56
May 28th 2023
Hyperregular Bracket Strings
Codeforces Round #875 (Div.1, Div. 2)
2400
combinatorics, data structures, hashing, math, number theory, sortings, two pointers
Participant score: 9.4/10
Probably the best problem I've ever set, definitely give it a try if you have some time to spare.
57
May 28th 2023
Mex Tree
Codeforces Round #875 (Div.1, Div. 2)
2800
brute force, dp, trees
Participant score: 6.96/10
I initially proposed this problem as a div2. C, thinking that the bipartite coloring approach worked. After we found out that that was not the case, I was barely involved in the preparation of this problem. I absolutely despise the fact that $$$O(N \sqrt{N})$$$ memory doesn't pass, and I hate the forced use of some random tricks from obscure blogs.

This is the problem that I hate the most out of everything I've ever written.

ICPC Camps

#
Date
Problem
Contest
Difficulty
Tags
Problem Feedback
Additional comments
58
October 28th 2023
Yet Another Colored Tree Problem
RCPC 2023 Day 1
2100?
trees, dp, dfs and similar
Participant score: 8.7/10
This problem can be solved without any fancy techniques
59
October 28th 2023
Coins
RCPC 2023 Day 1
1400?
games, number theory
Participant score: 8/10
Decent problem I guess
60
October 28th 2023
Anton Would Approve This Problem
RCPC 2023 Day 1
1500?
strings, greedy/dp
Participant score: 10/10
Would Anton approve this problem?
61
October 28th 2023
Difference In Skill
RCPC 2023 Day 1
1600?
data structures
Participant score: 8/10
One of the problems of all time
62
October 28th 2023
Sign Flipping
RCPC 2023 Day 1
1600?
greedy, data structures
Participant score: 9/10
Decent problem I guess
63
October 28th 2023
The Binary Matrix of All Time
RCPC 2023 Day 1
900?
math
Participant score: 4.3/10
Funny problem
64
October 28th 2023
Weird Divisibility
RCPC 2023 Day 1
2200?
number theory, brute force
Participant score: 7/10
Awesome number theory problem
65
October 28th 2023
Triple Reverse Sort
RCPC 2023 Day 1
800?
sortings
Participant score: 8/10
Rejected Codeforces div2A lol
66
October 28th 2023
Distinctness Queries
RCPC 2023 Day 1
2500?
implementation, data structures
Participant score: 8/10
It took me 2 hours to write the model solution for this problem :skull:

Full text and comments »

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

By Gheal, 14 months ago, In English

1831A — Twin Permutations

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate Problem

1831B — Array Merging

Author: tibinyte

Hints
Solution
Code (tibinyte, C++)
Rate problem

1830A — Copil Copac Draws Trees

Author: alecs

Hints
Solution
Code (Gheal, C++)
Code (alecs, C++)
Rate problem

1830B — The BOSS Can Count Pairs

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Code (Vladithur, Python)
Rate problem

1830C — Hyperregular Bracket Strings

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate problem

1830D — Mex Tree

Author: Gheal

Hints
Solution
Code (tibinyte, C++)
Rate problem

1830E — Bully Sort

Author: valeriu

Thanks to errorgorn for the solution!

Solution
Code (tibinyte, fenwick tree + ordered_set C++)
Code (tibinyte, sqrt decomposition, C++)
Code (errorgorn, divide and conquer, C++)
Rate problem

1830F — The Third Grace

Author: tibinyte

Thanks to errorgorn for the editorial!

Solution
Code (errorgorn, C++)
Code (valeriu, C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments.

Full text and comments »

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

By Gheal, history, 21 month(s) ago, In English

Hello, Codeforces! (or as we say in romanian, "Nu renunţ la tine niciodată")

I am glad to invite everyone to participate in Codeforces Round 833 (Div. 2), which will be held on 12.11.2022 17:35 (Московское время).

This round will be rated for all participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them. All of the problems are authored by me.

I would like to thank the following people, without whom this round would not have been possible:

Here is the scoring distribution: $$$500−1000−1500−2000−2250-2750$$$

Good luck & have fun!

Edit 1: The round is over, the editorial can be found here.

Edit 2: Congratulations to the winners:

Div 1 + Div 2:

Div 2:

Full text and comments »

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

By Gheal, history, 21 month(s) ago, In English

The original blog was deleted yesterday by one of the other authors. We are very sorry about this.

A — The Third Three Number Problem

Authors: antontrygubO_o, Gheal

Hints
Solution
Code (C++)
Rate Problem
Post Scriptum

B — Almost Ternary Matrix

Author: Gheal

Solution
Code (C++)
Rate Problem

C — The Third Problem

Author: Gheal

Hints
Solution
Code (C++)
Rate Problem

D — Almost Triple Deletions

Authors: Gheal

Hints
Solution
Code (C++)
Rate Problem

E — Three Days Grace

Author: tibinyte

Solution
Code (C++)
Rate Problem

Full text and comments »

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

By Gheal, history, 21 month(s) ago, In English

A — The Ultimate Square

Author: Gheal

Hints
Solution
Code (C++)
Rate Problem

B — Balanced Substrings

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

C — Zero Sum Prefixes

Idea: Gheal, Solution: IgorI

Hints
Solution
Code(C++)
Rate problem

D — ConstructOR

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

E — Yet Another Array Counting Problem

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

F — Circular Xor Reversal

Idea: Gheal, Solution: IgorI

Hints
Solution
Code(C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me in the comments.

Full text and comments »

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

By Gheal, 2 years ago, In English
Vote your favourite problem

103633A — The Hatchet

Author: tibinyte

Rate Problem
Solution
Code (C++)

103633B — Floor Or Xor

Author: tibinyte

Rate Problem
Solution
Code (C++)

103633C — Yet Antother Constructive Problem

Author: Gheal

Rate Problem
Hint 1
Hint 2
Solution
Code (C++)
Post Scriptum

103634A — Bamboo Coloring

Rate Problem
Solution
Post Scriptum

Code (C++) (cadmiumky)

Note: this code can be further optimized by removing the $$$lca$$$ function

103634B — Xor Or Floor

Author: tibinyte

Rate Problem
Solution
Code (C++)

103634C — Jump

Author: Gheal

Rate Problem
Solution
Code (C++)
Post Scriptum

Full text and comments »

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

By Gheal, history, 3 years ago, In English

I would like to apologize for the checker issue with problem C. I selected std::ncmp out of habit and forgot to change it afterwards. I would also like to apologize for taking so long to fix the issue. The model solution for div1A was also wrong, and I decided to fix that first. Nonetheless, we still hope that you enjoyed our problems in both Div. 1 and Div. 2.

103503A — Make Sum Great Again

Author: Gheal

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (Gheal)

103503B — Binary Search Search

Author: Gheal

Hint 1
Hint 2
Solution
Code 1 (Gheal)
Code 2 (tibinyte)

103503C — Plates

Author: Gheal

Hint 1
Hint 2
Solution
Code (Gheal)

Full text and comments »

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

By Gheal, history, 3 years ago, In English

Disclaimer: This contest is not rated

Hello Codeforces!

We would like to invite you to the training round of Infoleague Winter 2021, starting from Saturday, December 4th at 14:00 GMT.

This contest will have 8 problems, which are not sorted in increasing order of difficulty. They should provide an interesting challenge to everyone up to around 2300 rating.

The scoring system is IOI-esque, with partial feedback. All problem statements will be available in English.

Problemsetters: Gheal, tibinyte, valeriu

Testers: andrei_boaca, IacobTudor, RaresFelix

Upd 1: Six days down, one to go! The editorial will be posted tommorrow, shortly after the end of the round.

Upd 2: The contest is over, congratulations to the winners!

  1. jiangbowen_ and AlexLorintz with 800 points
  2. sansen with 700 points
  3. MoRanAirConditioner with 620 points
  4. Kira_1234 with 605 points
  5. Egor and xiaolaogou with 565 points

Thank you to everyone who participated! The editorial can be found here.

Full text and comments »

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

By Gheal, history, 3 years ago, In English

Hello Codeforces!

We would like to invite you to the second round of Infoleague Autumn 2021, on Saturday, November 20th at 15:30 GMT.

This contest will have two divisions, Div 1 and Div 2. In both Div 1 and Div 2 you will have to solve 3 problems, which should hopefully be sorted in increasing order of difficulty. Div 2 is recommended for specialists and below, while Div 1 is recommended mainly for experts and low CMs.

Contest links: Div 1, Div 2

  • Contest duration (Div 1): 4:00h
  • Contest duration (Div 2): 3:00h
  • Scoring distribution (Both divisions): 100-100-100

The scoring system is IOI-esque, with partial scoring. All problem statements will be available in both English and Romanian.

Problemsetters: Gheal, tibinyte, valeriu

Testers: andrei_boaca, IacobTudor, RaresFelix

Upd 1: The Div 2 round is over! Congratulations to the winners!

  1. iulianarsenoiu — AK in 18 minutes
  2. vulpes2 — 300 points
  3. Ausmosian — 205 points
  4. merlin_ — 200 points
  5. alexkrunker — 200 points

Also, congratulations to the first solvers of each problem:

Div 2 Editorial: https://mirror.codeforces.com/blog/entry/97107

Upd 2: The Div 1 round is over! Congratulations to the winners!

  1. iulianarsenoiu — 300 points
  2. Pety — 280 points
  3. AlexLorintz — 210 points
  4. maghrabyJr_ — 200 points
  5. lukameladze1 — 180 points

Also, congratulations to the first solvers of each problem:

Div 1 Editorial: https://mirror.codeforces.com/blog/entry/97108

Big thanks to everyone for participating! We would love to see you again at our next rounds!

Full text and comments »

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